题目
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2384
题意
n个司机,n个白天路线,n个晚上路线,要求每个司机一个白天一个晚上路线。设司机2个路线所需时间超出d部分为加班工时,需额外给r元/h。问总加班支出最小是多少。
思路
明显,要分的均匀。一个数组大到小,一个数组小到大,依次序组合即可
代码
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <cstring> using namespace std; const int MAXN = 1e3 + 3; typedef pair<int, int> Pair; int a[MAXN]; int b[MAXN]; int n, d, r; int main() { int T; //scanf("%d", &T); freopen("C:\Users\Iris\source\repos\ACM\ACM\input.txt", "r", stdin); //freopen("C:\Users\Iris\source\repos\ACM\ACM\output.txt", "w", stdout); for (int ti = 1; scanf("%d%d%d", &n, &d, &r) == 3 && n; ti++) { for (int i = 0; i < n; i++) { scanf("%d", a + i); } sort(a, a + n); for (int i = 0; i < n; i++) { scanf("%d", b + i); } sort(b, b + n); int ans = 0; for (int i = 0; i < n; i++) { ans += max(0, a[i] + b[n - 1 - i] - d); } printf("%d ", ans * r); } return 0; }