UVA 11389 The Bus Driver Problem
题目链接: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 |
解题思路:这个题目的意思是怎样分配使公交车司机加班费减至最少,n个司机,早上走n条路径,每个路经是x长度,晚上走n条路径,每个路径是X长度,d表示一个司机一天固定要跑的长度,r表示价格,每超过y个长度,则司机可获得y*r的加班费。
要使加班费减到最低,则需要对上午所跑长度和下午所跑长度分别进行排序,一个从小到大,一个从大到小,这样二者之和均能降到最小,因此加班费也会控制到最小。
程序代码 :
#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 ;
}
最新文章
- iOS 动态下载系统提供的中文字体
- SQL Server 2012 数据库笔记
- 学习C++.Primer.Plus 8 函数探幽
- 5个最优秀的Java和C#代码转换工具
- 在iOS虚拟机上使CLPlacemark获取中文信息
- 不用标准库实现memmove,借助一个缓冲区temp,即使src和dest所指的内存有重叠也能正确拷贝
- ES5 object的新函数
- 简单RTP发送类c++实现
- css3实现三角形,聊天背景气泡,心形等形状
- USACO dualpal
- RobotFramework自动化测试框架-移动手机自动化测试Clear Text关键字的使用
- 解决firefox不支持-webkit-line-clamp属性
- matplotlib-形状
- OGG-01028 Incompatible Record解决办法
- linux下修改/etc/profile文件
- bzoj 2124 等差子序列 (线段树维护hash)
- git使用多个SSH公钥信息
- Eclipse导入web项目发布项目时报Tomcat version 7.0 only supports J2EE 1.2, 1.3, 1.4, and Java EE 5 and 6 Web错误解决方案
- sql复制表结构,复制表内容语句
- IE8引入JavaScript
热门文章
- jq實現網頁個性title
- 错误记录--关于foreach,集合已修改;可能无法执行枚举操作
- canvas sprite动画 简单封装
- 【转】数据库分页Java实现
- Linq101-Aggregate
- HTML 学习笔记
- `~!$^*()[]{}\|;:&#39;";,<;>;/?在英文怎么读?
- 访问快递100的rest的请求
- uva 11529 Strange Tax Calculation (几何+计数)
- restrict和volatile的作用