首页 > 代码库 > UVa 11389 - The Bus Driver Problem
UVa 11389 - The Bus Driver Problem
题目:有n个上午的任务和下午的任务,分配给司机,如果工作总时间超过d,超过的部分要给加班费;
现在让你安排任务,问最小的加班分花费。
分析:贪心。将两个任务分别按递增和递减序排序,每个对应边号的一组即可。
设序列中的两组配对的元素为m1,a1,m2,a2 且 m1≤m2,a1≤a2;
则配对方式<m1,a2>,<m2,a1>优于<m1,a1>,<m2,a2>(浪费的可能更少)。
说明:(⊙_⊙)。
#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> using namespace std; int morni[101]; int after[101]; int cmp1(int a, int b){ return a < b; } int cmp2(int a, int b){ return a > b; } int main() { int n,d,r; while (~scanf("%d%d%d",&n,&d,&r) && n) { for (int i = 0 ; i < n ; ++ i) scanf("%d",&morni[i]); for (int i = 0 ; i < n ; ++ i) scanf("%d",&after[i]); sort(morni, morni+n, cmp1); sort(after, after+n, cmp2); int sum = 0; for (int i = 0 ; i < n ; ++ i) if (morni[i]+after[i] > d) sum += r*(morni[i]+after[i]-d); printf("%d\n",sum); } return 0; }
UVa 11389 - The Bus Driver Problem
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。