题意：鞋匠一口气接到了不少生意，但是做鞋需要时间，鞋匠只能一双一双地做，根据协议每笔生意如果拖延了要罚钱。
给出每笔生意需要的天数和每天的罚钱数，求出最小罚钱的排列顺序。
只要按罚款/天数去从大到小排序，如果比例一样就按序号排序（要求字典序）。
解释我就不献丑了，附上Staginner大神的证明：
对于为什么贪心策略是这个样子的，我们不妨拿相邻的两个事件a、b来说明一下。由于a、b之后的事件是固定的，所以我们无论排成ab还是排成ba后面部分的损失都是固定的，那么损失的差别主要来源于究竟是排成ab还是排b成a。排ab的损失为ta*fb，排ba的损失为tb*fa，那么如果ta*fb<tb*fa，我们就排成ab，这样可以得到fa/ta>fb/tb，推而广之，就得到了我们的贪心策略。
代码：
/*
* Author: illuz <iilluzen@gmail.com>
* Blog: http://blog.csdn.net/hcbbt
* File: uva10026.cpp
* Lauguage: C/C++
* Create Date: 2013-08-25 20:11:52
* Descripton: UVA 10026 Shoemaker's Problem, sort + struct
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <list>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <utility>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repu(i, a, b) for (int i = (a); i < (b); i++)
#define repf(i, a, b) for (int i = (a); i <= (b); i++)
#define repd(i, a, b) for (int i = (a); i >= (b); i--)
#define swap(a, b) {int t = a; a = b; b = t;}
#define mc(a) memset(a, 0, sizeof(a))
#define ms(a, i) memset(a, i, sizeof(a))
#define sqr(x) ((x) * (x))
#define FI(i, x) for (typeof((x).begin()) i = (x).begin(); i != (x).end(); i++)
typedef long long LL;
typedef unsigned long long ULL;
/****** TEMPLATE ENDS ******/
const int MAXN = 1002;
struct Deal {
int no;
double pri;
int day;
friend bool operator < (const Deal& a, const Deal& b) {
if (a.pri != b.pri) return a.pri > b.pri;
else return a.no < b.no;
}
} d[MAXN];
int main() {
int t, n, m;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
rep(i, n) {
d[i].no = i + 1;
scanf("%d%d", &d[i].day, &m);
d[i].pri = (double)m / (double)d[i].day;
};
sort(d, d + n);
printf("%d", d[0].no);
repu(i, 1, n) printf(" %d", d[i].no);
printf("
");
if (t) printf("
");
}
return 0;
}