題干：（Uva不放題干了）

題目大意：（實在是自己懶得寫網上找了一個）

解題報告：

? ?調度問題，直接貪心出完成任務需要的時間最長的那個人排序，就行了。

方法正確性的證明以前也寫過了，，這里就不再寫了，，還是貼那篇題解中附的（這篇題解應該也是采用的交換證明法）。

那篇題解

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; struct Node {int a,b; } node[MAX]; bool cmp(Node a,Node b) {return a.b>b.b; } int n; int main() {int iCase = 0;while(~scanf("%d",&n)) {if(n == 0) break;for(int i = 1; i<=n; i++) scanf("%d%d",&node[i].a,&node[i].b);int ans = 0,tmp=0;sort(node+1,node+n+1,cmp);for(int i = 1; i<=n; i++) {tmp += node[i].a;ans = max(ans,tmp + node[i].b);}printf("Case %d: %d\n",++iCase,ans);}return 0 ; }

今天講課學長說了一種貪心的證明思路貌似很正確啊。，先假設找到了一種最優解，然后看我們貪心的方法是否會改變這個最優解，如果改變不了，那么說明我們的方法一定是沒有問題的。

總結

以上是生活随笔為你收集整理的【UVA - 11729】Commando War （贪心，时间调度问题）的全部內容，希望文章能夠幫你解決所遇到的問題。

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