P2780 [AHOI2016初中组] 游戏 题解

luxiaomao · 2023-09-30 09:59:08 · 题解

前言（废话）

看着这道蓝题，手推了十分钟背包（我是蒟蒻），然后才看到数据范围……

又可以水题解用贪心做啦！

分析

题解区似乎有大佬上了贪心的代码，但是蒟蒻决定把这个过程讲得清晰一些，争取让像我一样的蒟蒻也能看懂（蒟蒻会写蓝题吗）

首先给出最终答案的式子：

(此处的 x 序列经过升序排序)

那么这个式子是怎么得出来的捏？

题目说了，双方的策略都是最优的。

先考虑小雪（t 的选定）

题目只给出 a 和 b，如何选定 t，使得 |t-m| 最大？

首先明确两个极端：

• 如果 t 向 0 接近，可以证明不是最优（懒得证），毕竟小可可以尽量选小的，同样让 m 向 0 接近。

• 如果 t 向无穷大接近，是最优的，因为小可选的数再大，也只能选 k 个数，那么 t 应该尽量比这 k 个数的和大。

综上，t 的值应尽量大，且其上界为 b，则 t = b。

（其实这里只是蒟蒻的通俗口语解释，感觉数学证明用在这里小题大做，请 dalao 们不要嫌弃）

接着是小可（m 的选定）

如果能够看懂为什么 t = b，那么接下来的应该难度不大。

人家 t 都尽量大了，那你的 m 也应该尽量大呀。

选取序列 x 中最大的 k 个数，即将序列 x 升序排序后 m = \sum\limits_{i = n-k+1}^{n}x_i 。

整合一下，就能得到开头给出的公式。

Code Time

#include<bits/stdc++.h>
using namespace std;

int x[255];
int n,k,a,b;

int main()
{
    scanf("%d%d%d%d",&n,&k,&a,&b);
    for(int i = 1;i <= n;i++)
    {
        scanf("%d",&x[i]);
    }
    sort(x+1,x+1+n);
    for(int i = n;i + k > n;i--)
    {
        b -= x[i];
    }
    printf("%d",b);
    return 0;
}

完结撒花~

第一次写有关数学的题解，还希望管理员大大看我写得这么认真，给过QAQ~