cf-edu165D

发表于 分类于 ， ， 阅读次数： Waline： 本文字数： 959 阅读时长 ≈ 3 分钟

题意：

爱丽丝和鲍勃正在商店里玩游戏。商店里有 \[n\] 件商品；每件商品有两个参数： \[a_i\] （爱丽丝的物品价格）和 \[b_i\] （鲍勃的物品价格）。

爱丽丝希望选择一个商品子集（可能是空）并购买它们。之后，Bob 会执行以下操作：

  • 如果爱丽丝购买的物品少于 \[k\] ，则鲍勃可以免费拿走所有物品；
  • 否则，他会免费拿走爱丽丝购买的\[k\] 个物品（由鲍勃选择是哪个 \[k\] 个物品），至于其他选择的物品，鲍勃会从爱丽丝那里购买，并为 \(i\) -个物品支付 \[b_i\]。

爱丽丝的利润等于 \[\sum\limits_{i \in S} b_i - \sum\limits_{j \in T} a_j\] ，其中\[S\] 是鲍勃从爱丽丝处购买的物品集， \[T\] 是爱丽丝从商店购买的物品集。换句话说，爱丽丝的利润就是鲍勃支付给她的金额和她购买商品所花费的金额之间的差额。

爱丽丝希望自己的利润最大化，而鲍勃希望爱丽丝的利润最小化。您的任务是计算在爱丽丝和鲍勃都采取最优行动的情况下爱丽丝的利润。

Problem - D - Codeforces

题解：

注意到，Bob在选择免费的时候显然是直接免费最大的\[b_i\]，于是，Alice总是希望选出的物品中价值最高的物品的成本尽可能的小，而剩下的物品的\[b_i - a_i\]尽可能的大。

先考虑极端情况，对单个物品，无论该物品是怎样的情况都不是会选。显然推广到当n>count(\[a_i<b_i\])时，不选都是最好的。显然，这仅仅是不考虑利润为负数的情况。于是我们假定必须选物品，并将结果与0取最大。

对于一个物品\[i\]，我们可以证明在\[a_i < b_i\]时该物品是必选的吗？如果我们选了这个物品：

  1. 并未被免费，则b并非为被选中物品（数量大于k）的前k+1大显然，我们应该选择它

  2. 被免费了，则b为被选中物品（数量大于k）的前k+1大,我们需要考虑对Alice来说，如果一个物品加进来就被免费了（b为前k+1大）且希望利润最大，我们应该淘汰掉本来免费当中b最大的，即应该去除b最大的物品。考虑到去除的b与加进b中的差值可能大于该物品本身利润，因此是无法确定是否选择的。

综上，无法确定在\[a_i < b_i\]时该物品是必选，对这个不等式的反也成立的物品也成立。

注意到在2中我们说如果一个物品加进来就被免费了，则b为前k+1大。这说明，对于整体来说存在一个b该b以上的物品全免费，该b以下的物品计算利润。我们可以排序后枚举这个值模拟一下上述过程，与答案取最大。

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
void slove() {
    cin >> n >> k;
    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) cin >> b[i];
    vector<int> id(n);
    for(int i=0;i<n;i++) id[i] = i;
    sort(id.begin(), id.end(), [&](int x, int y){
        if (b[x] != b[y]) return b[x] > b[y];
        return a[x] < a[y];
    });

    // for(int i=0;i<n;i++) cout<<a[id[i]]<<' '<<b[id[i]]<<endl;
    // cout<<nline;

    ll s1 = 0, s2 = 0, ans = 0;
    set<int> s;
    for(int i = 0; i < k; i++){
        s.insert(a[id[i]]);
        s1 += a[id[i]];
    }
    for(int i = k; i < n; i++){
        if (b[id[i]] > a[id[i]]){
            s2 += b[id[i]] - a[id[i]];
        }
    }
    for(int i = k; i < n; i++){
        ans = max(ans, s2 - s1);
        if (b[id[i]] > a[id[i]]){
            s2 -= b[id[i]] - a[id[i]];
        }
        s.insert({a[id[i]], id[i]});
        s1 += a[id[i]];
        s1 -= *(--s.end());
        s.erase(--s.end());
    }
    cout << ans << '\n';
}