UVA 11389 The Buss Driver Problem
5964 ワード
テーマリンク:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=82842#problem/D
In city there re re re re n bus drivers.Also there re re n moning bus routes&n afternoon bus routes with various lengths.Each driver is assigned one moning route&one oning route.For any driver，ifs total dayhe has to be paid overtime for eve hour after the first d hors at flat Tatara/hour.Your task is to assign moning route&one eving route to each bus driver so that the total overtime me me me me me me me me me me me minthauty.parity。
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 moring route s given in meters.Simillarly the third line has n space separated inters denoting the prong route length.The lengths.The leiness。
Output
For each test case，print the minimum possible overtime mount that the authority must pay.
コンストラクション
を選択します。 1≦n≦100- 1≦d≦10000- 1≦r≦5
Sample Input
Output for Sample Input
2 20 5 10 15 2 20 5 10 10 0 0 0
50
この問題の意味は、バスの運転手に残業代を最小にする方法を割り当てることです。n人の運転手は朝n本の道を歩いて、それぞれの道はx長さで、夜n本の道を歩いて、各ルートはX長さです。dは運転手が一日固定して走る長さを表しています。r表の価格はy個の長さを超えると、運転手はy*rの残業代をもらえます。
残業代を最低にするには、午前中の走りの長さと午後の走りの長さをそれぞれ並べて、小さい時から大きい時まで、小さい時から小さい時まで二つの和を最小にできるので、残業代も最小限に抑えられます。
プログラムコード:
In city there re re re re n bus drivers.Also there re re n moning bus routes&n afternoon bus routes with various lengths.Each driver is assigned one moning route&one oning route.For any driver，ifs total dayhe has to be paid overtime for eve hour after the first d hors at flat Tatara/hour.Your task is to assign moning route&one eving route to each bus driver so that the total overtime me me me me me me me me me me me minthauty.parity。
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 moring route s given in meters.Simillarly the third line has n space separated inters denoting the prong route length.The lengths.The leiness。
Output
For each test case，print the minimum possible overtime mount that the authority must pay.
コンストラクション
を選択します。 1≦n≦100- 1≦d≦10000- 1≦r≦5
Sample Input
Output for Sample Input
2 20 5 10 15 2 20 5 10 10 0 0 0
50
この問題の意味は、バスの運転手に残業代を最小にする方法を割り当てることです。n人の運転手は朝n本の道を歩いて、それぞれの道はx長さで、夜n本の道を歩いて、各ルートはX長さです。dは運転手が一日固定して走る長さを表しています。r表の価格はy個の長さを超えると、運転手はy*rの残業代をもらえます。
残業代を最低にするには、午前中の走りの長さと午後の走りの長さをそれぞれ並べて、小さい時から大きい時まで、小さい時から小さい時まで二つの和を最小にできるので、残業代も最小限に抑えられます。
プログラムコード:
1 #include <iostream>
2 #include <algorithm>
3 #include <cstdio>
4
5 using namespace std;
6 const int m=100+5;
7 int a[m],b[m];
8
9 bool p(int a,int b)
10 { return a>b;}
11
12 inline int max(int a,int b)
13 {
14 return a>b?a:b;
15 }
16
17 int main()
18 {int n,d,r,i;
19 while(cin>>n>>d>>r&&(n!=0&&d!=0&&r!=0))
20 {
21 for(i=0;i<n;i++)
22 scanf("%d",&a[i]);
23
24 for(i=0;i<n;i++)
25 scanf("%d",&b[i]);
26 sort(a,a+n);
27 sort(b,b+n,p);
28 int sum=0;
29 for(i=0;i<n;i++)
30 sum+=max(0,(a[i]+b[i]-d));
31 cout<<sum*r<<endl;
32 }
33 return 0;
34 }