Shoemaker's Problem

本题为贪心算法题，不要想多了，就只是一个贪心算法。

      一个"鞋匠",有n件工作要做，每件工作需要做Ti天，从第一天开始，到开始做该工作的这段时间，每天要付Si元费用。问按怎样一个顺序做能让鞋匠付的钱最少。

       每一件工作，开始的时间越晚，需要付的钱（对于该项工作来说）就越多。做完所有工作的时间是不变的，但是工作的顺序是可变的。而没件工作的罚款比率不同（天数每天罚钱数的比）。对于所有的工作来说，比率越小的，放在越前面做，总体罚钱的数就会越少。所以，我们只要算出比率，排序后输出序号就好了。

      这里又有问题了，细心的孩子会发现，在同一组案例中。可能会有1件以上的工作他的这个比率一样，那又怎么办呢？题目说了，要是有几个符合要求的答案，输出字典序最小的那一个。也就是说，要是比率一样的话，就按开始输入的顺序排序就好了（序号）。

      其实真的很简单，就是输入，存储，算比率，排序，输出就好了。我承认我想多了，和杭电上的一个做作业的动归题搞混思想了。

#include<stdio.h>
#include<algorithm>
using namespace std;
struct node
{
    int num;
    int time;
    int cent;
    double bi;
} shoe[1005];
bool cmp(node a,node b)   //排序
{
    if(a.bi==b.bi)   //比率相同，按输入顺序排序
        return a.num<b.num;
    return a.bi<b.bi;   //比率小的排前面
}
int main()
{
    int t;
    int n;
    int i;
    int f=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=0; i<n; i++)  //输入
        {
            shoe[i].num=i+1;
            scanf("%d%d",&shoe[i].time,&shoe[i].cent);
            shoe[i].bi=(double)shoe[i].time/shoe[i].cent;  //算比率，记得数据类型强制装换
        }
        sort(shoe,shoe+n,cmp);  //排序
        if(f)printf("\n");  //案例之间有空行，这里处理不好，UVA会直接返回WRONG ANSWER
        printf("%d",shoe[0].num);  //输出
        for(i=1; i<n; i++)printf(" %d",shoe[i].num);
        printf("\n");
        f=1;
    }
    return 0;
}