| I I U C O N L I N E C O N T E S T 2 0 0 8 |
|
| Problem E: The Bus Driver Problem |
|
| Input: standard input Output: standard output |
|
|
|
|
| In a city there are n bus drivers. Also there are n morning bus routes & n afternoon bus routes with various lengths. Each driver is assigned one morning route & one evening route. For any driver, if his total route length for a day exceeds d, he has to be paid overtime for every hour after the first d hours at a flat r taka / hour. Your task is to assign one morning route & one evening route to each bus driver so that the total overtime amount that the authority has to pay is minimized.
|
|
| Input |
|
| The first line of each test case has three integers n, d and r, as described above. In the second line, there are n space separated integers which are the lengths of the morning routes given in meters. Similarly the third line has n space separated integers denoting the evening route lengths. The lengths are positive integers less than or equal to 10000. The end of input is denoted by a case with three 0 s.
|
|
| Output |
|
| For each test case, print the minimum possible overtime amount that the authority must pay.
|
|
| Constraints |
|
| - 1 ≤ n ≤ 100 - 1 ≤ d ≤ 10000 - 1 ≤ r ≤ 5
|
|
| Sample Input |
Output for Sample Input |
| 2 20 5 10 15 10 15 2 20 5 10 10 10 10 0 0 0 |
50 0 |
| |
|
思路:贪心。每个BUS选一条最短白天路线和一条最长晚上路线即可。因为对于最小白天路线，选最大的夜晚路线使得d最大，而且如果这样选都会超过d，那么其他的路线都会超过，那么选这个是最合适的。
代码：
#include#include using namespace std; const int N = 105; int n, d, r, af[N], ni[N]; bool cmp(int a, int b) { return a > b; } void init() { for (int i = 0; i < n; i ++) scanf("%d", &af[i]); for (int i = 0; i < n; i ++) scanf("%d", &ni[i]); } int solve() { int ans = 0; sort(af, af + n); sort(ni, ni + n, cmp); for (int i = 0; i < n; i ++) { if (af[i] + ni[i] > d) { ans += (af[i] + ni[i] - d) * r; } } return ans; } int main() { while (~scanf("%d%d%d", &n, &d, &r) && n + d + r) { init(); printf("%d\n", solve()); } return 0; }