首页 > 代码库 > [题解]UVA10026 Shoemaker's Problem

[题解]UVA10026 Shoemaker's Problem

2024-07-11 19:20:07   219人阅读

链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=967

描述：要做n双鞋子，第 i 双鞋子要做Ti天，每天消耗Si的钱（当前正在做第 i 双鞋子时不耗钱）。求在最少消耗钱的情况下做鞋子的顺序。

思路：贪心

        明显是一个排序的模型，然后我们就思考顺序怎么确定。考虑当前两双鞋子a和b，它们的顺序对它们前后的鞋子都没有影响，它们所创造的影响仅仅是a和b本身的消耗。顺序是ab时，消耗为Ta*Sb；顺序是ba时，消耗为Tb*Sa。只需要比较Ta*Sb和Tb*Sa的大小排序就可以了。

 

我的实现：

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 #define MaxN 1020 7 struct node 8 { 9     int Time,Fine,Num;10 }Shoe[MaxN];11 int T,n;12 inline void Get_int(int &Ret)13 {14     char ch;15     bool flag=false;16     for(;ch=getchar(),ch<‘0‘||ch>‘9‘;)17         if(ch==‘-‘)18             flag=true;19     for(Ret=ch-‘0‘;ch=getchar(),ch>=‘0‘&&ch<=‘9‘;Ret=Ret*10+ch-‘0‘);20     flag&&(Ret=-Ret);21 }22 bool Cmp(node a,node b)23 {24     return a.Fine*b.Time > a.Time*b.Fine;25 }26 int main()27 {28     Get_int(T);29     int i;30     while(T--)31     {32         Get_int(n);33         for(i=1;i<=n;++i)34         {35             Get_int(Shoe[i].Time);36             Get_int(Shoe[i].Fine);37             Shoe[i].Num=i;38         }39         sort(Shoe+1,Shoe+1+n,Cmp);40         for(i=1;i<n;++i)41             printf("%d ",Shoe[i].Num);42         printf("%d\n",Shoe[n].Num);43         if(T)44             printf("\n");45     }46     return 0;47 }
View Code

状态：


联系
我们