題目大意：鞋匠有n個任務，第i個任務要花費t_i天，同時第i個任務每耽誤一天要有f_i的罰金。求完成所有任務的最小罰金。

　　雖然知道是貪心，可是并不確定如何作貪心選擇，只好“取經”了...假如有兩個任務i和j，先做i的話罰金就是t_i*f_j，先做j的話就是t_j*f_i (其實我也想到這個了，就是不知道怎么用），可以得到f/t大的任務應該先做。對貪心有多了一點認識了，貪心做出當前情況下的最好選擇，與子問題無關，而動態規劃中做出的選擇與子問題有關系，要依賴子問題的結果。

1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 #define MAXN 1000+10 5 6 double w[MAXN]; 7 int ans[MAXN]; 8 9 bool cmp(const int a, const int b) 10 { 11 return w[a] > w[b]; 12 } 13 14 int main() 15 { 16 #ifdef LOCAL 17 freopen("in", "r", stdin); 18 #endif 19 int N; 20 scanf("%d", &N); 21 while (N--) 22 { 23 int n; 24 scanf("%d", &n); 25 int time, fine; 26 for (int i = 1; i <= n; i++) 27 { 28 scanf("%d%d", &time, &fine); 29 w[i] = 1.0 * fine / time; 30 } 31 for (int i = 1; i <= n; i++) ans[i] = i; 32 sort(ans+1, ans+n+1, cmp); 33 for (int i = 1; i <= n; i++) 34 printf("%d%s", ans[i], (i==n)?"\n":" "); 35 if (N) printf("\n"); 36 } 37 return 0; 38 } View Code

　　如果有多個方案時要字典序輸出，考慮到sort函數是不穩定的，感覺會出錯，但還是抱著試試的態度提交了，想著如果WA了就換stable_sort，但是竟然AC了...這個...先不管了，先就這樣吧

轉載于:https://www.cnblogs.com/xiaobaibuhei/p/3226776.html

總結

以上是生活随笔為你收集整理的UVa 10026 - Shoemaker's Problem的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。