IIUCONLINE
CONTEST2008
|
Problem E: The Bus Driver Problem
|
Input: standard input
Output: standard output
|
|
In a city there arenbus drivers. Also there arenmorning bus routes &nafternoon 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 exceedsd, he has to be paid overtime for every hour after the firstdhours at a flatrtaka / 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 integersn,dandr, as described above. In the second line, there arenspace separated integers which are the lengths of the morning routes given
in meters. Similarly the third line hasnspace 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
|
|
|
题意:n辆BUS,有n条白天路线,n条夜晚路线,距离上限d,超过上限每小时加工资r。现在求怎么去分配使得给加班工资最少。
思路:贪心。每个BUS选一条最短白天路线和一条最长晚上路线即可。因为对于最小白天路线,选最大的夜晚路线使得d最大,而且如果这样选都会超过d,那么其他的路线都会超过,那么选这个是最合适的。
代码:
#include <stdio.h>
#include <algorithm>
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;
}
分享到:
相关推荐
判断输入字符串是否为镜像或回文串。 来源于UVaOJ - 401. 水题。
Uva 100 ,问题是The 3n+1 probelm ,可以ac的代码
开源项目-codingsince1985-UVa#uva-online-judge-solutions-in-golang.zip,两年来每天都在解决一个uva在线裁判问题,算起来…
uva705 Slash Maze 的代码,在UVaOJ上通过
PDF试题
UVA 100题答案
uva532 Dungeon Master的源代码,并且AC了
Algorithm-UVA-Solutions-in-Python.zip,python 3中各种uva(acm)问题的解决方案。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
这是UVA133 TheDoleQueue救济金发放问题,经典的算法问题。初学算法的人要对这种算法非常熟悉并且能熟练运用。