# 洛谷3723 [ah2017_hnoi2017]礼物

## 补习夫妇特

Posted by yjjr's blog on February 26, 2018

# 题目

## 输入输出样例

### 输入样例#1

5 6
1 2 3 4 5
6 3 3 4 5


### 输出样例#1

1


## 说明

### 数据范围

30%的数据满足n≤500, m≤10；

70%的数据满足n≤5000；

100%的数据满足1≤n≤50000, 1≤m≤100, 1≤ai≤m。

70分很好想到

# code

70分暴力代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define inf 1e18
using namespace std;
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=1e5+6;
int n,m,x[maxn],y[maxn],pos;
ll sum,ans,Min=inf;
int main()
{
rep(i,1,n){
sum=0;
rep(j,i,i+n-1)sum+=(x[j]-y[j-i+1])*(x[j]-y[j-i+1]);
if(sum<Min)Min=sum,pos=i;
}
ans=Min;
rep(c,1,m){
sum=0;
rep(j,pos,pos+n-1)sum+=(x[j]+c-y[j-pos+1])*(x[j]+c-y[j-pos+1]);
ans=min(sum,ans);sum=0;
rep(j,pos,pos+n-1)sum+=(x[j]-y[j-pos+1]-c)*(x[j]-y[j-pos+1]-c);
ans=min(sum,ans);
}
cout<<ans<<endl;
return 0;
}


#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<complex>
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define dep(i,a,b) for(ll i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
typedef complex<double> E;
const int maxn=5e4+6;
double pi=acos(-1.0);
E A[maxn<<3],B[maxn<<3],c[maxn<<3];
double x[maxn<<3],y[maxn<<3];
ll ans1,ans2,sum1,sum2,ans,ans3;
int len,n,m,R[maxn<<3],lg;
void fft(E *a,int f){
rep(i,0,len-1)
if(i<R[i])swap(a[i],a[R[i]]);
for(int i=1;i<len;i<<=1){
E wn(cos(pi/i),f*sin(pi/i));
for(int j=0;j<len;j+=(i<<1)){
E w(1.0,0);
for(int k=0;k<i;k++,w*=wn){
E x=a[j+k],y=w*a[j+k+i];
a[j+k]=x+y;
a[j+k+i]=x-y;
}
}
}
}
int main()
{
rep(i,1,n){
scanf("%lf",&x[i]);
ans1+=x[i]*x[i];
sum1+=x[i];
}
rep(i,1,n){
scanf("%lf",&y[i]);
ans1+=y[i]*y[i];
sum2+=y[i];
y[i+n]=y[i];
}
rep(i,1,n)A[i]=x[n-i+1];
rep(i,1,2*n)B[i]=y[i];
len=1;while(len<4*n)len*=2,lg++;
rep(i,0,len)R[i]=(R[i>>1]>>1)|((i&1)<<(lg-1));
fft(A,1),fft(B,1);
rep(i,0,len-1)c[i]=A[i]*B[i];
fft(c,-1);
ans=1e9;
rep(i,-m,m){
ans2=ans1;
ans2+=2*i*sum1;ans2-=2*i*sum2;
ans2+=n*i*i;
rep(j,0,n-1){
ans3=ans2;
ans3-=2*(ll)(c[n+j+1].real()/len+0.5);
ans=min(ans,ans3);
}
}
printf("%lld\n",ans);
}