我要建网站需要什么,付费wordpress,网站留言发送到qq邮箱,建设网站利用点击量赚钱思路#xff1a;把每个节点存到堆#xff08;大根堆#xff09;里。 如果节点放入后总时间没有超过m则放入堆中#xff1b;如果总时间超过了#xff0c;就看堆头元素是否比新元素大。如果大#xff0c;则删除堆头#xff08;反悔贪心#xff09;。
注意别忘记开long l…
思路把每个节点存到堆大根堆里。 如果节点放入后总时间没有超过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_queuelong 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;
}
