自动搬运

查看原文

来自洛谷，原作者为

	听取MLE声一片 如果我当时做的再多一点，结局会不会不同呢？

搬运于2025-08-24 22:21:49，当前版本为作者最后更新于2020-05-15 20:17:57，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前面两位大佬把公式发出来了，我就讲一下公式的推导过程。

这里主要是插入排序的思想，就像是打扑克牌，抽到一张扑克牌就往已有的扑克牌里插入。这道题说了顺序为1~n，那么从后往前就是n~1。将ans从n递减，与原数字进行比对，如果不等，这个数就应该插入到前面去，ans应该不变。反之，如果相等，ans就-1，比对下一个。

代码就看这（其实差不多）

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,a[500001],ans;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
        cin>>a[i]; 
	ans=n;
	for(int i=n;i;i--)
		if(a[i]==ans)
            ans--; 
	cout<<ans;
 	return 0;
}

谢谢大家！