Topic link ：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=82842#problem/D

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

Their thinking ： The meaning of this topic is how to allocate to minimize the overtime pay of bus drivers ,n A driver , In the morning n Paths , Every way is x length , At night n Paths , Each path is X length ,d It means the fixed length of a driver's day ,r It means the price , Every time more than y Length , Then the driver can get y*r Overtime pay .

To minimize overtime pay , You need to sort the length you run in the morning and the length you run in the afternoon , From small to large , One from big to small , In this way, the sum of the two can be minimized , So overtime pay will be kept to a minimum .

Program code ：

 #include <iostream>

#include <algorithm>

#include <cstdio>
using namespace std;

const int m=+;

int a[m],b[m];
bool p(int a,int b)

{ return a>b;}
inline int max(int a,int b)

{

return a>b?a:b;

}
int main()

{int n,d,r,i;

while(cin>>n>>d>>r&&(n!=&&d!=&&r!=))

{

for(i=;i<n;i++)

scanf("%d",&a[i]);
for(i=;i<n;i++)

scanf("%d",&b[i]);

sort(a,a+n);

sort(b,b+n,p);

int sum=;

for(i=;i<n;i++)

sum+=max(,(a[i]+b[i]-d));

cout<<sum*r<<endl;

}

return ;

}

UVA 11389 The Bus Driver Problem More articles about

  1. UVA 11389 The Bus Driver Problem Greedy for water

    Topic link :UVA - 11389 Description of the question : Yes n A driver ,n A morning line and n It's an evening route , Arrange an early and a late route for each driver , So that each morning and evening route belongs to only one driver . If a driver's total driving hours of morning shift and evening shift ...

  2. UVa 11389 - The Bus Driver Problem difficulty :0

    subject https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&a ...

  3. 【 Strategy 】UVa 11389 - The Bus Driver Problem

    The question : There's a driver , Afternoon route , At night, the routes are different n individual . Give each driver just one afternoon route and one evening route . Give the time of each route , If the driver drives more than d, You have to pay overtime d×r. How to allocate routes to minimize overtime pay . Although the code looks ...

  4. UVa 11389 ( greedy ) The Bus Driver Problem

    The question : There's a driver , Afternoon route , At night, the routes are different n individual . Give each driver just one afternoon route and one evening route . Give the time of each route , If the driver drives more than d, You have to pay overtime d×r. How to allocate routes to minimize overtime pay . analysis : sense ...

  5. The Bus Driver Problem

    Topic linking :http://acm.hust.edu.cn/vjudge/contest/view.action?cid=90648#problem/G The question : Assign each driver a day and night route , ...

  6. UVA11389 The Bus Driver Problem

        The question : There's a driver , Afternoon route , At night, the routes are different n individual . Give each driver just one afternoon route and one evening route . Give the time of each route , If the driver drives more than d, You have to pay overtime d*r. How to allocate routes to minimize overtime pay .   greedy ...

  7. UVA 11389( The problem of greed )

    UVA 11389 Time Limit:1000MS     Memory Limit:0KB     64bit IO Format:%lld & %llu Description II  ...

  8. UVA 10245 The Closest Pair Problem Closest point problem Divide and conquer algorithm

    The question , give n Coordinates of points , Find the nearest distance between two points , If it is less than 10000 It outputs INFINITY. Pure violence can go over time , So we have to find another way , Using the divide and conquer algorithm . Recursively sort the points according to their coordinates , It's divided into two parts , The closest distance is not between two blocks ...

  9. UVa 100 - The 3n + 1 problem（ Function loop length ）

    Title source :https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&pa ...

Random recommendation

  1. NPOI Derived data , Format , Lock cell

    The code includes : 1: Export multiple sheet    2: Format cell   3: merge cell   4: Dropdown options   5: Enter the number limit   6: Lock cell static void Main(string[] ar ...

  2. Use Gson Exclude specific fields

    http://blog.csdn.net/hknock/article/details/51037564

  3. 【 turn 】 About LWF—— Linear workflow

    1. What is? LWF? LWF Full name Linear Workflow, Linear workflow .“ workflow ” It can be understood as a workflow here .LWF It's a way of adjusting the image Gamma value , So that the image can be displayed linearly . ...

  4. CentOS 6.5- Network connection is not turned on by default ： Turn on the Internet connection

    vi  /etc/sysconfig/network-scripts/ifcfg-eth0 Modify the network , prohibit IP6 Turn on , Disable self starting service chkconfig

  5. Sql Server Derived table structure Excel

    SELECT Table name Then D.name Else '' End, Table description Then isnull(F.value,'') Else '' End, Field ordinal number = A.colorder, Field name = ...

  6. redis Queue cache + mysql Bulk warehousing + php Offline Integration

    Problem analysis reflection : In the evolution process of application website architecture , It is the best choice to apply the latest framework and tool technology : however , If we can put forward a simple and reliable solution based on the existing framework , Maybe it's an attempt to improve yourself . solve : Question 1 : It's better to log in ...

  7. EF In singleton mode and C/S Mode development , If an exception occurs after operating the data object , We have to deal with the aftermath .

    try{ Delete or modify }catch { _DBContext.Refresh(RefreshMode.StoreWins, entity); }

  8. airdrop-ng/aircrack-ng

    Looking for a long time , Just found the installation method and use , This is to record that the first thing to do is to install airodump-ng 1.2 beat The premise for me to install that version is airodump mon0 It's ready to try . Not today airodump-ng Installed , ...

  9. 【leetcode81】Product of Array Except Self

    Title Description : Given a length of n Array of integers for Array[], Output an array of equal length result[], This output array , Corresponding position i Yes, except for Array[i] outside , The product of all the other elements for example : given [1,2,3,4 ...

  10. Teacher Yang's class _Java Under the core technology of the console simulation microblog user registration case

    Background of case design : Write a Sina Weibo user registration program , Required HashSet Set implementation .  Suppose that when a user enters a user name . password . Confirm the password . Birthday ( Input format yyyy-mm-dd To be right ). Phone number ( The length of the mobile phone is 11 position , and ...