首页 > 代码库 > 九度OJ 1375 陈博的完美主义 （枚举，细心细心）
九度OJ 1375 陈博的完美主义 （枚举，细心细心）
时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：1158
解决：287
- 题目描述：
- 上一回合大家都知道，在JOBDU团队里，陈博是最讲平均主义的人，对数字十分敏感。事实上，他还是个数字完美主义者。例如看到N个数字的时候，从1到N的每个数都需要在其中出现且仅出现一次，否则他就觉得这个数字序列不完美。后来，我明白了：这是排列！对于一个整数序列d1, d2, d3 ... dn，你是否能够算出至少改变其中的几个数，才能把他们变成从1到N的一个排列？例如，对于整数序列 3, 2, 2，我们只需要将其中的一个2改为1就能得到一个从1到3的排列：3, 1, 2
- 输入：
- 每个测试文件包含多个测试案例，每个测试案例两行，第一行包括一个整数N，代表整数序列的长度，第二行是以空格隔开的N个整数，代表该整数序列。其中我们能保证1 <= N <= 10^5，每个整数的长度不超过100.
- 输出：
- 对于每个整数序列，输出一行，包含一个整数，表明至少要改变该整数序列的多少个数才能得到一个从1到N的排列。
- 样例输入：
3 3 2 2 1 1
- 样例输出：
1 0
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<string>
#include<stdlib.h>
int flag[1000100];
using namespace std;
inline int parser(string a){
return atoi(a.c_str());
}
int main(int argc, char *argv[])
{
int N;
int ans;
while(~scanf("%d",&N))
{
ans=0;
memset(flag,0,sizeof(flag));
for(int i=0;i<N;++i){
string t;
cin>>t;
if(t.size()>6)ans++;
else{
int tm=parser(t);
if(tm<=0)ans++;
else if(tm>N)ans++;
else {
if(flag[tm]==0)
flag[tm]=1;
else
ans++;
}
}
}
printf("%d\n",ans);
}
return 0;
}
第二组数据也是最耗时的数据，680MS耗在了上面，勉强AC
九度OJ 1375 陈博的完美主义 （枚举，细心细心）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。