【题目链接】:http://codeforces.com/problemset/problem/738/E

【题意】



给你一个类似树形的关系;

然后告诉你某个人头顶上有多少个上司numi;

只有father的father才算是它的上司,father的兄弟不算;

然后告诉你所有的人里面最大boss的标号;

问你最少有多少个numi是错误的;

【题解】



会发现;

这里的numi实际上和这个人在树中的深度对应;

则我们把最后的numi数组升序排一下;

如果相邻两个数字它们的差的绝对值不超过1;

且第一个数字为0,且0只出现一次;

那么这个num数组就是合法的;

因为这就表明这棵树是没有断层的;

你总有办法安排它.

那如果中间有断层怎么办?

(这就说明原问题等价于,要改变最少的人的数字,使得最后的升序序列符合上面的要求);

比如如果最后的排序结果为

0 1 1 2 4 5 6 8

我们每次找,最小的,还没被覆盖到的数字;

比如,这里有一个3没被填充到;

这个时候;

我们的策略就是,找最大的,已经被填充过的数字;

(这里是8)

然后把它变成3

->0 1 1 2 3 4 5 6

更一般的;

我们把一开始多余的0(就是不在s位置上的0),设置成INF(因为要求只能有一个0);

则策略就是;

每次找最小的还未被填充的数字,然后用最大的已经填充的数字替换成那个数字;

直到最小的还未被填充的数字已经大于最大的已经填充的数字为止;

或者没有还未被填充的数字了;



【Number Of WA】



1



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

#define Open() freopen("F:\\rush.txt","r",stdin)

#define Close() ios::sync_with_stdio(0),cin.tie(0)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 2e5+100;

const int INF = 2e5+1;

int n,s,a[N],bo[N],ma = 0,ans = 0;

priority_queue<int,vector<int>,greater<int> > xiaogen;

priority_queue<int,vector<int>,less <int> > dagen;

int main()

{

    //Open();

    Close();//scanf,puts,printf not use

    //init??????

    cin >> n >> s;

    rep1(i,1,n)

    {

        cin >> a[i];

        if (i==s)

        {

            if (a[i]!=0)

            {

                ans++;

                a[i] = 0;

            }

        }

        else

        {

            if (a[i]==0)

                a[i] = INF;

            bo[a[i]]++;

            ma = max(ma,a[i]);

        }

    }

    rep1(i,1,ma)

    if (bo[i])

    {

        //有的数字,最大的那个

        while (bo[i]--) dagen.push(i);

    }

    else

    {//没有的数字,最小的那个

        xiaogen.push(i);

    }

    while ( int(xiaogen.size()) && xiaogen.top()<dagen.top())

    {

        int x = xiaogen.top();

        xiaogen.pop();dagen.pop();

        dagen.push(x);

        //把有的数字最大的那个换成最小的没有的那个数字

        ans++;

    }

    cout << ans << endl;

    return 0;

}