题目

{% raw %}

点击显/隐题目

{% endraw %} 有n个正整数，其中1到n的正整数出现且只出现一次的序列，称为1-n的一个排列。如1，2，3和3，1，2都是1-3的排列，但是1，3，3不是1-3的排列。如今，给n个数，问最少修改几个数，可以使得序列成为1-n的一个排列。

{% raw %}

{% endraw %}

一个整数t，表示测试数据的组数，(1<=t<=210)
对于每一组测试数据，第一行为一个整数n，（1 <= n <= 500）
第二行有n个整数a1,a2,……an，空格分隔，(ai为任意的32位有符号正整数)。

保证多组数据中的n的和不超过100000。

{% raw %}

{% endraw %}

每组测试数据，输出一个整数，表示最少修改几个数。

{% raw %}

{% endraw %}

2
5
1 3 2 4 5
6
1 1 1 1 1 1

{% raw %}

{% endraw %}

0
5

{% raw %}

{% endraw %}

题解

思路应该很容易,不过数据比较坑
用一个数组来记录 1-n 的数字哪个已经读入过了
没有读入的就是要交换的

这道题数据量和题目给的不一样
开大一点能解决

另外可以使用 set 来保存
只要是 1-n 的数字,直接扔到 set 里
最后 n-s.size() 即可

数字存在负数,因此读入的判断两侧都要判断

代码

点击显/隐代码

```cpp 置换的魔术 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份 /*/ #define debug #include //*/ #include #include #include #include using namespace std;

int main(){
#ifdef debug
freopen("in.txt", "r", stdin);
int START = clock();
#endif
cin.tie(0);
cin.sync_with_stdio(false);

int T;
scanf("%d",&T);
while(T--){
    set<int> s;
    s.clear();

    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int t;
        scanf("%d",&t);
        if(t <= n && t >= 1)
            s.insert(t);
    }
    printf("%d\n",n-s.size());
} 

#ifdef debug
printf("Time:%.3fs.\n", double(clock() - START) / CLOCKS_PER_SEC);
#endif
return 0;

}

</div>

AOJ 833.置换的魔术

题目

题解

代码