自动搬运

查看原文

来自洛谷，原作者为

	cff_0102 & aqua_qaq | 团子群 185800038 | 如果我死了说明我 AFO 了

搬运于2025-08-24 22:36:05，当前版本为作者最后更新于2022-02-07 20:30:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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)}$）。要证明的就转化为了证明不存在“原方法比新方法更优”的情况。

1. $a_i<b_i,a_i<b_j,a_j<b_i,a_j<b_j$。此时 $a_i\le a_j\le b_j\le b_i$，原方法和新方法答案都是 $a_i+a_j$，这种情况原方法并不比新方法更优。

2. $a_i<b_i,a_i<b_j,a_j<b_i,a_j>b_j$。此时 $a_i\le b_j\le a_j\le b_i$，原方法答案是 $a_i+b_j$，新方法答案是 $a_i+a_j$，因为 $a_j>b_j$，所以这种情况原方法并不比新方法更优。

3. $a_i<b_i,a_i<b_j,a_j>b_i,a_j<b_j$。此时出现 $a_j>b_i\ge b_j$，但 $a_j<b_j$，所以矛盾，该情况不存在。

4. $a_i<b_i,a_i<b_j,a_j>b_i,a_j>b_j$。此时 $a_i\le b_j\le b_i\le a_j$，原方法答案是 $a_i+b_j$，新方法答案是 $a_i+b_i$，因为 $b_i\ge b_j$，所以这种情况原方法并不比新方法更优。

5. $a_i<b_i,a_i>b_j,a_j<b_i,a_j<b_j$。此时 $a_i>b_j>a_j$，但 $a_i\le a_j$，所以该情况也不存在。

6. $a_i<b_i,a_i>b_j,a_j<b_i,a_j>b_j$。此时 $b_j\le a_i\le a_j\le b_i$，原方法答案是 $a_i+b_j$，新方法答案是 $b_j+a_j$，因为 $a_i\le a_j$，所以这种情况原方法并不比新方法更优。

7. $a_i<b_i,a_i>b_j,a_j>b_i,a_j<b_j$。此时出现 $a_j>b_i>a_i$，但 $a_i\le a_j$，所以该情况也是不存在的。

8. $a_i<b_i,a_i>b_j,a_j>b_i,a_j>b_j$。此时 $b_j\le a_i\le b_i\le a_j$，原方法答案是 $a_i+b_j$，新方法答案是 $b_j+b_i$，因为 $a_i<b_i$，所以这种情况原方法并不比新方法更优。

9. $a_i>b_i,a_i<b_j,a_j<b_i,a_j<b_j$。此时 $b_i<a_i<b_j$，但 $b_i\ge b_j$，所以该情况不存在。

10. $a_i>b_i,a_i<b_j,a_j<b_i,a_j>b_j$。此时 $b_i<a_i<b_j$，但 $b_i\ge b_j$，所以该情况不存在。

11. $a_i>b_i,a_i<b_j,a_j>b_i,a_j<b_j$。此时 $b_i<a_i<b_j$，但 $b_i\ge b_j$，所以该情况不存在。

12. $a_i>b_i,a_i<b_j,a_j>b_i,a_j>b_j$。此时 $b_i<a_i<b_j$，但 $b_i\ge b_j$，所以该情况不存在。

13. $a_i>b_i,a_i>b_j,a_j<b_i,a_j<b_j$。此时 $a_i>b_i>a_j$，但 $a_i\le a_j$，也出现矛盾。

14. $a_i>b_i,a_i>b_j,a_j<b_i,a_j>b_j$。此时 $a_i>b_i>a_j$，但 $a_i\le a_j$，也出现矛盾。

15. $a_i>b_i,a_i>b_j,a_j>b_i,a_j<b_j$。此时 $b_j>a_j>b_i$，但 $b_i\ge b_j$，同样出现矛盾。

16. $a_i>b_i,a_i>b_j,a_j>b_i,a_j>b_j$。此时 $b_j\le b_i\le a_i\le a_j$，原方法和新方法答案都是 $b_i+b_j$，所以这种情况原方法并不比新方法更优。

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

代码实现：

所以在排序好的两个数组中，直接一一对应进行比较就行了。这个必然是最优方案。对于第 $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;//不要忘了
}

望管理能过这篇题解。