UVA 10026 Shoemaker's Problem 鞋匠的难题 贪心+排序

题意:鞋匠一口气接到了不少生意,但是做鞋需要时间,鞋匠只能一双一双地做,根据协议每笔生意如果拖延了要罚钱。

给出每笔生意需要的天数和每天的罚钱数,求出最小罚钱的排列顺序。

只要按罚款/天数去从大到小排序,如果比例一样就按序号排序(要求字典序)。

解释我就不献丑了,附上Staginner大神的证明:

对于为什么贪心策略是这个样子的,我们不妨拿相邻的两个事件a、b来说明一下。由于a、b之后的事件是固定的,所以我们无论排成ab还是排成ba后面部分的损失都是固定的,那么损失的差别主要来源于究竟是排成ab还是排b成a。排ab的损失为ta*fb,排ba的损失为tb*fa,那么如果ta*fb<tb*fa,我们就排成ab,这样可以得到fa/ta>fb/tb,推而广之,就得到了我们的贪心策略。

代码:

 /*
* Author: illuz <iilluzen@gmail.com>
* Blog: http://blog.csdn.net/hcbbt
* File: uva10026.cpp
* Lauguage: C/C++
* Create Date: 2013-08-25 20:11:52
* Descripton: UVA 10026 Shoemaker's Problem, sort + struct
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <list>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <utility>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repu(i, a, b) for (int i = (a); i < (b); i++)
#define repf(i, a, b) for (int i = (a); i <= (b); i++)
#define repd(i, a, b) for (int i = (a); i >= (b); i--)
#define swap(a, b) {int t = a; a = b; b = t;}
#define mc(a) memset(a, 0, sizeof(a))
#define ms(a, i) memset(a, i, sizeof(a))
#define sqr(x) ((x) * (x))
#define FI(i, x) for (typeof((x).begin()) i = (x).begin(); i != (x).end(); i++)
typedef long long LL;
typedef unsigned long long ULL; /****** TEMPLATE ENDS ******/ const int MAXN = 1002;
struct Deal {
int no;
double pri;
int day;
friend bool operator < (const Deal& a, const Deal& b) {
if (a.pri != b.pri) return a.pri > b.pri;
else return a.no < b.no;
}
} d[MAXN]; int main() {
int t, n, m;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
rep(i, n) {
d[i].no = i + 1;
scanf("%d%d", &d[i].day, &m);
d[i].pri = (double)m / (double)d[i].day;
};
sort(d, d + n);
printf("%d", d[0].no);
repu(i, 1, n) printf(" %d", d[i].no);
printf("\n");
if (t) printf("\n");
}
return 0;
}
上一篇:SQL Server 数据库编程技巧


下一篇:[py]编码-强力理解版