自动搬运

查看原文

来自洛谷，原作者为

	QwQcOrZ AFOed | 印刷成文不能代表它们就是真理 | 极东魔术昼寝结社之夏 | The Great Gig In The Sky

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

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

以下是正文

显然如果一头牛拿不到礼物，那么他后面的牛也都拿不到礼物

那么就可以考虑二分第一个拿不到礼物的牛的位置，最后计算拿不到礼物的牛的个数并输出

如何 check 当前位置能否拿到礼物？考虑下述做法：

• 方便起见，我们称当前二分到的牛为 牛1437 ，设该牛的位置为 $now$
• 将当前位置之前的牛（即第 $1$ 到第 $now-1$ 头牛）按插入的位置从后到前排序（即降序排序）
• 将所有牛依次插入到其应该插入的位置（按之前排序的顺序），并改变 牛1437 的位置（$now\gets now-1$），如果插入到了 牛1437 的前面，那么 牛1437 就不可能获得礼物了，返回 $\operatorname{false}$
• 如果所有牛都插入到了 牛1437 的位置之后，说明此牛能拿到礼物，返回 $\operatorname{true}$

经过思考，我们会发现这个做法是对的

显然二分的 check 需要满足他是个充分必要条件，那么考虑证明此做法的充要性

先证明必要性：因为只有满足所有在 牛1437 前的牛都插入到 牛1437 之后了，牛1437 才能拿到礼物。而上述插入方式显然是最容易满足条件的，所以该条件有必要性

然后是充分性：显然当满足必要性的情况下，如果 牛1437 不能拿到礼物当且仅当 牛1437 之前的牛没有机会拿到礼物，以至于它不会插入到 牛1437 之后

而这种情况发生的唯一条件是 牛1437 之前的牛前面已经形成循环节了

又因为这题有单调性，也就是越前面的牛越容易合法。所以这里在 牛1437 之前的牛如果拿不到礼物，那么 牛1437 也拿不到礼物。如果由此迭代到第一个拿不到礼物的牛，就能发现在那个位置判也是不合法的（不能拿到礼物的）。而后面的牛显然不可能比前面的牛优（也就是更容易合法），所以 牛1437 也是不会合法的

故此有充分性

时间复杂度 $O(nlog^2n)$，用桶排可以优化到 $O(nlogn)$

$Code\ Below$

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;

int read()
{
	int s=0;
	char c=getchar(),lc='+';
	while (c<'0'||'9'<c) lc=c,c=getchar();
	while ('0'<=c&&c<='9') s=s*10+c-'0',c=getchar();
	return lc=='-'?-s:s;
}
void write(int x)
{
	if (x<0)
	{
		putchar('-');
		x=-x;
	}
	if (x<10) putchar(x+'0');
	else
	{
		write(x/10);
		putchar(x%10+'0');
	}
}
void print(int x,char c='\n')
{
	write(x);
	putchar(c);
}
int a[N],b[N],n;
bool check(int now)
{
    //因为题目给出的位置是从后往前数的，所以这里的位置都是以从最后一个向前的若干个的形式表示
	for (int i=1;i<now;i++) b[i]=a[i];
	sort(b+1,b+now);
	int tmp=n-now;//牛1437的位置
	for (int i=1;i<now;i++)
	{
		if (b[i]>tmp) return 0;
		tmp++;
	}
	return 1;
}

signed main()
{
	n=read();
	for (int i=1;i<=n;i++) a[i]=read();
	int l=1,r=n;
	while (l<=r)
	{
		int mid=(l+r)/2;
		if (check(mid)) l=mid+1;
				   else r=mid-1;
	}
	print(n-r);

	return 0;
}