南通市建设局网站成都网站建设方案外包

思路：把每个节点存到堆（大根堆）里。 如果节点放入后总时间没有超过m则放入堆中；如果总时间超过了，就看堆头元素是否比新元素大。如果大，则删除堆头（反悔贪心）。

注意别忘记开long long

代码：

#include <bits/stdc++.h>
using namespace std;
const long long int N = 1e5 + 10;
long long int n, m;
struct node
{long long int x;long long int t;
} a[N];
long long int ans, sum;
priority_queue<long long int> q;
bool cmp(node a, node b)
{return a.x < b.x;
}
int main()
{cin >> n >> m;for (long long int i = 1; i <= n; i++){cin >> a[i].x >> a[i].t;}sort(a + 1, a + n + 1, cmp); // 按x由小到大排序for (long long int i = 1; i <= n; i++){if (sum + a[i].x + a[i].t <= m) // 没超过m{                               // sum保持t的总和sum += a[i].t;q.push(a[i].t);}else{if (!q.empty() && sum - q.top() + a[i].x + a[i].t <= m){ // 替换堆头sum = sum - q.top() + a[i].t;q.pop();q.push(a[i].t);}}}cout << q.size();return 0;
}