为什么m不能提前除以n
查看原帖
为什么m不能提前除以n
794701
wo_hen_la楼主2025/1/23 00:05

第三个样例过不了,

#include <bits/stdc++.h>
using namespace std;

#define int __int128
const int N=2e5+5;

int read(){ char ch=getchar();int x=0,f=1;while(ch>'9' || ch<'0'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();return x*f; }
void print(int x){ if(x<0) putchar('-'),x=-x;if(x>9)print(x/10);putchar(x%10+'0'); }

int n;
double m;
int a[N],f[N],sum[N];

bool chk(int x)
{
	for(int l=1;l+x-1<=n;l++){
		int r=l+x-1;
		double s=1.0*(sum[r]-sum[l-1])/x;
		double all=1.0*(f[r]-f[l-1]);
		double fang=all/x-1.0*s*s;
		//cout<<fang<<"\n";
		if(fang<=m) return 1;
	}
	return 0;
}
signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	n=read();m=read();



  //为什么m不能提前除以n
	m/=n;




	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++){
		f[i]=f[i-1]+a[i]*a[i];
		sum[i]=sum[i-1]+a[i];
	}
	int l=1,r=n,ans;
	while(l<=r){
		int mid=(l+r)>>1;
		if(chk(mid)) l=mid+1,ans=mid;
		else r=mid-1;
	}
	print(n-ans);
	return 0;
}
2025/1/23 00:05
加载中...