错误票据
一个无脑排序的题0.0
方法一:无脑调库,O(logn)
#include<bits/stdc++.h>
using namespace std;
int main(){
int n = 0,p = 0,ans1 = 0,ans2 = 0;
cin >> n;
vector<int>arr;
//IO
for(int i = 0;i < n;i ++)
while(cin >> p)
arr.push_back(p);
//sort一下
sort(arr.begin(),arr.end());
int size = arr.size();
//找下重复项
for(int i = 1;i < size;i ++){
if(arr[i] - arr[i - 1] == 2)
ans1 = arr[i] - 1;
if(arr[i] == arr[i - 1])
ans2 = arr[i];
}
cout << ans1 << " " << ans2;
return 0;
}
方法二:建一个arr的copy O(n)
$$ 10^2的数据数据规模要什么自行车xD $$
题目说了只有一个断点和一个重复的,那就建一个新的数组来放,把min_element当开头;
开头不可能是ans,那就把数组初始化成int_min;
然后按位置放,如果这个位置已经被放过了,那就是重复项.
如果最后还没被放置,那就是空缺项.
#include<bits/stdc++.h>
using namespace std;
int main(){
int n = 0,p = 0,ans1 = 0,ans2 = 0;
cin >> n;
vector<int>arr;
//IO
for(int i = 0;i < n;i ++)
while(cin >> p)
arr.push_back(p);
//让最小元素当开头;建一个新数组初始话为int_min
int arrBegin = *min_element(arr.begin(),arr.end());
vector<int>arrcopy(arr.size(),INT_MIN);
//把arr塞进新数组里,找重复项
for(int i : arr){
if(arrcopy[i - arrBegin] == INT_MIN){
arrcopy[i - arrBegin] = i;
}else{
ans2 = i;
}
}
//还没被操作过的位置就是空缺项
auto a = find(arrcopy.begin(),arrcopy.end(),INT_MIN);
ans1 = a - arrcopy.begin() + arrBegin;
cout << ans1 << " " << ans2;
return 0;
}