Codeforces Round #436 (Div. 2) D. Make a Permutation!

http://codeforces.com/contest/864/problem/D

题意：

给出n和n个数（ai <= n），要求改变其中某些数，使得这n个数为1到n的一个排列，首先保证修改字数最少，其次保证这个排列的字典序最小。

思路：

首先统计未出现过的数的个数，那么这个就是最小的改变次数。

将未出现过的数按升序存进一个数组C。

之后对于每一个数，如果这个数只出现过一次，那么就无法改变这个数。

如果一个数出现过大于一次，那么拿这个数x与C数组的第一个数字y比较，如果x<y 并且x未被标记，那么就标记x被保留过，在下一次遇到x的时候直接替换就可以了。

如果x > y，那么肯定用y去替换x，并且将x的出现次数减去1。

通过上述两个操作，就可以保证字典序最小。

代码：

#include <stdio.h>

int a[200005],b[200005],c[200005];
bool v[200005];

int main()
{
    int n;

    scanf("%d",&n);

    for (int i = 1;i <= n;i++)
    {
        scanf("%d",&a[i]);
        b[a[i]]++;
    }

    int cnt = 0;

    for (int i = 1;i <= n;i++)
    {
        if (!b[i]) c[cnt++] = i;
    }

    int pos = 0;

    for (int i = 1;i <= n;i++)
    {
        int x = a[i];

        if (pos == cnt) continue;

        if (b[x] <= 1) continue;

        int y = c[pos];

        if (!v[x])
        {
            if (x < y)
            {
                v[x] = 1;
            }
            else
            {
                b[x]--;
                pos++;
                a[i] = y;
            }
        }
        else
        {
            b[x]--;
            a[i] = y;
            pos++;
        }
    }

    printf("%d
",cnt);

    for (int i = 1;i <= n;i++)
    {
        if (i == 1) printf("%d",a[i]);
        else printf(" %d",a[i]);
    }

    return 0;
}