codeforces 1203F2 Complete the Projects (hard version)

传送门：http://codeforces.com/problemset/problem/1203/F2

由简单的我们知道要在b<0的部分，我们需要选择a+b尽可能大的

所以这题要求最多能选多少个，b>=0的情况我们尽量拿就行了

b<0的情况，就尽量先拿a+b大的，当某个时刻某个物品不能拿的时候，就从之前的拿的物品中b最小的（减得最多的）把他(可能是当前这个物品本身)丢出去，就是一种时光倒流法的贪心。

#include<bits/stdc++.h>
#define maxl 1010
using namespace std;
int n,r,ans;
struct node
{
int a,b;
bool operator < (const node &y)const
{
return a<y.a;
}
bool operator > (const node &y)const
{
return a>y.a;
}
};
vector <node> pos,neg;
priority_queue<int,vector<int>,greater<int> >q;
inline void prework()
{
scanf("%d%d",&n,&r);
node d;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&d.a,&d.b);
if(d.b<0)
neg.push_back(d);
else
pos.push_back(d);
}
sort(pos.begin(),pos.end());
int l=neg.size();
for(int i=0;i<l;i++)
{
neg[i].a+=neg[i].b;
neg[i].a=max(neg[i].a,0);
}
sort(neg.begin(),neg.end());
reverse(neg.begin(),neg.end());
}
inline void mainwork()
{
ans=0;
int l=pos.size();
for(int i=0;i<l;i++)
if(r>=pos[i].a)
r+=pos[i].b,ans++;
l=neg.size();
for(int i=0;i<l;i++)
{
r+=neg[i].b;
q.push(neg[i].b);
if(r<neg[i].a)
{
r-=q.top();
q.pop();
}
}
ans+=q.size();
}
inline void print()
{
printf("%dn",ans);
}
int main()
{
prework();
mainwork();
print();
return 0;
}

最后

以上就是无语河马为你收集整理的codeforces 1203F2 Complete the Projects (hard version)的全部内容，希望文章能够帮你解决codeforces 1203F2 Complete the Projects (hard version)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。