題目鏈接：點擊查看

題目大意：現在有一個人，初始時有r元錢，現在有n個項目需要讓他來解決，每個項目的門檻是a元錢，完成項目后的報酬是b元（報酬可以是負數），問能否在適當調整項目順序后完成所有項目，能的話輸出YES，否則輸出NO

題目分析：我是在補題的時候做的這個題，所以就可以直接看到標簽了，標簽只寫了是一個2100分的貪心，不過想了好久還只是想到了一點點部分，這個題目的核心是如何排序，只要排好序后，從頭到尾按照題意掃描一遍就可以判斷了

那么對于這個題目的排序，我們首先肯定是要優先拿報酬都是非負數的，這樣才能讓這個人的錢越來越多，則對于報酬都是正數的項目來說，最優解是讓門檻較低的項目排在前面，這樣就解決了報酬是正數的項目了

則剩下的就是報酬是負數的項目了，我們不能單純對于門檻的大小來排序，隨便找一組數據就hack掉了，比如：

2 10

10 -5

8 -1

所以肯定還是需要思考的，因為我們在完成項目后需要盡可能的讓剩下的錢更多，那么就可以按照a+b作為權值進行降序排序，因為當這個人在完成當前項目的時候，錢一定是大于等于門檻的，我們不妨設當前的錢就是門檻，這樣一來在完成當前項目后，剩下的錢就是a+b元了，這樣就能簡單證明出來了（好像不太嚴謹，但大概能說明這樣排序的可行性了）

排完序之后掃一遍，按照規則判斷就行了，規則就是這個人的錢每次必須都比門檻要高，并且錢不能出現負數

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=110;int n,r;struct Node {int a,b,flag;//flag=0:b為正或零 flag=1:b為負 bool operator<(const Node& k)const{if(flag!=k.flag)return flag<k.flag;if(flag==0)//都是正數return a<k.a;//這里如果都是正數的話，那么b的大小就無所謂了，只需要讓a升序排列就行了else//都是負數 {if(a+b!=k.a+k.b)//優先按照a+b降序排序return a+b>k.a+k.b;return a>k.a;//其次按照a較大的排序}} }a[N];bool check() {for(int i=1;i<=n;i++){if(r<a[i].a)//如果當前的錢不足以抵消當前任務的門檻return false;r+=a[i].b;if(r<0)//如果中途出現了負數return false;}return true; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);scanf("%d%d",&n,&r);for(int i=1;i<=n;i++){scanf("%d%d",&a[i].a,&a[i].b);if(a[i].b>=0)a[i].flag=0;elsea[i].flag=1;}sort(a+1,a+1+n);if(check())printf("YES\n");elseprintf("NO\n");return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 1203F1 Complete the Projects (easy version)(贪心)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。