[Codeforces Round 193 (Div. 2)] C. Students Revenge

非常厉害的一题贪心题。Orz Lazycal。题目大意是：

  • 有 n 条命令，你要从中选出恰好 p 条命令作为候选命令，然后主席会从中选出恰好 k 条命令执行。
  • 每条命令有两个属性：如果执行那么主席的会变白的头发数 Ai，如果不执行那么委员会的不满意指数 Bi 。
  • 对于主席来说，她首先希望不执行的那 p-k 条给委员会带来的不满意指数最小，然后希望那 k 条命令使自己变白的头发最少。
  • 对于你来说（，由于某些原因），你首先希望主席变白的头发最多，然后希望委员会的不满意指数最大。
  • 现在让你求应该选出哪 p 条命令。

分析一下：首先我们不能很high地直接把 Ai 最大的 k 条选出来，因为很有可能剩下的 p-k 条会使得我们取不到最好情况。实质上，我们和主席的价值观不一样，所以会导致直接取最大失败。我们应该设下挖坑让主席跳下去，我们可以先确定可被选到的最凶残的 k 条，让主席不得不选它们，然后再考虑剩下的 p-k 使得委员会不满意指数最大，同时又不影响主席选择那 k 条。我们不妨从主席的角度考虑。

我们把 n 条命令按照主席的意愿 (-Bi, +Ai) 排序，那么主席就会按照排序后的顺序从前到后选取命令来执行。注意到最后的 p-k 条命令我们是没必要选出来的，因为选了这其中的任意一条，都会被主席放在最后（很有可能不执行），然后就算这几条的 Ai 再大，也发挥不了用处。

好了，我们知道了主席的顺序，现在我们想让主席的头发白掉，所以我们把前 n-(p-k) 条命令按照我们的意愿 (-Ai) 稳定排序。选出前 k 条，这就是主席必选的 k 条。

现在我们考虑选出剩下的 p-k 条，这 p-k 条不能影响到前面 k 条的选取。因此我们可以先找到 k 条必选命令中，主席最后执行的命令是哪条（也就是第一次排序的结果中最靠后的），然后从这条后面选取。显然，在保证不会影响 k 条的情况下，我们按我们的意愿 (-Bi) 排序选出剩下的 p-k 条即可！

代码

Codeforces 332 C 
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

#include <cstdio>
#include <algorithm>
using std::sort;

const int MAXN = 100000;
struct Order { int hair, anger, index, _i; };
Order a[MAXN], b[MAXN];
int n, p, k;
int main()
{
  scanf("%d%d%d", &n, &p, &k);
  for (int i = 0; i < n; ++i)
  {
    scanf("%d%d", &a[i].hair, &a[i].anger);
    a[i].index = i+1;
  }
  sort(a, a+n, [](const Order& lhs, const Order& rhs)
    { return lhs.anger > rhs.anger || (lhs.anger == rhs.anger && lhs.hair < rhs.hair); });
  for (int i = 0; i < n-p+k; ++i)
    b[i] = {a[i].hair, a[i].anger, a[i].index, i};
  sort(b, b+n-p+k, [](const Order& lhs, const Order& rhs)
    { return lhs.hair > rhs.hair || (lhs.hair == rhs.hair && lhs._i < rhs._i); });
  int latest = -1;
  for (int i = 0; i < k; ++i)
  {
    latest = std::max(latest, b[i]._i);
    printf("%d ", b[i].index);
  }
  sort(a+latest+1, a+n, [](const Order& lhs, const Order& rhs)
    { return lhs.anger > rhs.anger; });
  for (int i = 0; i < p-k; ++i)
    printf("%d ", a[latest+1+i].index);
}

Comments