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
- 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 ...
- UVa 11389 - The Bus Driver Problem difficulty :0
subject https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&a ...
- 【 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 ...
- 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 ...
- 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 , ...
- 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 ...
- UVA 11389( The problem of greed )
UVA 11389 Time Limit:1000MS Memory Limit:0KB 64bit IO Format:%lld & %llu Description II ...
- 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 ...
- 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
- 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 ...
- Use Gson Exclude specific fields
http://blog.csdn.net/hknock/article/details/51037564
- 【 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 . ...
- 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
- 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 = ...
- 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 ...
- 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); }
- 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 , ...
- 【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 ...
- 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 ...