UVA 11729 (13.09.09) - c++编程基础

题意:

就是要对T个士兵洗脑, 叫他们做事

洗脑需要时间的, 为A

洗完脑就滚蛋吧, 乖乖听话做事去, 做事时间为B;

求对所有士兵洗完脑并做完全部事后, 一共花了多少时间

要点:

训完一个士兵后, 这个士兵做事去了, 这时候已经可以去训下一个了

做法:

明显的, 我们要把做事时间最久的找出来, 这样, 他做事的时候可以去训其他士兵, 节约时间

故先对做事时间排名, 然后模拟各种情况就是了~

不要乱, 不会乱!

AC代码:

#include  
#include  
  
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;  
}