CF332C. Students' Revenge题解

发表于 分类于

题目传送门

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

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

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