uva10026 - Shoemaker's Problem（贪心）

本文主要是介绍uva10026 - Shoemaker's Problem（贪心），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：10026 - Shoemaker's Problem

题目大意：有个鞋匠在同一天接到了一堆的生意。可是他每天只能做一双鞋，给出做每双鞋需要的时间和推辞做鞋的赔偿。问怎样合理的分配才能使得赔偿最小。

解题思路：鞋子编号  要花的时间  需要的赔偿（每天）

                      1                    1                100

                      2                    5                  4

这样的两双鞋有两种安排：  

                     做完1再做2      赔偿  1 * 4；

                     做完2再做1      赔偿   5 * 100；

                     所以应该将时间/赔偿小的鞋子先做。

代码：

#include <stdio.h>
#include <algorithm>
using namespace std;const int N = 1005;struct Shoe {int i;int t;int f;
}s[N];int cmp (const Shoe &a, const Shoe &b) {return a.t * b.f < b.t * a.f;}int main () {int t;scanf ("%d", &t);int n;while (t--) {scanf ("%d", &n);for (int i = 0; i < n; i++) {scanf ("%d%d", &s[i].t, &s[i].f);s[i].i = i + 1;}sort (s, s + n, cmp);for (int i = 0; i < n; i++) {if (i == n - 1)printf ("%d\n", s[i].i);elseprintf ("%d ", s[i].i);}if (t)printf ("\n");}return 0;
}

这篇关于uva10026 - Shoemaker's Problem（贪心）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---