UVA10026

使用貪心按照性價比排序即可，唯一需要注意的就是它的輸出格式。

The outputs of two consecutive cases will be separated by a blank line.

#include<iostream>   
#include<algorithm>   
using namespace std;  
  
struct Node{  
    int index;    //每雙鞋子的索引   
    double time;  
    double fine;  
    double cost;   //性價比   
};  
Node test[1001];  
bool cmp(const Node& node1,const Node& node2);  
int main()  
{  
    int  testNumber;  
    cin>>testNumber;  
    for(int i=1;i<=testNumber;i++)  //測試的數目   
    {  
        int shoseNumber;  
        cin>>shoseNumber;  
        for(int j=0;j<shoseNumber;j++)   //獲取輸入   
        {  
  
            cin>>test[j].time;  
            cin>>test[j].fine;  
            test[j].index=j+1;   //計算性價比   
            test[j].cost=test[j].fine/test[j].time;  
        }  
        sort(test,test+shoseNumber,cmp);  
        for(int h=0;h<shoseNumber-1;h++)  
            cout<<test[h].index<<" ";  
        cout<<test[shoseNumber-1].index<<endl;  
        if(i!=testNumber)  
            cout<<endl;  
    }  
    return 0;  
}  
  
bool cmp(const Node& node1,const Node& node2)  
{  
    if(node1.cost!=node2.cost)  
        return node1.cost>node2.cost;  
    else  
        return node1.cost<node2.cost;  
}  

#include<iostream>
#include<algorithm>
using namespace std;

struct Node{
    int index;    //每雙鞋子的索引
    double time;
    double fine;
    double cost;   //性價比
};
Node test[1001];
bool cmp(const Node& node1,const Node& node2);
int main()
{
    int  testNumber;
    cin>>testNumber;
    for(int i=1;i<=testNumber;i++)  //測試的數目
    {
        int shoseNumber;
        cin>>shoseNumber;
        for(int j=0;j<shoseNumber;j++)   //獲取輸入
        {

            cin>>test[j].time;
            cin>>test[j].fine;
            test[j].index=j+1;   //計算性價比
            test[j].cost=test[j].fine/test[j].time;
        }
        sort(test,test+shoseNumber,cmp);
        for(int h=0;h<shoseNumber-1;h++)
            cout<<test[h].index<<" ";
        cout<<test[shoseNumber-1].index<<endl;
        if(i!=testNumber)
            cout<<endl;
    }
    return 0;
}

bool cmp(const Node& node1,const Node& node2)
{
    if(node1.cost!=node2.cost)
        return node1.cost>node2.cost;
    else
        return node1.cost<node2.cost;
}