 /**//*
抄PKKJ wiki 的 Orz

题意:给出F[],G[],求使得下列函数最小的实数x
n
p(x) = ∑ min { (F[i] + x - G[j])^2 }
i j∈[1,m]

第一眼看上去,不知从哪里入手,主要是因为要先确定G[j]
假设我们对F[i]已经确定了Gj[i],则上式变为
p(x) = ∑(F[i]+x-Gj[i])^2 = (F[1]+x-Gj[1])^2 + (F[2]+x-Gj[2])^2 + + (F[n]+x-Gj[n])^2
展开整理 nx^2 + 2∑(F[i]-Gi[j])x + (F[i]-Gi[j])^2 = Ax^2 + Bx + C
则答案为满足给定一定区间的最值了

那怎么确定G[j]呢?枚举
首先有个性质,
若G[j]<=F[i]+x<=G[j+1],设mid = (G[j]+G[j+1])/2
当F[i]+x <= mid时,应与G[j]匹配
当F[i]+x >= mid时,应与G[j+1]匹配
所以mid是一个分界点(事件点),所以对每个F[i]求出其所有的分界点(m个),则总共有nm个事件点

按照事件点的x值排序后,枚举
一开始时,全部的F[i]匹配G[0],然后逐步枚举事件点x
引入x后,只有某个点F[id]匹配的G就改变了,由G[j-1]变到G[j],这时再重新计算更新答案即可
O(1)的更新了

启示:看起来是一道数学题,但毕竟是程序设计的,需要程序设计的方法,这里就是枚举了!!
应该假设确定了每个点匹配的G[j],这样就能直接展开那个p(x)了,就很容易求得最值了!!
而确定G[j],引入事件点,排序后,每次只更新一个O(1)
*/
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int MAXN = 2010;
const double DINF = 1e60;//

struct Event
  {
double x;
int id;
bool operator<(const Event &B)const
 {
return x<B.x;
}
 Event() {}
Event(double _x,int _id)
 {
x = _x;
id = _id;
}
};

Event E[MAXN*500];
double F[MAXN],G[MAXN];
int pos[MAXN];
int n,m;

double update(double A,double B,double C,double xl,double xr,double &x)
  {
x = -B/(2.0*A);
//注意要在限制的范围内[xl,xr]
if(x>xr)x = xr;
if(x<xl)x = xl;
return A*x*x + B*x + C;
}

double solve()
  {

for(int i=0;i<n;i++)
scanf("%lf",&F[i]);
for(int i=0;i<m;i++)
scanf("%lf",&G[i]);

int ne = 0;
for(int i=0;i<n;i++)
for(int j=1;j<m;j++)
 {
double mid = (G[j] + G[j-1])/2.0;
// x = mid - F[i];
E[ne++] = Event(mid-F[i],i);
}
sort(E,E+ne);

memset(pos,0,sizeof(pos));
double A,B,C,best,ans;
A = B = C = 0.0;
for(int i=0;i<n;i++)
 {
A += 1.0;
B += 2*(F[i]-G[0]);
C += (F[i]-G[0])*(F[i]-G[0]);
}

double pre = -DINF;
best = DINF;
for(int i=0;i<ne;i++)
 {
double x,tmp = update(A,B,C,pre,E[i].x,x);
if(tmp<best)best = tmp,ans = x;
pre = E[i].x;
pos[E[i].id]++;
int id = E[i].id;
B -= 2*(F[id] - G[pos[id]-1]);
B += 2*(F[id] - G[pos[id]]);
C -= (F[id] - G[pos[id]-1])*(F[id] - G[pos[id]-1]);
C += (F[id] - G[pos[id]])*(F[id] - G[pos[id]]);
}
double x,tmp = update(A,B,C,pre,DINF,x);
if(tmp<best)best = tmp,ans = x;
return ans;
}

int main()
  {
while(~scanf("%d%d",&n,&m))
printf("%.3f\n",solve());
return 0;
}
|
|
常用链接
随笔分类
Links
搜索
最新评论

|
|