UVa 11389 (贪心) The Bus Driver Problem

时间:2021-07-11 15:24:28

题意:

有司机,下午路线,晚上路线各n个。给每个司机恰好分配一个下午路线和晚上路线。

给出行驶每条路线的时间,如果司机开车时间超过d,则要付加班费d×r。

问如何分配路线才能使加班费最少。

分析:

感觉上是要先排序,然后时间最长的路线配另一个时间最短的路线。

这里就严格证明一下这样贪心的正确性。

以两条路线为例,其他情况都是类似的:

不妨假设:A1≥A2,B1≤B2,水平线代表d

情况一:

UVa 11389 (贪心) The Bus Driver Problem

如图,司机一要付加班费,司机二不用,如果我们将B1、B2交换:

因为B1≤B2,所以付给司机一的加班费不会更少,而司机二的开车时间不会增加,所以也不用付加班费。

因此,交换以后总加班费不会减少。

情况二:

UVa 11389 (贪心) The Bus Driver Problem

两位司机都要付加班费,则超出时间为(A1 + B1 - d) + (A2 + B2 - d)

如果交换B1、B2:

  • 如果两位司机还是超出正常工作时间,那么总的加班费用不变
  • 如果交换后司机一加班,司机二不加班,则超出时间为(A1 + B2 - d)。用这个减去原来的时间:(A1 + B2 - d) - (A1 + B1 - d) - (A2 + B2 - d) = d - (B1 + A2),因为此时司机二不加班,所以原式≥0,所以总超出时间不会减少

情况三:

UVa 11389 (贪心) The Bus Driver Problem

司机一不付加班费,司机二要付。此时加班时长为(A2 + B2 - d)

如果交换B1、B2:

由B1≤B2,A1≥A2,所以B2加到A1上时,司机一一定会加班,司机二一定不会加班,此时加班时长为(A1 + B2 - d),减去原来的时间为(A1 + B2 - d) - (A2 + B2 - d) = (A1 - A2) ≥ 0

所以总加班时间不会减少。

好了,所有的情况应该都分析完了。

 #include <cstdio>
#include <algorithm>
using namespace std; const int maxn = + ;
int a[maxn], b[maxn]; int cmp(const int& a, const int& b)
{
return a > b;
} int main()
{
freopen("11386in.txt", "r", stdin);
int n, d, r;
while(scanf("%d%d%d", &n, &d, &r) == && n)
{
for(int i = ; i < n; ++i) scanf("%d", &a[i]);
for(int i = ; i < n; ++i) scanf("%d", &b[i]);
sort(a, a + n);
sort(b, b + n, cmp); int ans = ;
for(int i = ; i < n; ++i)
ans += max(a[i] + b[i] - d, ) * r; printf("%d\n", ans);
} return ;
}

代码君

UVa 11389 (贪心) The Bus Driver Problem的更多相关文章

  1. UVA 11389&lpar;贪心问题&rpar;

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

  2. 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 ...

  3. UVA 11389 The Bus Driver Problem 贪心水题

    题目链接:UVA - 11389 题意描述:有n个司机,n个早班路线和n个晚班路线,给每个司机安排一个早班路线和一个晚班路线,使得每个早班路线和晚班路线只属于一个司机.如果一个司机早班和晚班总的驾驶时 ...

  4. UVa 11389 - The Bus Driver Problem 难度&colon;0

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

  5. 【策略】UVa 11389 - The Bus Driver Problem

    题意: 有司机,下午路线,晚上路线各n个.给每个司机恰好分配一个下午路线和晚上路线.给出行驶每条路线的时间,如果司机开车时间超过d,则要付加班费d×r.问如何分配路线才能使加班费最少. 虽然代码看起来 ...

  6. The Bus Driver Problem

    题目连接:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=90648#problem/G 题意: 给每位司机分配一个白天和晚上的行车路线, ...

  7. UVA11389 The Bus Driver Problem

        题意:有司机,下午路线,晚上路线各n个.给每个司机恰好分配一个下午路线和晚上路线.给出行驶每条路线的时间,如果司机开车时间超过d,则要付加班费d*r.问如何分配路线才能使加班费最少.   贪心 ...

  8. UVA 100 The 3&ast;n&plus;1 problem

      UVA 100 The 3*n+1 problem. 解题思路:对给定的边界m,n(m<n&&0<m,n<1 000 000);求X(m-1<X<n+ ...

  9. 01&lowbar;传说中的车&lpar;Fabled Rooks UVa 11134 贪心问题&rpar;

    问题来源:刘汝佳<算法竞赛入门经典--训练指南> P81: 问题描述:你的任务是在n*n(1<=n<=5000)的棋盘上放n辆车,使得任意两辆车不相互攻击,且第i辆车在一个给定 ...

随机推荐

  1. supermap iobect &period;net 7&period;1&period;2 图例的拆分

    LayoutSelection objLytSelect = m_MapLayoutControl.MapLayout.Selection;//.Selection; //LayoutSelectio ...

  2. redis 集群创建常见几个问题

    Redis配置集群遇到问题及解决方法   配置完所有主节点后,报" ERR Invalid node address specified" 由于Redis-trib.rb 对域名或 ...

  3. 移动互联网公司如何将BPM流程管理变身移动化?

    背景介绍 OPPO是广东欧珀移动通信有限公司的旗下品牌,成立于2004年,是一家全球性的智能终端和移动互联网公司,致力于为客户提供最先进和最精致的智能手机.高端影音设备和移动互联网产品与服务,业务覆盖 ...

  4. python---difflib

    文件内容差异对比 difflib为python的标准库模块,无需安装.作用时对比文本之间的差异.并且支持输出可读性比较强的HTML文档,与LInux下的diff 命令相似.在版本控制方面非常有用. # ...

  5. CSS备忘-1

    CSS 可以通过以下方式添加到HTML中: 内联样式- 在HTML元素中使用"style" 属性 内部样式表 -在HTML文档头部 <head> 区域使用<sty ...

  6. vs2010在进行数据架构比较时报&&num;39&semi;text lines should not be null&&num;39&semi;错误

    通过VS2010进行服务器数据库和本地数据库比较架构(都是sql server 2008 R2)时,弹出“text lines should be not null”错误,如下图: 解决方法:在Vis ...

  7. 加载loading对话框的功能&lpar;不退出沉浸式效果&rpar;

    上一篇基于修改系统源码的前提下,实现了完全的沉浸式体验效果.可参考这篇 戳这 一.自定义Dialog 在沉浸式效果下,当界面弹出对话框时,对话框将获取到焦点,这将导致界面退出沉浸式效果,那么是不是能通 ...

  8. 【转】大型Vuex项目 &comma;使用module后, 如何调用其他模块的 属性值和方法

    Vuex 允许我们把 store 分 module(模块).每一个模块包含各自的状态.mutation.action 和 getter. 那么问题来了, 模块化+命名空间之后, 数据都是相对独立的, ...

  9. C&plus;&plus;并发编程实战---阅读笔记

    1. 当把函数对象传入到线程构造函数中时,需要避免“最令人头痛的语法解析”.如果传递了一个临时变量,而不是一个命名的变量:C++编译器会将其解析为函数声明,而不是类型对象的定义. 例如: class ...

  10. Python - 列表与字符串的互相转换

    题目:请将text字符串中的数字取出,并输出成一个新的字符串 text = "aAsmr3 idd4bgs7Dlsf 9eAF" b = list(text) new_list = ...