Money Buys Less Happiness Now
1.题目大意:
有n天,每天可以赚x块钱,然后每天可以通过花\(C_{i}\)块钱购买1点快乐值,然后每天赚的钱至少要在下一天才能用,问最多能获得多少快乐值。
2.解题思路:
我们发现天数变得很多,不能像e题那样dp了,所以要用贪心。具体来讲,我们碰到当前能买的就直接买,如果买不了,就从之前买过的但是比自己贵的那些物品里面挑一个最贵的,然后用当前的物品替换。可以发现这样一定是最优的,因为换掉最贵的就一定能留下更多的钱买后面的物品。(可能从来没做过这样的题吧,所以想半天一点思路都没有
3.代码:
void solve() {
ll n, x;cin >> n >> x;
vi a(n + 1);
for(int i = 1; i <= n; i++) cin >> a[i];
ll now = 0;
priority_queue<ll> q;
for(int i = 1; i <= n; i++) {
if(now >= a[i]) {
now -= a[i];
q.push(a[i]);
} else {
if(!q.empty() && q.top() > a[i]) {
now += q.top() - a[i];
q.pop();
q.push(a[i]);
}
}
now += x;
}
cout << q.size() << "\n";
}
标签:Now,Less,946,Money,Buys,now,Happiness
From: https://www.cnblogs.com/orzkeyhacker/p/18209242