这道题是乙组里比较新奇的一题,本来一眼看下来不会,后来蒙了个按照单位时间内收到罚款排序居然对了,十分意外。
简单的证明一下:
假设有两个工作,时间分别为 $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; }
标签:YACS,Node,int,题解,乙组,times,n1,n2 From: https://www.cnblogs.com/Xy-top/p/17645436.html