P7996二分
查看原帖
P7996二分
815779
xhsomesagous楼主2023/11/27 23:00

P7996二分似乎有点问题,哪位大佬帮忙看看,谢谢?

#include<iostream>
using namespace std;
const int maxn=7e6+5;
const int inf=0x3f3f3f3f;
typedef long long ll;
inline ll read()
{
	ll ans=0,w=1;
	char ch;
	while((ch=getchar())<'0'||ch>'9') if(ch=='-') w=-1;
	while(ch>='0'&&ch<='9') ans=(ans<<3)+(ans<<1)+(ch^'0'),ch=getchar();
	return ans*w;
}//快读
inline void write(ll x,char ch=0)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
	if(ch) putchar(ch);
}//快写
ll n=read(),k=read(),a[maxn],sum=0;
ll near=0;
double chazhi=0.0;
double fangcha(ll geshu)
{
	ll sum1=sum*geshu;
	double ave=sum1*1.0/n,ans=0.0;
	for(int i=1;i<=n;i++) ans+=(a[i]*geshu-ave)*(a[i]*geshu-ave);
	return ans*(1.0/n);
}
bool check(ll x)
{
	double tmp=fangcha(x);
	double h=tmp-k>=0?tmp-k:k-tmp;//绝对值
	write(h,'\n');
	if(h<chazhi) //当前绝对值更小,就更新
	{
		near=x;//其实就是答案
		chazhi=h;//更新差值
		return 1;
	}
	return 0;
}
int main()
{
	ll l=inf,r=0;
	for(int i=1;i<=n;i++) 
	{
		a[i]=read();
		sum+=a[i];
		l=a[i]>l?l:a[i],r=a[i]>r?a[i]:r;
      //l为最小边界,r为最大边界
	}
	if(!fangcha(1)) puts("No answer!"),exit(0);//方差为0
	while(r-l>0.5)
	{
		ll mid=(l+r)/2;
		if(check(mid)) l=mid+1;
		else r=mid;
	}
	write(near,'\n');//输出
	return 0;
}
2023/11/27 23:00
加载中...