首页 > 代码库 > 九度OJ 1375 陈博的完美主义 (枚举,细心细心)

九度OJ 1375 陈博的完美主义 (枚举,细心细心)

题目1375:陈博的完美主义(25分)

时间限制: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
这道题,提交了9次才AC,脑子秀逗了,不过第二个数据真的好屌的,得考虑负数,0,哎,还好一开始选择了atoi函数

#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 陈博的完美主义 (枚举,细心细心)