cdq分治論文
cdq分治的應用之一 用來做斜率與X都不單調的斜率優化。。
cdq分治的大致套路就是先按某一個值進行排序
按照序號順序歸并分為 <=mid 與 >mid 的兩部分
遞歸解決左區間的子問題 將左區間對右區間的影響加上 再遞歸解決右區間
體現在這里就是 先按k(斜率)值排序
按序號順序排序 遞歸解決[l,mid]
并在遞歸結束時按x遞增的順序將區間內的點排序
這樣左區間的f值已經為最優并且x遞增 右區間按k值遞增
將左區間的點依次入棧并維護一個凸殼 更新右區間的f值
最后在遞歸解決右區間即可
#include <cstdio>#include <cstring>#include <algorithm>#include <cstring>#include <cmath>#define MAXN 100005#define N 100#define INF 1000000005#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))using namespace std;const double eps = 1e-8;/*f[i]=f[j]/(a[j]*rate[j]+b[j])*rate[j]*a[i]+f[j]/(a[j]*rate[j]+b[j])*b[i] x[j]=f[j]/(a[j]*rate[j]+b[j])*rate[j] y[j]=f[j]/(a[j]*rate[j]+b[j]) ->f[i]=x[j]*a[i]+y[j]*b[i] ->y[j]=f[i]/b[i]-x[j]*a[i]/b[i]*/int n,l1,l2,top,st[MAXN];double f[MAXN];struct point{ double a,b,r,x,y,k; int id;}p[MAXN],t[MAXN];double k(int i,int j){ if(p[i].x-p[j].x==0) return p[i].y-p[j].y>0?INF:-INF; return (p[i].y-p[j].y)/(p[i].x-p[j].x);}void solve(int l,int r){//--f[l]為最優 計算x[l] y[l] if(l==r) { f[l]=max(f[l],f[l-1]); p[l].x=f[l]/(p[l].a*p[l].r+p[l].b)*p[l].r; p[l].y=f[l]/(p[l].a*p[l].r+p[l].b); return; } int mid=(l+r)>>1,j=1,l1=l,l2=mid+1;//--將p按位置排序 for(int i=l;i<=r;i++) if(p[i].id<=mid) t[l1++]=p[i]; else t[l2++]=p[i]; for(int i=l;i<=r;i++) p[i]=t[i];//--遞歸計算左區間 solve(l,mid);//--將左區間入棧 維護凸殼(此時左區間已經按x排好序) top=0; for(int i=l;i<=mid;i++) { while(top>1&&k(i,st[top])>k(st[top],st[top-1])) top--; st[++top]=i; }//--用左區間的點更新右區間的f for(int i=mid+1;i<=r;i++) { //f[i]=x[j]*a[i]+y[j]*b[i] while(j<top&&k(st[j],st[j+1])>p[i].k) j++; int tmp=st[j]; f[p[i].id]=max(f[p[i].id],p[tmp].x*p[i].a+p[tmp].y*p[i].b); }//--遞歸計算右區間 solve(mid+1,r);//--將L-R按x排序 l1=l,l2=mid+1; for(int i=l;i<=r;i++) if((l2>r||p[l1].x<p[l2].x)&&l1<=mid) t[i]=p[l1++]; else t[i]=p[l2++]; for(int i=l;i<=r;i++) p[i]=t[i];}bool cmp(point a,point b){return a.k>b.k;}int main(){ scanf("%d%lf",&n,&f[0]); for(int i=1;i<=n;i++) { scanf("%lf%lf%lf",&p[i].a,&p[i].b,&p[i].r); p[i].k=-p[i].a/p[i].b,p[i].id=i; } sort(p+1,p+1+n,cmp); solve(1,n); 把while寫成if結果調了一上午 我好菜啊。。新聞熱點
疑難解答
