2013年8月24日

UVa 11729 - Commando War

#include <cstdio>
#include <algorithm>
using namespace std;

struct Soldier {
  bool operator<(const Soldier & other) const {
    return (j != other.j) ? (j > other.j) : (b < other.b);
  }
  int b, j;
} soldiers[1000];

int main() {
  int n, C = 1;
  while (scanf("%d", &n) && n) {
    for (int i = 0; i < n; i++) {
      scanf("%d%d", &soldiers[i].b, &soldiers[i].j);
    }
    sort(soldiers, soldiers + n);
    int bt = 0, ans = 0;
    for (int i = 0; i < n; i++) {
      bt += soldiers[i].b;
      ans = max(ans, soldiers[i].j + bt);
    }
    printf("Case %d: %d\n", C++, ans);
  }
  return 0;
}

沒有留言:

張貼留言