自动搬运

查看原文

来自洛谷，原作者为

	yewanxingkong QwQ

搬运于2025-08-24 22:24:11，当前版本为作者最后更新于2020-09-16 21:33:07，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

我第一眼看到这个题时，立马就想到了暴力。

枚举 $k$ ，把前 $k$ 个数和接下来 $k$ 个数从小到大排序然后一一比大小，出现前面 $k$ 个里的第几个数大于等于后面 $k$ 个里的第几个数就排除掉。

然后想到优化：

1. 从后往前枚举，最先找到的正确的那个就是答案。

2. $k$ 的最大值为 $n/2$ ，因为如果大于这个数，加下来的数就凑不齐k个了。

3. 既然给了 $m$ 那就一定是有用的，记录下最早的那个 $m$ , $k$ 值一定是比这个 $m$ 所在序号小的，因为后面不可能到比最大值还大的数。

4. 用桶排。 $sort$ 一定是会炸的。

就下来就是代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int m,n,ji=1000000000,f[20010],fa[2010],fb[2010],chu,o;
inline int read(){
	int date=0,w=1;char c=0;
	while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
	while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
	return date*w;
}
int check(int x){
    int oo=1;
	for(int i=1;i<=x;i++)
		fa[f[i]]+=1;
	for(int i=x+1;i<=2*x;i++)
		fb[f[i]]+=1;
	int a=1,b=1;
	for(int i=1;i<=x;i++){
		while(!fa[a])a++;
		while(!fb[b])b++;
		if(a>=b)oo=0;
		fa[a]--;
		fb[b]--;
	}
	return oo;
}
int main(){
	m=read();
	n=read();
	for(int i=1;i<=n;i++){
		f[i]=read();
		if(f[i]==m&&o==0){
			o=1;
			ji=i;
		}
	}
	ji=min(ji-1,n/2);
	for(int i=ji;i>=1;i--)
		if(check(i)){
			chu=i;
			break;
		}
	cout<<chu;
	return 0;
}