UVa 10026 Shoemaker's Problem

　　本題是指鞋匠一次只能選一個工作做，以Sample Input為例，如果先選第一件工作，它需要完成的時間為3天，那麼這3天就無法做其他工作，罰金就為3*(1000+2+5)元，本題要找出選擇工作的次序使得罰金最小。

想法：
　　兩相鄰事件a(Ta,Fa),b(Tb,Bb)無論排成ab或是ba，其他部分的罰金是固定的所以差異在於ab(Ta*Fb)還是ba(Tb*Fa)的損失較小

假如是ab較小，則

• (Ta*Fb)<(Tb*Fa) 
• => (Fa/Ta)>(Fb/Tb) 

a的(罰金/時間)比較大

因此本題解法是將每個工作(Fi/Ti)由大到小排序

	#include<algorithm>
	#include<cstdio>
	using namespace std;
	struct Node{
	double tf;
	int order;
	};
	bool cmp(Node a,Node b){
	return a.tf>b.tf;
	}
	int main(){
	int Case,N;
	scanf("%d",&Case);
	while(Case--){
	scanf("%d",&N);
	int time[1011],fine[1011],i;
	Node a[1011];
	for(i=0;i<N;i++){
	scanf("%d %d",&time[i],&fine[i]);
	a[i].tf=fine[i]*1.0/time[i]; //轉double記得*1.0
	a[i].order=i+1;
	}
	sort(a,a+N,cmp);
	printf("%d",a[0].order);
	for(i=1;i<N;i++)
	printf(" %d",a[i].order);
	printf("\n");
	if(Case) //注意最後一個Case不能有換行
	printf("\n");
	}
	return 0;
	}

view raw [UVa] 10026 Shoemaker's Problem.cpp hosted with ❤ by GitHub