P2571 [SCOI2010]傳送帶

題意：

你要從 A 點到 D 點。有兩條傳送帶：第一條從 A 到 B，速度為 pp，第二條從 C 到 D，速度為 q。不走傳送帶時速度為 r。求從 A 到 D 的最少時間。

題解：

很明顯，答案路徑是由AE+EF+FD組成的，E在AB上，F在CD上。
答案就是dis(A,E)/p+dis(E,F)/r+dis(F,D)/q
這是一個二元函數，E和F都是未知的
我們可以假設E已知，此時就是找一個F讓f(E)=dis(E,F)/r+dis(F,D)/q最小，會發現這是一個單峰函數，也就是f(E)可以通過三分F得到最小值，而E也是未知量，我們還要取dis(A,E)/p+f(E)的最小值，我們發現這還是一個單峰函數，三分尋找E，就是答案
總結：三分套三分
怎么看出這個是單峰函數？我們一開始是將E和F一個固定，比如單看F，然后設F在CD上的比例，然后列出式子，感覺像單峰函數

模擬退火也可以做。。我還不會

代碼：

三分模板要記熟

#include<bits/stdc++.h> #define debug(a,b) printf("%s = %d\n",a,b); using namespace std; typedef long long ll; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll=1e18; const int INF_int=0x3f3f3f3f; inline ll read(){ll s=0,w=1ll;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1ll;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10ll+((ch-'0')*1ll),ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } void rd_test(){#ifdef ONLINE_JUDGE#elsestartTime = clock(); //計時開始freopen("2571.in","r",stdin);#endif } void Time_test(){#ifdef ONLINE_JUDGE#elseendTime = clock(); //計時結束printf("\n運行時間為:%lfs\n",(double)(endTime - startTime) / CLOCKS_PER_SEC);#endif } double Ax,Ay,Bx,By,Cx,Cy,Dx,Dy; double P,Q,R; const double eps=1e-9; double get(double x1,double y1,double x2,double y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } double Time(double x1,double y1,double x2,double y2){double t2=get(x1,y1,x2,y2)/R;double t3=get(x2,y2,Dx,Dy)/Q;return t2+t3; } double work(double x,double y){double t1=get(Ax,Ay,x,y)/P;//第一段double lx=Cx,ly=Cy,rx=Dx,ry=Dy;while(get(lx,ly,rx,ry)>eps){double lmidx=lx+(rx-lx)/3.0;double lmidy=ly+(ry-ly)/3.0;double rmidx=rx-(rx-lx)/3.0;double rmidy=ry-(ry-ly)/3.0;double ans1=Time(x,y,lmidx,lmidy);double ans2=Time(x,y,rmidx,rmidy); if(ans2-ans1>eps){rx=rmidx;ry=rmidy;}else {lx=lmidx;ly=lmidy;}}return t1+Time(x,y,lx,ly); } int main() {//rd_test();cin>>Ax>>Ay>>Bx>>By;cin>>Cx>>Cy>>Dx>>Dy;cin>>P>>Q>>R; double lx,ly,rx,ry;lx=Ax,ly=Ay;rx=Bx,ry=By;while(get(lx,ly,rx,ry)>eps){double lmidx=lx+(rx-lx)/3.0;double lmidy=ly+(ry-ly)/3.0;double rmidx=rx-(rx-lx)/3.0;double rmidy=ry-(ry-ly)/3.0;double ans1=work(lmidx,lmidy);double ans2=work(rmidx,rmidy); if(ans2-ans1>eps){rx=rmidx;ry=rmidy;}else {lx=lmidx;ly=lmidy;}}printf("%.2lf\n",work(lx,ly));return 0;//Time_test(); }

總結

以上是生活随笔為你收集整理的P2571 [SCOI2010]传送带的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。