codeforces 1203 F1 Complete the Projects (easy version) 贪心

https://codeforces.com/problemset/problem/1203/F1
题目大意：给出$n$个任务，每个任务有$ratin{g}_i$限制和加分$scor{e}_i$($scor{e}_i$可能是个负数)，给出你的初始$rating$，当$rating>ratin{g}_i$时，才能完成第$i$个任务，完成任务后：$rating=rating+scor{e}_i$，你可以任意安排完成任务的顺序，且完成任意一个任务后必须满足$rating>=0$，若能实现输出$YES$否则输出$NO$。

思路：贪心，$score$为正的，按照$rating$从小到大排序，$score$为负的；在最坏情况下，每个任务完成后的最高分数为：$rating=ratin{g}_i+scor{e}_i$，按照这个值从大到小排序。

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define pr pair<int,int>
typedef long long ll;
using namespace std;
int n,tot;
struct node
{
int a,b;
node(){}
node(int aa,int bb)
{
a=aa,b=bb;
}
}a[105],b[105];
bool cmp1(node x,node y)
{
return x.a<y.a;
}
bool cmp2(node x,node y)
{
return (x.a+x.b)>(y.a+y.b);
}
int main()
{
scanf("%d %d",&n,&tot);
int u,v;
int len1=0,len2=0;
for(int i=0;i<n;i++)
{
scanf("%d %d",&u,&v);
if(v>=0)
a[len1++]=node(u,v);
else
b[len2++]=node(u,v);
}
bool flag=1;
sort(a,a+len1,cmp1);
sort(b,b+len2,cmp2);
for(int i=0;i<len1;i++)
{
if(tot>=a[i].a)
tot+=a[i].b;
else
flag=0;
}
for(int i=0;i<len2;i++)
{
if(tot>=b[i].a)
tot+=b[i].b;
else
flag=0;
}
if(tot<0)
flag=0;
printf("%sn",flag?"YES":"NO");
return 0;
}

最后

以上就是成就柜子为你收集整理的codeforces 1203 F1 Complete the Projects (easy version) 贪心的全部内容，希望文章能够帮你解决codeforces 1203 F1 Complete the Projects (easy version) 贪心所遇到的程序开发问题。

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