后悔操作的实现
in
6
4 -4 1 -3 1 -3
out
5
给出 一个数组
题目让你求出在所加的值不小于0的情况下求出最多可选的数
限制:只能从左往右选
反悔操作的实现
利用优先队列,每当眼前解优于之前的解时,便可以抛弃原先的解选择当前解
key code
const int N=2010;
int n,m,k,a[N],b[N],p[N];
void solve(){
//try it again.
cin>>n;
up(1,n)cin>>a[o];
priority_queue<int>q;
int res=0,cur=0;
up(1,n){
if(a[o]>=0){
cur+=a[o];
res++;
}
else{
if(cur+a[o]>=0){
res++;
cur+=a[o];
q.push(-a[o]);
}
else if(!q.empty()&&q.top()>-a[o]){
cur+=a[o]+q.top();
q.pop();
q.push(-a[o]);
}
}
}
cout<<res;
}
原文链接: https://www.cnblogs.com/liangqianxing/p/17058594.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/312728
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!