直接拆式子：
[sum_{i=1}^nleft(x_i-y_i+c
ight)^2
]
[sum_{i=1}^n x_i^2-x_i imes y_i+c imes x_i-x_i imes y_i+y_i^2-c imes y_i+x_i imes c-c imes y_i+c^2
]
[sum_{i=1}^n x_i^2+y_i^2+c^2-2 imes x_i imes y_i+2cleft(x_i-y_i
ight)-2 imes x_i imes y_i
]
[left(sum_{i=1}^n x_i^2
ight)+left(sum_{i=1}^n y_i^2
ight)+cleft(2left(sum_{i=1}^n x_i-y_i
ight)+nc
ight)-2left(sum_{i=1}^n x_i imes y_i
ight)
]
为了取到最小值，前三项都是确定的。其中 (cin[1-m,m-1])，因为初始的差至多是 (m-1)。
将下标全部减一，也就是说我们只需要求出下式的最大值
[sum_{i=0}^{n-1}x_i imes y_i
]
按照套路翻转下标
[sum_{i=0}^{n-1}x_{n-1-i} imes y_i
]
尝试将 (x) 倍长然后再卷起来，举个例子：
[x={x_0,x_1,x_0,x_1}
]
[y={y_0,y_1}
]
[z={x_0y_0,x_0y_1+x_1y_0,x_1y_1+x_0y_0,x_0y_1+x_1y_0,x_1y_1}
]
可以发现第 (1) 和 (2) 项恰好组成了所有旋转后的方案。也就是说第 (n-1) 到 (2n-2) 项组成了所有旋转后的 (n) 种方案。
取个 (max) 就好啦，时间复杂度 (Oleft(nlog n+m ight))。
code:
#include<bits/stdc++.h>
using namespace std;
#define N 131073
#define Db double
#define Min(x,y)((x)<(y)?x:y)
#define Max(x,y)((x)>(y)?x:y)
#define For(i,x,y)for(i=x;i<=(y);i++)
const Db PI=acos(-1.0);
struct Complex
{
Db x,y;
Complex(Db X=0.0,Db Y=0.0):x(X),y(Y){};
Complex operator+(Complex const&_)const
{
return Complex(x+_.x,y+_.y);
}
Complex operator-(Complex const&_)const
{
return Complex(x-_.x,y-_.y);
}
Complex operator*(Complex const&_)const
{
return Complex(x*_.x-y*_.y,x*_.y+y*_.x);
}
}x[N],y[N];
int tr[N];
void FFT(Complex*f,int len,bool type)
{
int i,p,j,now;
Complex tmp,ome,buf;
For(i,0,len-1)
if(i<tr[i])swap(f[i],f[tr[i]]);
for(p=2;p<=len;p<<=1)
{
now=p>>1;
ome=Complex(cos(2.0*PI/Db(p)),sin(2.0*PI/Db(p))*(type?-1.0:1.0));
for(j=0;j<len;j+=p)
{
buf=Complex(1.0,0.0);
For(i,j,j+now-1)
{
tmp=buf*f[i+now];
f[i+now]=f[i]-tmp;
f[i]=f[i]+tmp;
buf=buf*ome;
}
}
}
if(type)
For(i,0,len-1)f[i].x=round(f[i].x/Db(len));
}
int main()
{
int n,m,i,tot=0,mn=INT_MAX,mx=INT_MIN;
scanf("%d%d",&n,&m);
For(i,1,n)scanf("%lf",&x[i].x);
For(i,1,n)scanf("%lf",&y[i].x),tot+=(x[i].x-y[i].x)*2.0;
For(i,1-m,m-1)mn=Min(mn,i*(tot+n*i));
For(i,1,n)
{
mn+=x[i].x*x[i].x+y[i].x*y[i].x;
x[i-1].x=x[i].x;
y[i-1].x=y[i].x;
}
For(i,0,(n-1)>>1)swap(x[i],x[n-1-i]);
y[n].x=0.0;
For(i,0,n-1)x[i+n].x=x[i].x;
m=1;
while(m<n<<1)m<<=1;
For(i,0,m-1)tr[i]=tr[i>>1]>>1|(i&1?m>>1:0);
FFT(x,m,0),FFT(y,m,0);
For(i,0,m-1)x[i]=x[i]*y[i];
FFT(x,m,1);
For(i,n-1,(n-1)<<1)mx=Max(mx,x[i].x);
printf("%d",mn-(mx<<1));
return 0;
}
可以学到的技巧：
- 一些跟下标有关的东西可以试试卷积。