由于提问区乌烟瘴气的,我把问题放在分享区啦。
问题如下:
首先题源是牛客网-小白月赛的暴力题。
强迫症
这是我周赛前写完的代码,交了之后,反馈过了96%的样例。几乎AC。
然后周赛开始了,进行周赛。
赛后,我返回这个题。我多给程序加了臭氧优化和快读,再重新提交,反馈只有50%的通过率。
我十分惊讶。
我甚至怀疑一开始我是不是看错了,第一次提交会有96%通过率?
于是我粘贴了第一次的代码重新提交,看看到底是过了多少。
于是神奇的事情发生了,代码AC了。
我更惊讶了。
- 百试百灵的臭氧失效了。
- 经过多次测试发现,这份代码的通过率是波动的。有时AC,有时超时。
- 我适当做了一些代码上的实验,排除了一些因素干扰。
初步怀疑是STL set 和 vector(涉及了erase)操作带来的不确定性。
希望知识广博的同学可以给出合理的解释
附上程序代码
这份是时而AC时而T的。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_set>
using namespace std;
#define int long long
#define fastio ios::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
#define pb push_back
const int N = 1e5+10 ;
int n ;
vector<int> a ;
int ans ;
bool check()
{
unordered_set<int> s ;
for(auto x : a )
{
if(!s.count(x))
{
s.insert(x) ;
}
}
if(s.size() == n ) return 1 ;
return 0 ;
}
signed main()
{
cin >> n ;
for(int i = 1 ; i <= n ; i ++)
{
int x ;
cin >> x ;
a.pb(x) ;
}
sort(a.begin() , a.end() ) ;
// 处理特殊情况
if(a[n-1] == a[n-2])
{
ans++ ;
a.pb(a[n-1] + a[n-2]) ;
a.erase(a.begin() + n - 1 , a.begin() + n ) ;
}
while(1)
{
for(int i = n-2 ; i >= 0 ; i --)
{
if(a[i] == a[i-1]) // 重复了
{
ans ++ ;
a.pb(a[i] + a.back()) ;
a.erase(a.begin() + i , a.begin() + i + 1) ;
}
}
if(check())
{
break ;
}
}
cout << ans << endl;
return 0 ;
}