第一篇题解的做法是随机化,但我算了一下,我构造的数据有大于 0.9 的概率它这篇题解的代码会挂掉(
数据生成器:
#include<bits/stdc++.h>
using namespace std;
int main()
{
srand((unsigned)time(NULL));
int n=10000;
cout<<n<<endl;
for(int i=1; i<=4999; ++i) cout<<0<<' '<<i-1<<endl;
for(int i=1; i<=4999; ++i) cout<<10000<<' '<<i+4998<<endl;
cout<<1<<' '<<10000<<endl<<9999<<' '<<-1<<endl;
return 0;
}
正解输出:199980005
第一篇题解输出:199940009
然而,第一篇题解的代码如果增加随机点的次数,能过当前数据范围,但其实,如果加大数据范围到 n≤106,这篇题解不管在时间上或正确性上都会错。