自动搬运

查看原文

来自洛谷，原作者为

	杨誉yy Not a part of your machine.

搬运于2025-08-24 22:18:15，当前版本为作者最后更新于2020-11-12 20:25:06，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Solution1: 36pts

第一眼过去，一看就是带有简单决策的模拟。

那么，手动模拟怎么做呢？对于样例给出的输入，先将其排序，得到E和B的手牌：
E 1 4 6
B 2 3 5

从B的最小手牌2开始，对E的手牌由大到小进行遍历，若遇到比该牌小的牌，$ans++$，同时对这张E的手牌进行标记，不再进行比较。

那么，在循环到手牌2时，发现E的第一张手牌1比2小，于是$v[e[1]]=true$且$ans++$。

接着我们发现，B的第二张手牌已经是全场最小的牌。于是与当前E手中最大的牌极限一换一，$v[e[3]]=true$。

显然，经过$n$次循环，问题就能全部解决。可这种算法的时间在$O(n^2)$左右徘徊，很显然是过不了的。

暴力打下去，拿了36分，代码：

#include<cstdio>
#include<algorithm>
using namespace std;
int ans,i,j,n,m,tmp,tail,cnt;
int a[100010],b[100010];
bool v[100010];
int main()
{
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&b[i]);
		v[b[i]]=true;
	}
	sort(b+1,b+n+1);
	for(i=1;i<=2*n;i++)
	{
		if(!v[i])
		{
			cnt++;
			a[cnt]=i;
		}
		if(cnt==n)
		{
			break;
		}
	}
	tail=n+1;
	for(i=1;i<=n;i++)
	{
		for(j=n;j>=1;j--)
		{
			if(b[j]!=-1&&a[i]>b[j])
			{
				ans++;
				b[j]=-1;
				break;
			}
		}
		if(tmp==ans)
		{
			do
			{
				tail--;
			}
			while(b[tail]==-1);
			b[tail]=-1;
			
		}
		tmp=ans;
	}
	printf("%d",ans);
}

Solution2: 100pts

暴力只拿了36分，在模拟方式上也没有太大的改进空间。这时我们发现在实现模拟的过程中有很多无用的操作：对最小数的“极限一换一”处理并没有在决策上起到任何帮助；对E手中的牌的标记没有记录下来的必要。即对于B的一张牌，只要知道它有赢面即可，不用精确到每一张牌的决策。

经过简化，我们可以将操作流程理解为：对B手中的所有牌进行遍历，找出所有在E手中比他小且未曾被使用过的牌，$cnt++$。若当前$cnt>0$，则$cnt--$并将$ans++$。

显然，若仍继续使用原先的储存结构，实现过程将会很难办。我们可以很容易地想到用桶来储存。

输入时用bool型的$v[]$来记录E的手牌。接着进行$2n$次循环：对于每一次循环，若$v[i]==true$，则$cnt++$，表示对于当前的牌，E手中共有$cnt$张手牌没被使用且比当前的牌小。

若$!v[i]$，表示i为B的手牌，则对$cnt$进行判断；若$cnt>0$，则表示该牌有赢面，于是$ans++$,E手中可取用的手牌少了一张，$cnt--$。

因为使用桶的方式进行储存，所以在进行遍历时数列本身是有序的，在记录$cnt$的值时非常便捷。可以看出，该算法的时间接近于$O(n)$，完全可以通过本题。

AC代码如下：

#include<cstdio>
int ans,i,j,n,m,tmp,tail,cnt,b;
bool v[100010];
int main()
{
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&b);
		v[b]=true;
	}
	for(i=1;i<=2*n;i++)
	{
		if(!v[i])
		{
			if(cnt>0)
			{
				cnt--;
				ans++;
			}
		}
		else
		{
			cnt++;
		}
	}
	printf("%d",ans);
}