算法竞赛进阶指南-0x08-Task
题目链接
题目大意：一工厂有n台机器，第i台机器每天最长可以工作xi小时，最多可以处理难度系数为yi的订单。一天工厂收到了m个订单，第i个订单的处理时间为xi，难度系数为yi，完成该订单所能得到的收入是
xi×500+yi×2
问这一天工厂能完成的最多订单数，以及在完成最多订单数的情况下所能取得的最大收入。
连续假了两发思路。第一发是将机器的最大工作时间从大到小排序，然后让每台机器找到难度可接受的范围内所能取得的时间最大的订单。但是碰到下面这样的数据就不行了。
1
2
3
4
5
6
| 3 2
17 5
14 2
22 6
7 4
3 6
|
第二发是将机器的最大工作时间从小到大排序，然后让每台机器找到难度尽可能大，且在这个基础上时间尽可能大的订单。但碰到这样的数据又不行了。
1
2
3
4
5
6
| 2 3
10 0
13 5
7 2
12 3
10 5
|
想破了头都想不出合适的方法，看了看标程。标程是将订单的时间从大到小排序，然后每个订单选时间允许的情况下难度系数尽可能小的机器…之所以这么做，是因为难度之间的差最大只有100，相同时间下，最高难度跟最低难度之间赚的钱只差200，而相同难度下，时间差1，赚的钱就差了500了。所以在订单数最多的情况下，应尽可能地保证所需时间大的订单被处理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <bits/stdc++.h>
using namespace std;
pair<long long, long long> p[100005];
int main()
{
int n, m, i, x, y;
while (~scanf("%d%d", &n, &m))
{
priority_queue<pair<long long, long long> > tsk;
pair<long long, long long> p;
priority_queue<long long> mch[105];
for (i = 1; i <= n; i++)
{
scanf("%d%d", &x, &y);
mch[y].push(x);
}
for (i = 1; i <= m; i++)
{
scanf("%lld%lld", &p.first, &p.second);
tsk.push(p);
}
long long res = 0, sum = 0;
while (!tsk.empty())
{
p = tsk.top();
tsk.pop();
for (i = p.second; i <= 100; i++)
{
if (!mch[i].empty() && mch[i].top() >= p.first)
{
mch[i].pop();
sum++;
res += p.first * 500 + p.second * 2;
break;
}
}
}
printf("%lld %lld\n", sum, res);
}
return 0;
}
|