自动搬运

查看原文

来自洛谷，原作者为

	liyilin2004 **

搬运于2025-08-24 22:04:14，当前版本为作者最后更新于2018-08-29 15:34:25，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路：贪心

赤裸裸的贪心

把读入的数据分成1~n/2，n/2+1~n两份，排序，用剩下的数（也就是Bessie的牌）最大的对第一份最大的数，依次减小，最小的对第二份最小的，依次增大

上代码咯

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int a[25001],c[25001],b[100001];||a存前半部分，c存后半部分，b记录是谁的牌
int ans;
int main()
{
	cin>>n;
	for(int i=1;i<=n/2;i++)
	{
		cin>>a[i];
		b[a[i]]=1;
	}
	for(int i=1;i<=n/2;i++)
	{
		cin>>c[i];
		b[c[i]]=1;
	}
	sort(a+1,a+1+n/2);
	sort(c+1,c+1+n/2);||排序，方便下面贪心
	int j=2*n;
	for(int i=n/2;i>=1;i--)||从大到小枚举前半部分
	{
		while(b[j]&&j>=1)||找到Bessie未用的最大的牌
			j--;
		if(j<a[i])||最大的也比这张牌小，无解
			continue;
		else
			b[j]=1,ans++;		
	}
	j=1;	
	for(int i=1;i<=n/2;i++)
	{	
		while(b[j]&&j<=2*n)||找到Bessie未用的最小的牌
			j++;
		if(j>c[i])||最小的也比这张牌大，无解
			continue;
		else
			b[j]=1,ans++;
	}
	cout<<ans;
	return 0;
}

安利一发博客liyilin2004的博客 欢迎来拜访⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄