【題解】UVA 11729 Commando War

【題目敘述】https://vjudge.net/problem/UVA-11729
【解題想法】Greedy

  • 參考 ZeroJudge b231: TOI2009 第三題:書【圖解
#include <iostream>
#include <algorithm>
using namespace std;

struct Soldier{
    int B, J;
};
bool cmp(Soldier p, Soldier q){
    return p.J > q.J;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N, TC = 1;
    while (cin >> N && N){
        Soldier soldier[N];
        for (int i = 0; i < N; i++){
            cin >> soldier[i].B  >> soldier[i].J;
        }
        sort(soldier, soldier+N, cmp);
        int sum_B = 0, sum_J  = 0;
        for (int i = 0; i < N; i++){
            sum_B += soldier[i].B;
            if (sum_B + soldier[i].J > sum_J) sum_J = sum_B + soldier[i].J;
        }
        cout << "Case " << TC++ << ": ";
        cout << sum_J << "\n";
    }
    return 0;
}
分享本文 Share with friends