11389 - The Bus Driver Problem
Time limit: 1.000 seconds
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2384
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
查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/
Sample Input
2 20 5
10 15
10 15
2 20 5
10 10
10 10
0 0 0
Output for Sample Input
50
0
一增一减必然是最优的，可以通过交换两个元素的位置来反证。
完整代码：
/*0.016s*/
#include<cstdio>
#include<algorithm>
#include<functional>
using namespace std;
int a[105], b[105];
int main()
{
int n, d, r, sum, temp;
while (scanf("%d%d%d", &n, &d, &r), n)
{
for (int i = 0; i < n; ++i)
scanf("%d", &a[i]);
for (int i = 0; i < n; ++i)
scanf("%d", &b[i]);
sort(a, a + n);
sort(b, b + n, greater<int>());
sum = 0;
for (int i = 0; i < n; ++i)
{
temp = a[i] + b[i] - d;
if (temp > 0) sum += temp;
}
printf("%d\n", sum * r);
}
return 0;
}
作者：csdn synapse7
以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索int
， include
， for
， 贪心
， d bus
， route
， Sum Problem
The
bus driver、busdriver、bus driver 1.5、bus driver 1.5下载、virtual bus driver，以便于您获取更多的相关知识。