首页 > 代码库 > programming-challenges Shoemaker's Problem (110405) 题解
programming-challenges Shoemaker's Problem (110405) 题解
Greedy.
证明:
Let‘s say we have job 1, 2, ..., n, and they have time and fine as t1, f1, t2, f2, ..., tn, fn
and they are in the order of t1/f1 <= t2/f2 <= t3/f3 <= ... <= tn/fn
So this is the objective schedule. Now we change 1 with m (1 < m <= n)
By the original order, we need pay fine as much as: F1 = t1 * (f2 + ... + fn) + t2 * (f3 + ... + fn) + ... + tm * (fm+1 + ... + fn) + R
By the new order, we need pay fine as much as: F2 = tm * (f1 + ... + fm-1 + fm+1 + ... + fn) + t1 * (f2 + ... + fm-1 + fm+1 + ... + fn) + ... + fm-1 * fm+1 + ... + fn) + R
F1 - F2 = (t1 + t2 + ... + tm-1) * fm - (tm * f1 + tm * f2 + ... + tm * fm-1)
As t1 * fm <= tm * f1, t2 * fm <= tm * f2, ..., tm-1 * fm <= tm * fm-1 F1 - F2 <= 0
So the original order is the best order.
#include <iostream> #include <sstream> #include <fstream> #include <string> #include <vector> #include <queue> #include <map> #include <set> #include <stack> #include <assert.h> #include <algorithm> #include <math.h> #include <ctime> #include <functional> #include <string.h> #include <stdio.h> #include <numeric> #include <float.h> using namespace std; /* 4.6.5 */ struct Rec { int time, cost, id; Rec(int atime, int acost, int aid) : time(atime), cost(acost), id(aid) {} }; bool camp(Rec r1, Rec r2) { return r1.time * r2.cost < r1.cost * r2.time; } int main() { int TC = 0; cin >> TC; bool blank = false; for (int tc = 1; tc <= TC; tc++) { int num = 0; cin >> num; vector<Rec> recs; for (int i = 0; i < num; i++) { int time, cost; cin >> time >> cost; recs.push_back(Rec(time, cost, i + 1)); } stable_sort(recs.begin(), recs.end(), camp); if (blank) { cout << endl; } blank = true; for (int i = 0; i < recs.size(); i++) { if (i > 0) cout << " "; cout << recs[i].id; } cout << endl; } return 0; }
programming-challenges Shoemaker's Problem (110405) 题解