a673 - 10026 - Shoemaker's Problem
題目描述
鞋匠有 N 件工作，每件工作有完成所需天數和延遲一天的罰金。目標是找到一個工作順序，使得總罰金最小。
解題思路
這題可以使用貪心演算法解決。核心思想是按照每個工作延遲一天的罰金除以完成所需天數的比率進行排序。比率越高，表示延遲一天的罰金越高，因此應該優先完成這些工作。如果比率相同，則按照工作編號排序，以確保輸出字典序最小的結果。
具體步驟如下：
- 讀取輸入，將每個工作的天數和罰金儲存到一個結構體中，並記錄原始工作編號。
- 使用自定義比較函數
cmp對工作進行排序。比較函數首先比較罰金除以天數的比率，如果比率相同，則比較工作編號。 - 輸出排序後的工作編號。
複雜度分析
- 時間複雜度: O(N log N)，主要來自排序操作。
- 空間複雜度: O(N)，用於儲存工作資訊。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
struct a{
int a,b,c;
};
a ar[1001];
bool cmp(a x,a y){
if(x.b*y.a>x.a*y.b)
return 1;
if(x.b*y.a==x.a*y.b){
if(x.c>y.c)return 0;
return 1;
}
return 0;
}
int main(){
int t,n;
cin >> t;
while(t--){
cin >> n;
for(int i=0;i<n;++i){
cin >> ar[i].a >> ar[i].b;
ar[i].c=i+1;
}
sort(ar,ar+n,cmp);
for(int i=0;i<n;++i){
cout << ar[i].c ;
if(i!=n-1)cout << " ";
}
cout << "\n";
if(t)cout << "\n";
}
}