CF332C. Students' Revenge题解

题目传送门

题意:有 nn 个物品,每个物品有权值 a,ba,b,首先由 A 选择 pp 个物品,然后由 B 从其中再选择 kk 个物品。B 首先想让剩余 pkp-k 个物品的 bb 的和尽可能小,在此基础上让 aa 的和尽可能小;A 首先想让这 kk 个物品的 aa 的和尽可能大,在此基础上让剩余 pkp-kbb 的和尽可能大。问 A 选哪 pp 个才能在 B 走最优策略下对 A 最有利。

首先,A 选 pp 个后由于不知道 B 会怎么选,从而较难确定选哪 pp 个更优。于是我们考虑 A “让” B 选哪 kk 个对 A 最优。由于 B 始终会选对 B 最优的,所以我们 A 能“让” B 选某 kk 个,当且仅当存在至少 pkp-k 个对 B 更劣的选择(这样 B 才会心甘情愿地选 A 规定的那 kk 个)。

  1. 所以,我们先按对 B 的贡献从优到劣排序,A 可以且尽可以从前 n(pk)n-(p-k) 个元素里选“让” B 选的元素(这样后面才存在至少 pkp-k 个更劣的)。
  2. 由于前面这些元素 A 可以任意选,所以可以对前 n(pk)n-(p-k) 再按对 A 的贡献从优到劣排序。此时前 kk 个已经钦定为 B 选的元素,接下来要处理剩下 pkp-k 个元素该怎么选。
  3. 此时这 pkp-k 的限制为:必须比前 kk 个中任意一个对 B 都更劣(为了保证 B 不选它);在此基础上对 A 尽可能优。可以通过对 A 的贡献排序后选最前面满足条件的 pkp-k 个。

通过三次不同的排序处理即可。

By cxm1024

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
#include<bits/stdc++.h>
using namespace std;
struct node {
int a,b,num;
} a[100010];
signed main() {
int n,p,k;
cin>>n>>p>>k;
for(int i=1;i<=n;i++) {
cin>>a[i].a>>a[i].b;
a[i].num=i;
}
sort(a+1,a+n+1,[](node x,node y) {
if(x.b!=y.b) return x.b>y.b;
return x.a<y.a;
}); //对 B 从优到劣排序
sort(a+1,a+n+1-(p-k),[](node x,node y) {
if(x.a!=y.a) return x.a>y.a;
return x.b>y.b;
}); //前 n-(p-k) 个对 A 从优到劣排序
sort(a+k+1,a+n+1,[](node x,node y) {
return x.b>y.b;
}); //后面对 A 从优到劣排序。此时不需要考虑 a 权值,因为这里是要确定 B 不选的元素。
int minb=1e9,maxa=0;
for(int i=1;i<=k;i++) {
cout<<a[i].num<<" ";
if(a[i].b<minb) minb=a[i].b,maxa=a[i].a;
else if(a[i].b==minb) maxa=max(maxa,a[i].a);
}
for(int i=k+1,cnt=0;cnt<p-k;i++)
if(a[i].b<minb||(a[i].b==minb&&a[i].a>=maxa)) {
cout<<a[i].num<<" ";
cnt++;
}
cout<<endl;
return 0;
}