YACS 2023年6月月赛 乙组 T3 工作安排 题解
题目链接
这道题是乙组里比较新奇的一题，本来一眼看下来不会，后来蒙了个按照单位时间内收到罚款排序居然对了，十分意外。
简单的证明一下：
假设有两个工作，时间分别为 $t_1$ $f_1$ $t_2$ $f_2$，假设把第一个放在前面更优，前面的罚款不变。
则有 $t_1\times f_1+(t_1+t_2)\times f_2<t_2\times f_2+(t_1+t_2)\times f_1$。
化简后可得 $t_1\times f_2<t_2\times f_1$。
进一步移项可得 $\frac{t_1}{f_1}<\frac{t_2}{f_2}$，然后排序即可。
代码很短：
#include <iostream> #include <algorithm> #define int long long using namespace std; int n, s, ans; struct Node {int x, y;}a[200005]; bool cmp (Node n1, Node n2) {return n1.y * n2.x > n2.y * n1.x;} signed main () { cin >> n; for (int i = 1; i <= n; i ++) cin >> a[i].x >> a[i].y; sort (a + 1, a + n + 1, cmp); for (int i = 1; i <= n; i ++) { s += a[i].x; ans += s * a[i].y; } cout << ans; return 0; }