题解 P6549 【[COCI2010-2011#2] KNJIGE】

听取MLE声一片 · 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;
}

谢谢大家！