思路：把每个节点存到堆（大根堆）里。 如果节点放入后总时间没有超过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; }
