uva 10026 Shoemaker's Problem 贪心

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

题意：一个鞋匠收到若干单生意，每次他都只能修一双鞋，而没双鞋都有它修理的时间，和没修之前每天的赔偿，

思路：假设F1，T1，F2，T2，分别是第一双鞋的赔偿和时间，以及第二双鞋的赔偿和时间，我们假设先选第1双，那么总赔偿就是F2*T1,如果是第2双就是F1*T2，那我们当然是选赔偿最少的了，如果F2*T1 < F1 * T2 的话，就能变形为 （F2/T2）/ （F1/T1） < 1 ,换句话就是说，如果赔偿要较少的话，那么F1/T1 要比较大，所以我们没次都是选比值较大的那双鞋,好了，这就很明显是贪心了

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 1010;int num[MAXN],t[MAXN],f[MAXN];
int n;bool cmp(int a,int b)
{double s1,s2;s1 = (f[a-1] * 1.0) / t[a-1];s2 = (f[b-1] * 1.0) / t[b-1];return s1 > s2;
}int main()
{int T;scanf("%d%*c",&T);while (T--){scanf("%d",&n);for (int i = 0; i < n; i++){scanf("%d%d",&t[i],&f[i]);num[i] = i + 1;}sort(num,num+n,cmp);printf("%d",num[0]);for (int i = 1; i < n; i++)printf(" %d",num[i]);printf("\n");if (T)printf("\n");}return 0;
}

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

---