题目大意：鞋匠有n个任务，第i个任务要花费t_i天，同时第i个任务每耽误一天要有f_i的罚金。求完成所有任务的最小罚金。

　　虽然知道是贪心，可是并不确定如何作贪心选择，只好“取经”了...假如有两个任务i和j，先做i的话罚金就是t_i*f_j，先做j的话就是t_j*f_i (其实我也想到这个了，就是不知道怎么用），可以得到f/t大的任务应该先做。对贪心有多了一点认识了，贪心做出当前情况下的最好选择，与子问题无关，而动态规划中做出的选择与子问题有关系，要依赖子问题的结果。

1 #include 
      
        2 #include 
       
         3 using namespace std; 4 #define MAXN 1000+10 5  6 double w[MAXN]; 7 int ans[MAXN]; 8  9 bool cmp(const int a, const int b)10 {11     return w[a] > w[b];12 }13 14 int main()15 {16 #ifdef LOCAL17     freopen("in", "r", stdin);18 #endif19     int N;20     scanf("%d", &N);21     while (N--)22     {23         int n;24         scanf("%d", &n);25         int time, fine;26         for (int i = 1; i <= n; i++)27         {28             scanf("%d%d", &time, &fine);29             w[i] = 1.0 * fine / time;30         }31         for (int i = 1; i <= n; i++)   ans[i] = i;32         sort(ans+1, ans+n+1, cmp);33         for (int i = 1; i <= n; i++)34             printf("%d%s", ans[i], (i==n)?"\n":" ");35         if (N)   printf("\n");36     }37     return 0;38 }
       
      

　　如果有多个方案时要字典序输出，考虑到sort函数是不稳定的，感觉会出错，但还是抱着试试的态度提交了，想着如果WA了就换stable_sort，但是竟然AC了...这个...先不管了，先就这样吧