题目描述
某涉密单位下发了某种票据,并要在年终全部收回。
每张票据有唯一的ID号。
全年所有票据的ID号是连续的,但ID的开始数码是随机选定的。
因为工作人员疏忽,在录入ID号的时候发生了一处错误,造成了某个ID断号,另外一个ID重号。
你的任务是通过编程,找出断号的ID和重号的ID。
假设断号不可能发生在最大和最小号。
样例
输入样例:
2
5 6 8 11 9
10 12 9
输出样例:
7 9
算法1
(暴力枚举) $O(n)$
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
int a[10010];
bool st[100100];
int main(){
int n,idx = 0;
cin>>n;
string line;
getline(cin,line);
while(n--)
{
getline(cin,line);
stringstream ssin(line);
while(ssin>>a[idx])idx++;
}
sort(a, a + idx);
int n1=0,m=0;
for(int i=0;i<idx;i++)
{
if(st[a[i]])n1=a[i];
st[a[i]]=true;
}
for(int i=1;i<idx;i++)
{
if(a[i]>=a[i-1]+2)m=a[i]-1;
}
cout<<m<<" "<<n1<<endl;
return 0;
}
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<sstream>
#include<cstring>
#include<algorithm>
using namespace std;
int a[10010];
int main(){
int n,idx = 0;
cin>>n;
string line;
getline(cin,line);
while(n--)
{
getline(cin,line);
stringstream ssin(line);
while(ssin>>a[idx])idx++;
}
sort(a, a + idx);
int n1=0,m=0;
for(int i=1;i<idx;i++)
{
if(a[i]==a[i-1])n1=a[i];
else if(a[i]>=a[i-1]+2)m=a[i]-1;
}
cout<<m<<" "<<n1<<endl;
return 0;
}
作者:MrLuo
链接:https://www.acwing.com/activity/content/code/content/191960/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。