上海计算机学会 2023年6月月赛 乙组T3 工作安排（结构体排序、贪心算法）

第三题：T3工作安排

标签：结构体排序、贪心算法

题意：有$n$份任务。完成第$i$份任务需要$t_i$的时间，在这份任务没有完成之前，每一个单位时间会收到$f_i$单位的罚款。求以什么顺序安排这些任务，才能使罚款总额最少？

数据范围：$1<=n,t_i,f_i<=200,000$

题解：这道题有点像 洛谷P1012 [NOIP1998 提高组] 拼数 这道题。
本质来说就是进行结构体排序的时候，比较的内容不再是简单的两个对象（比如代码里面$x$和$y$）各自的数据内容，而是说需要两者结合进行比较。

像这道题，有两份任务$x$和$y$，我到底是把$x$先完成还是先把$y$先完成，我们需要考虑到先完成$x$任务，那对于$y$来说就得等$x.t$的时间，那罚款就是$x.t\ast y.f$；同理先完成$y$任务对于$x$来说的罚款是$y.t\ast x.f$，我们需要贪心的考虑哪种所带来的罚款会少点。

还有个细节就是等待时间应该是累积的，对于第$i$项任务没完成之前，需要收到罚款的时间是前$i$项任务时间之和。

代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
struct node {
	ll t, f;
}p[200005];

bool cmp(node x, node y) {
	return x.t * y.f < y.t * x.f;
}

int main() {
	ll n, sum = 0, ans = 0;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> p[i].t >> p[i].f;
	}
	sort(p + 1, p + 1 + n, cmp);
	for (int i = 1; i <= n; i++) {
		sum += p[i].t;
		ans += p[i].f * sum;
	}
	  cout << ans << endl;
    return 0;
}