首页 > 代码库 > UVA11389-The Bus Driver Problem
UVA11389-The Bus Driver Problem
题目链接
题意:n个司机,n个下午路线和n个夜间的行驶时间。每个司机恰好分配到一个下午路线和一个夜间路线。司机行驶如果超过规定的行驶总时间,每个单位时间要多付给司机r元,求最小要给所有司机的加班费。
思路:贪心,将两个时间段的行驶时间排序,然后依次取最大和最小相加减去规定时间。那么超过的时间将最小,加班费也会最小。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 105; int x[MAXN], y[MAXN]; int n, d, r; int main() { while (scanf("%d%d%d", &n, &d, &r) != EOF) { if (!n && !d && !r) break; for (int i = 0; i < n; i++) scanf("%d", &x[i]); for (int i = 0; i < n; i++) scanf("%d", &y[i]); sort(x, x + n); sort(y, y + n); long long sum = 0; for (int i = 0; i < n; i++) { int temp = x[i] + y[n - 1 - i]; if (temp - d > 0) sum += temp - d; } printf("%lld\n", sum * r); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。