2013年8月26日

UVa 11997 - K Smallest Sums

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

struct Sum {
  bool operator<(const Sum & other) const {
    return s > other.s;
  }
  int index, s;
};

int main() {
  int k;
  while (scanf("%d", &k) == 1) {
    int ans[999];
    for (int i = 0; i < k; i++) {
      scanf("%d", &ans[i]);
    }
    sort(ans, ans + k);
    for (int i = 1; i < k; i++) {
      int b[999];
      for (int j = 0; j < k; j++) {
        scanf("%d", &b[j]);
      }
      sort(b, b + k);
      priority_queue<Sum> pq;
      for (int j = 0; j < k; j++) {
        pq.push((Sum){0, ans[j] + b[0]});
      }
      for (int j = 0; j < k; j++) {
        Sum sum = pq.top();
        pq.pop();
        int s = sum.s, index = sum.index;
        ans[j] = s;
        if (index + 1 < k) {
          pq.push((Sum){index + 1, s - b[index] + b[index + 1]});
        }
      }
    }
    for (int i = 0; i < k; i++) {
      printf("%d%s", ans[i], i == k - 1 ? "\n" : " ");
    }
  }
  return 0;
}

沒有留言:

張貼留言