题意
LYH拥有一堆药水,每瓶药水i有一种功效a[i];如果a[i]为正,则加血;如果为负,则扣血。
他决定从第一瓶开始,依次绝对每瓶喝还是不喝;最开始血量为0,他希望喝的药水尽量多,并且不会中途挂掉(喝光任何一瓶药水的时候血量都是大于或等于0)
Input
输入的第一行包含一个数 n.
接下来一行,有 n 个整数,第 i 个数表示 a[i].
Output
输出一共一个数,表示 LYH 最多能喝几瓶药水还没挂掉.
样例输入
6
4 -4 1 -3 1 -3
样例输出
5
解释
LYH可以依次喝 1, 3, 4, 5, 6 五瓶药水. 他的血量最开始为 0,之后喝掉药水的血量依次为 4, 5, 2, 3, 0.
核心思路(反悔贪心)
在喝不死的情况下使劲喝。
然后当遇到一瓶“毒药”可能会把自己喝死的时候,我们去看一下以前所有的“毒药”,如果以前有一瓶毒药扣血比现在的多,那我宁愿之前不喝那瓶毒药,而喝现在的毒药.
例如:2,-2,-1.....这个序列,我喝到-1的时候发现喝不了了,那我宁愿把-2这瓶换成-1,这样不仅不会影响之前“喝不死”的判定,同时还能加点血。
那如果要换之前的“毒药”,根据贪心,我肯定换掉之前扣血最多的“毒药”,所以我们用一个堆来维护一下。
贪心策略
0.用一个大根堆维护现在要喝的所有毒药。
1.顺序的喝药,如果喝不死,就喝,ans+=1;
2.如果喝毒药会死,我们就看一下要喝的毒药最大值是多少,如果之前的毒药扣血比现在多,就把之前的毒药换成现在的。
最后输出ans
代码
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>using namespace std;
typedef long long ll;
int n;
priority_queue <ll,vector<ll>,greater<ll>> heap;
ll sum,ans;int main(){freopen("potion.in","r",stdin);freopen("potion.out","w",stdout);scanf("%d",&n);ans=sum=0;for(int i=1;i<=n;i++){ll tmp;scanf("%lld",&tmp);if(sum+tmp>= 0){sum+=tmp;heap.push(tmp);ans++;}else if(heap.size()>0&&heap.top()<tmp){sum+=tmp-heap.top();heap.pop();heap.push(tmp); }}printf("%lld\n",ans);return 0;
}