每日算法打卡:错误票据 day 18

发布时间:2024年01月18日

原题链接

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

输入样例:
2
5 6 8 11 9 
10 12 9 
输出样例:
7 9 

题目分析

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

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

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

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

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

示例代码

重置输入流,排序做法

#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读入法,计数做法

#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;
}
文章来源:https://blog.csdn.net/ye_yumo/article/details/135678250
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。