题目
{% 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 %}
题解
思路应该很容易,不过数据比较坑
用一个数组来记录 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>