P8109 [Cnoi2021]幻想乡程序设计大赛 题解

· · 题解

P8109 [Cnoi2021]幻想乡程序设计大赛 题解

upd at 2022/2/9：有人举报了这道题的多个题解（虽然没有我的），吓得我赶紧补充一下分配方法的说明。

upd at 2022/2/10：管理员撤掉了这道题的所有题解，我赶紧再补充一下分配方法的说明。

upd at 2022/2/11：改正题解中的错误并增加补充说明。

思路：

既然这道题由红改黄了（虽然现在改回橙了又改回黄了），那大家就能看出这一道题实际上考的是一一对应直接得到答案就正确的证明过程。

这道题，我们使用贪心算法。尽量给 AC 队伍多的题目选多的气球，就可以尽量多的配对气球，也就是需要一一对应。证明如下：

证明：

这道题可以转化成要证明“最后分配方案存在 a_i\le a_j，且 i>j（逆序）的情况可能会比存在 a_i\le a_j，且 i<j（正常顺序）的情况答案更好”是错误、不存在的。

假设现在有配对好的两队和两组气球，分别为 a_i,a_j,b_i,b_j，满足 a_i\le a_j，且 i>j（也就是逆序）。我们要列出情况证明最终按顺序对应的配法，配对答案是最优的。

假设让它们逆序匹配的方法（a_i 配对 b_i，a_j 配对 b_j，配对答案是 \min{(a_i,b_i)}+\min{(a_j,b_j)}）是最优的，那么就有 b_i\ge b_j。分成 16 种情况分类讨论 a_i 和 b_i，a_i 和 b_j，a_j 和 b_i，a_j 和 b_j 之间的数量关系。后面说“原方法”就是逆序匹配，“新方法”就是顺序匹配（即 a_i 配对 b_j，配对答案是 \min{(a_i,b_j)}+\min{(a_j,b_i)}）。要证明的就转化为了证明不存在“原方法比新方法更优”的情况。

综上所述，在所有存在的情况中，逆序答案永远不比顺序答案更优，那么我们就可以一直用顺序答案，既然在每两对中都是按顺序答案更优，那么我们就按从小到大（从大到小也一样）的顺序来配对气球就可以了。

代码实现：

所以在排序好的两个数组中，直接一一对应进行比较就行了。这个必然是最优方案。对于第 i 道题，如果 b_i 更多，能发的气球就有 a_i 个，否则就有 b_i 个。所以第 i 道题可以让队伍拿到 \min{(a_i,b_i)} 个气球。那么答案就是 \sum\limits^{n}_{i=1}\min{(a_i,b_i)} 了。

#include<bits\stdc++.h>
using namespace std;
int n,a[100005],b[100005];//如题的变量
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<ᥒ;i++){
        cin>>b[i];
    }//输入部分

    //题目保证数据单调不降，不用排序

    int s=0;//存储答案
    for(int i=0;i<n;i++){//直接顺序比较，所有5种情况都是顺序更优
        s+=min(a[i],b[i]);//选更小的那个 
    }//计算
    cout<<s;//输出 
    return 0;//不要忘了
}

望管理能过这篇题解。