UVA 11729 (13.09.09)

題意: 就是要對T個士兵洗腦, 叫他們做事 洗腦需要時間的, 為A 洗完腦就滾蛋吧, 乖乖聽話做事去, 做事時間為B; 求對所有士兵洗完腦並做完全部事後, 一共花了多少時間?   要點: 訓完一個士兵後, 這個士兵做事去了, 這時候已經可以去訓下一個了   做法: 明顯的, 我們要把做事時間最久的找出來, 這樣, 他做事的時候可以去訓其他士兵, 節約時間 故先對做事時間排名, 然後模擬各種情況就是了~ 不要亂, 不會亂!   AC代碼:  

#include<stdio.h>  
#include<algorithm>  
  
using namespace std;  
  
struct soldier {  
    int A;  
    int B;  
}s[1234];  
  
int cmp(soldier a, soldier b) {  
    return a.B > b.B;  
}  
  
int cas = 0;  
  
int main() {  
    int T;  
    int sum;  
    while(scanf("%d", &T) != EOF && T) {  
        int t1, t2;  
        sum = 0;  
        for(int i = 0; i < T; i++)  
            scanf("%d %d", &s[i].A, &s[i].B);  
        sort(s, s+T, cmp);  
        for(int i = 0; i < T; i++) {  
            if(i == 0) {  
                sum += s[i].A;  
                t1 = s[i].B;  
            }  
            if(i != 0) {  
                t2 = s[i].A + s[i].B;  
                if(t2 > t1) {  
                        sum += s[i].A;  
                        t1 = s[i].B;  
                }  
                else {  
                    t1 = t1 - s[i].A;  
                    sum += s[i].A;  
                }  
            }  
        }  
        sum += t1;  
        printf("Case %d: ", ++cas);  
        printf("%d\n", sum);  
    }  
    return 0;  
}