2013年1月6日

UVa 10026 - Shoemaker's Problem


#include <cstdio>
#include <algorithm>

struct J {
  int t, c, n;
};

bool cmp(J a, J b) {
  return a.c * b.t > b.c * a.t;
}

int main() {
  int T;
  scanf("%d", &T);
  J job[1000];
  while (T--) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
      scanf("%d%d", &job[i].t, &job[i].c), job[i].n = i + 1;
    std::sort(job, job + n, cmp);
    for (int i = 0; i < n; i++)
      printf("%d%s", job[i].n, i == n - 1 ? "\n" : " ");
    if (T) puts("");
  }
  return 0;
}

2 則留言: