43740

礼物「AHOI / HNOI2017」

<h3 id="题意">题意</h3>

有两个手环,手环上均有\(n\)个珠子,每个珠子有一个值。你可以给第二个手环每个珠子加上同一个值。求\(\sum(x[i]-y[i])^2\)的最小值。

<hr /><h3 id="思路">思路</h3>

这道题还是比较young and simple的。

设加上的值为\(c\),那么所求式子等价于\(\sum(c+x[i]-y[i])^2=\sum(c^2+(x[i]-y[i])^2+2*c*(x[i]-y[i]))\)

二次函数顶点公式可以得到\(c\)的最优取值为\(\frac{\sum(y[i]-x[i])}{n}\),注意这里会出现精度Question。

FFT求一下\(\sum x[i]y[i]\)即可。

<h3 id="代码">代码</h3> #include <bits/stdc++.h> using namespace std; namespace StandardIO { template<typename T> inline void read (T &x) { x=0;T f=1;char c=getchar(); for (; c<'0'||c>'9'; c=getchar()) if (c=='-') f=-1; for (; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0'; x*=f; } template<typename T> inline void write (T x) { if (x<0) putchar('-'),x=-x; if (x>=10) write(x/10); putchar(x%10+'0'); } } using namespace StandardIO; namespace Solve { const int N=600000; const double pi=acos(-1); typedef complex<double> cx; int n,m,q,L; double ans=0x7fffffff; int x[N],y[N],R[N]; cx a[N],b[N]; int Sx,Sy,S; void fft (cx *tmp,int type) { for (register int i=0; i<n; ++i) if (i<R[i]) swap(tmp[i],tmp[R[i]]); for (register int i=1; i<n; i<<=1) { cx wn(cos(pi/i),type*sin(pi/i)); for (register int j=0; j<n; j+=(i<<1)) { cx w(1,0); for (register int k=0; k<i; ++k,w*=wn) { cx s=tmp[j+k],t=tmp[j+k+i]*w; tmp[j+k]=s+t,tmp[j+k+i]=s-t; } } } } inline void MAIN () { read(n),read(q); for (register int i=1; i<=n; ++i) read(x[i]); for (register int i=1; i<=n; ++i) read(y[i]); for (register int i=1; i<=n; ++i) Sx+=x[i]*x[i],Sy+=y[i]*y[i],S+=(x[i]-y[i]); for (register int i=1; i<=n; ++i) a[i]=x[i]; for (register int i=n+1; i<=2*n; ++i) a[i]=x[i-n]; for (register int i=1; i<=n; ++i) b[i]=y[n-i+1]; m=2*n; for (n=1; n<=m; n<<=1) ++L; for (register int i=0; i<=n; ++i) R[i]=(R[i>>1]>>1)|((i&1)<<(L-1)); fft(a,1),fft(b,1); for (register int i=0; i<=n; ++i) a[i]*=b[i]; fft(a,-1); int c=static_cast<int>(-static_cast<double>(S)/static_cast<double>(m/2)+0.5); for (register int ddd=c-5; ddd<=c+5; ++ddd) { for (register int i=m/2+1; i<=m; ++i) { ans=min(ans,(double)Sx+(double)Sy+2.0*S*ddd+(double)m/2.0*ddd*ddd-2.0*static_cast<int>(a[i].real()/n+0.5)); } } write(static_cast<int>(ans+0.5)); } } int main () { Solve::MAIN(); }

来源:博客园

作者:Ilverene

链接:https://www.cnblogs.com/ilverene/p/11426064.html

Recommend