标签：rmid long int Bad lmid n1 n2 502 Gateway
- 最优数学期望的分界点并不在区间中点处，因此需要整数三分，应当可以通过l=lmid+1、r=rmid-1收缩区间
- ACM时代，应当可以通过__gcd函数求最大公约数，不用自己手写了。【就算会编译错误也不计入罚时，试错成本极低】
- 对double比较相对大小的精度还是要有信心的，虽然这道题其实用不上double，稍微变形一下就好了
- 赛场上忘开long long了，万幸本题三分的结论应该是落在根号处，不会超精度，下次千万要谨慎
点击查看代码
//三分法求单谷函数极值
#include <bits/stdc++.h>
using namespace std;
long long t;
bool cmp(long long n1,long long n2)
{
return (n1>n2)^(n1*n2>2*t);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>t;
long long l=1,r=t;
while(l<r)
{
long long lmid=(l+r)>>1,rmid=lmid+1;
if(cmp(lmid,rmid))
{
r=rmid-1;
}
else
{
l=lmid+1;
}
}
long long x=l*(l+1)/2+t-l;
long long y=l;
long long g=__gcd(x,y);
x/=g;
y/=g;
cout<<x<<' '<<y<<"\n";
}
return 0;
}
标签：rmid,
long,
int,
Bad,
lmid,
n1,
n2,
502,
Gateway
From： https://www.cnblogs.com/watersail/p/18426083