uva - 10026 - Shoemaker's Problem（贪心）

题意：鞋匠一口气接到了不少生意，但是做鞋需要时间，鞋匠只能一双一双地做，根据协议每笔生意如果拖延了要罚钱。给出每笔生意需要的天数和每天的罚钱数，求出最小罚钱的排列顺序。只要按罚款/天数去从大到小排序，如果比例一样就按序号排序（要求字典序）。

方法：贪心。

贪心发证明：（转自http://blog.csdn.net/hcbbt/article/details/10313063 ）不妨拿相邻的两个事件a、b来说明一下。由于a、b之后的事件是固定的，所以我们无论排成ab还是排成ba后面部分的损失都是固定的，那么损失的差别主要来源于究竟是排成ab还是排b成a。排ab的损失为ta*fb，排ba的损失为tb*fa，那么如果ta*fb<tb*fa，我们就排成ab，这样可以得到fa/ta>fb/tb，推而广之，就得到了我们的贪心策略。

代码：

#include <iostream>
#include <iomanip>
#include <string>
#include <cstring>
#include <cstdio>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>

using namespace std;

#define MAX 1000+10
struct Work
{
	double day;
	double fine;
};

struct Per
{
	double day_fine;
	int s;
};

Work work[MAX];
int n;
Per per[MAX];

void Input()
{
	int i = 0;
	cin >> n;
	for (i = 0; i < n; i++)
		cin >> work[i].day >> work[i].fine;
}

void Handle()
{
	int i = 0;
	for (i = 0; i < n; i++)
	{
		per[i].day_fine = work[i].fine / work[i].day;
		per[i].s = i+1;
	}
}

int cmp(const void *a, const void *b)
{
	if ((*(Per *)a).day_fine != (*(Per *)b).day_fine)
		return (*(Per *)b).day_fine > (*(Per *)a).day_fine?1:-1;
	else
		return (*(Per *)a).s - (*(Per *)b).s;
}

int main()
{
#ifdef Local
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
#endif
	int i = 0, t = 0;
	cin >> t;
	while (t--)
	{
		Input();
		Handle();
		qsort(per, n, sizeof(per[0]), cmp);
		for (i = 0; i < n; i++)
		{
			if (i != n-1)
				cout << per[i].s << " " ;
			else
				cout << per[i].s ;
		}
		cout << endl;
		if (t)
			cout << endl;
	}
}

1、PE因为两个数字之间有空格，最后一个数字木有空格。。

是因为手术问题吗，没有状态，最近的题目都要去百度，反正以前也没状态。。

uva - 10026 - Shoemaker's Problem（贪心）

原文：http://blog.csdn.net/u013545222/article/details/18973605