 /**//*
抄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
搜索
最新評論

|
|