/**//* 抄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
搜索
最新评论
|
|