第三题:T3工作安排
标签:结构体排序、算法>贪心算法
题意:有
n
n
n份任务。完成第
i
i
i份任务需要
t
i
t_i
ti的时间,在这份任务没有完成之前,每一个单位时间会收到
f
i
f_i
fi单位的罚款。求以什么顺序安排这些任务,才能使罚款总额最少?
数据范围:
1
<
=
n
,
t
i
,
f
i
<
=
200
,
000
1<=n,\ t_i,\ f_i<=200,000
1<=n, ti, fi<=200,000
题解:这道题有点像 洛谷P1012 [NOIP1998 提高组] 拼数 这道题。
本质来说就是进行结构体排序的时候,比较的内容不再是简单的两个对象(比如代码里面
x
x
x和
y
y
y)各自的数据内容,而是说需要两者结合进行比较。
像这道题,有两份任务
x
x
x和
y
y
y,我到底是把
x
x
x先完成还是先把
y
y
y先完成,我们需要考虑到先完成
x
x
x任务,那对于
y
y
y来说就得等
x
.
t
x.t
x.t的时间,那罚款就是
x
.
t
∗
y
.
f
x.t*y.f
x.t∗y.f;同理先完成
y
y
y任务对于
x
x
x来说的罚款是
y
.
t
∗
x
.
f
y.t*x.f
y.t∗x.f,我们需要贪心的考虑哪种所带来的罚款会少点。
还有个细节就是等待时间应该是累积的,对于第
i
i
i项任务没完成之前,需要收到罚款的时间是前
i
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;
}