每日算法打卡：错误票据

算法
790 words

原题链接

1204. 错误票据

题目难度：简单

题目来源：第四届蓝桥杯省赛C++ A/B组,第四届蓝桥杯省赛Java A/B组

题目描述

某涉密单位下发了某种票据，并要在年终全部收回。

每张票据有唯一的ID号。

全年所有票据的ID号是连续的，但ID的开始数码是随机选定的。

因为工作人员疏忽，在录入ID号的时候发生了一处错误，造成了某个ID断号，另外一个ID重号。

你的任务是通过编程，找出断号的ID和重号的ID。

假设断号不可能发生在最大和最小号。

输入格式

第一行包含整数 N，表示后面共有 N 行数据。

接下来 N 行，每行包含空格分开的若干个（不大于100个）正整数（不大于100000），每个整数代表一个ID号。

输出格式

要求程序输出1行，含两个整数 m,n，用空格分隔。

其中，m表示断号ID，n表示重号ID。

数据范围

1≤N≤100

输入样例：

1
2
3
2
5 6 8 11 9 
10 12 9

输出样例：

1
7 9

题目分析

这道题目的意思就是从随机开始的一个id序列，存在一个段号和一个重复，需要找到断号和重复的数字

这道题的难度是在数据输入的，他只告诉我们输入的行数，但并不告诉每一行的数据量

对于这个题目的解决是这样的，我们可以开一个布尔数组，从前往后扫描每一个数字，先判断每一个数字是否出现过，如果出现过就说明这个id是重复的

对于中断的数字，我们可以先找到最小值，再从最小值开始扫描，第一个缺失的位置就是断号的位置

第二个做法就是用排序的做法，首先把整个数组排序，我们要从第二个位置开始扫描，如果这个数字跟前一个数字的差为0，那么就是重号，如果数字跟前一个数字相差大于1，则为断号

示例代码

重置输入流，排序做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<string>
#include<sstream>
#include<algorithm>
using namespace std;

const int N = 10010;

int n;
int a[N];

int main()
{
    int cnt;
    cin >> cnt;
    string line;
    getline(cin, line); // 读取第一行末的回车

    while (cnt--)
    {
        getline(cin, line);
        stringstream ssin(line); // 初始化输入流
        while (ssin >> a[n]) n++;
    }

    sort(a, a + n);

    int ans1, ans2;
    for (int i = 1; i < n; i++)
    {
        if (a[i] - a[i - 1] > 1)
            ans1 = a[i] - 1;
        else if (a[i] - a[i - 1] == 0)
            ans2 = a[i];
    }
    cout << ans1 << ' ' << ans2 << '\n';
    return 0;
}

EOF读入法，计数做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1000010;
bool st[N]; // 状态数组
int main()
{
    int n,m;
    int tmp;
    int nn;
    cin>>nn; // 行数
    while(scanf("%d",&tmp)!=EOF) // tmp表示数字
    {
        if(st[tmp]==false) // 标记
            st[tmp] = true;
        else
            n = tmp; // n表示重复的数字
    }
    int start = 0;
    while(st[start]==false) // 找到最小的数字
        start++;
    for(int i=start;;i++) // 找缺失的数字
    {
        if(st[i]==false)
        {
            m = i;
            break;
        }
    }
    cout<<m<<' '<<n<<'\n';
    return 0;
}
Comments