题解 【卢卡杨比火车站/（Nescafé杯模拟赛一）星之船】

好像是学校**祖传**老题来着。 据说这题原题最早是**毕克毕姥爷**出的。原题来自雀巢咖啡杯第一场，~~确实是个老题~~。 [原题link](https://max.book118.com/html/2017/0525/109015952.shtm) #### 题面： 您被分配到了火车司机的岗位，尽管您想当文艺工作者，您的任务是去运载被肃反的老布尔什维克，并将他们流放到西伯利亚，因为“要么跟约瑟夫走，要么跟弗拉基米尔走”，尽管工业化的路线是约瑟夫从列夫那里照搬过来的，然而由于列夫被驱逐，去了墨西哥，所以工业化的细节并不优秀，也不够灵活，导致您的火车的车门位置是乱的。 我们可以认为卢卡扬比火车站的站台长度是 L,火车最左侧的门称为第 1 个门,对于满足 1 ≤ I ≤ N 的整数,火车的第 i 个门与第 1 个门之间的距离是 Di ,并且 有 0 = D1 < D2 <...< DN-1 < DN ≤ L。站台上有 M 个乘客,对于满足 1 ≤ I ≤ M 的整数,第 i 个乘客距离站台左边缘的距离为 Pi ,那么有 0 ≤P1 ≤ P2 ≤ … ≤ PM ≤ L。如果火车停在 S 这个位置,也就是说火车的第 1 个门正对着站台的位置距离站台左边缘的距离是 S,那么由于所有的门都要正对站台,显然有 0 ≤ S ≤ L - DN 。此时,火车的第 i 个门正对站台的位置就是 S + D i 。 如果第 i 个乘客从第 j 个门上车,由于火车站巨大（因为有大量人员需要被流放）,门的大小可以忽略不计,那么他需要走的距离就是|Dj + S - Pi |。当然,所有的乘客都会选择需要时间最小的门上车。NKVD向您通报了停靠站台的情况,因为您被要求让乘客尽可能多走路，请你上报使得所有乘客上车距离和最长的停靠位置 S,以及此时所有乘客上车所需的距离总和。 如果存在多种满足条件的停靠方式，请输出S最小的方案。 题面latex炸了，领会精神。 #### 数据范围 对于 30%的数据 L ≤ 100; M ≤ 50; N ≤ 50。 对于 100%的数据 0< L ≤10,0000,0000; M ≤ 300; N ≤ 300。 ------------ ~~苏联笑话永不过时。~~ 看在慈父面子上不上原题面了，反正原题面也没啥意思，感兴趣可以去开头链接自己看。 好像能说的比赛时候都写在代码开头了。。。 ```cpp /* 对于每个人，每次对应一个门。 随着s单调变化，对应的门编号单调递减，所以最多有nm种对应关系 。 考虑上人在门的那个方向，这个也是单调的，又多n种情况。 这东西的答案是个分段函数，最多2nm段。 分段函数变化的时候至少有一个对应关系发生变化，对应关系发生变化的条件是个关于s的不等式，可以直接移项求每个对应关系变化时最小的s。 然后扔到堆里，每次取最小的s，算答案，修改对应状态就ojbk了 算答案的话，分段函数自变量只有一个次数为1的s，根据斜率求最值就行了。 当然也可以直接带入两个端点取max（当时傻了没想到） 然而考场出锅了，炸了一个int，然后整道题都炸了，100->30 行8，我先离开人世了。 考场rush的代码，还是建议看文字领会精神。 */ #include <iostream> #include <queue> #include <algorithm> using namespace std; typedef long long ll; const int kmaxn=300+15; ll dwlx[kmaxn];//达瓦里希 ll glg[kmaxn];//古拉格 ll Len; ll ans; ll anss; int n,m; struct Status{ int pr; int dir;//0 left 1 right or direct//门在人的左/右侧 }; enum DIRECTION{ L,R }; Status st[kmaxn]; priority_queue<pair<ll,int>,vector<pair<ll,int> > ,greater<pair<ll,int> > > q;//所需s值，前进至下一个状态的同志的编号。 ll myabs(ll l) { return l>0?l:-l; } int lb(ll v) { return lower_bound(glg+1,glg+n+1,v)-glg; } ll dir_advance(int p) { ll d=glg[st[p].pr]; return myabs(dwlx[p]-d)+1; } ll sts_advance(int p) { if(st[p].pr<=1)return Len-glg[n]+1; ll x=dwlx[p]; ll a=glg[st[p].pr-1]; ll b=glg[st[p].pr]; return (2*x-a-b+1)/2; } ll sadvance(int p) { if(st[p].dir==L) return dir_advance(p); else return sts_advance(p); } ll cal_num,cal_mul;//常数项，s的系数 void do_advance(int p) { ll d=glg[st[p].pr];//这个d考试时候是int，然后就爆了 if(st[p].dir==L)//dir change { cal_num+=d; cal_num-=dwlx[p]; cal_mul++; st[p].dir=R; cal_num+=d; cal_num-=dwlx[p]; cal_mul++; } else//pair change { st[p].dir=L; cal_num-=d; cal_num+=dwlx[p]; cal_mul--; d=glg[--st[p].pr]; cal_num-=d; cal_num+=dwlx[p]; cal_mul--; } ll t=sadvance(p); q.push(make_pair(t,p)); } int main() { ios::sync_with_stdio(false); cin>>Len>>m; Len*=10; for(int i=1;i<=m;++i) { cin>>dwlx[i]; dwlx[i]*=10; } cin>>n; for(int i=2;i<=n;++i) { cin>>glg[i]; glg[i]*=10; } ll t1,t2; int p; for(int i=1;i<=m;++i)//求初始配对 { t1=t2=Len*m; p=lb(dwlx[i]); if(p<=n)//right or direct t1=myabs(glg[p]-dwlx[i]); --p; if(p>0)//left t2=myabs(glg[p]-dwlx[i]); if(t1<t2)//dwlx glg { st[i].dir=R; st[i].pr=p+1; cal_num+=glg[p+1]; cal_mul++; cal_num-=dwlx[i]; } else//glg dwlx { st[i].dir=L; st[i].pr=p; cal_num-=glg[p]; cal_mul--; cal_num+=dwlx[i]; } } for(int i=1;i<=n;++i)//求每个点状态前进所需的s. { t1=sadvance(i); q.push(make_pair(t1,i)); } ////初始状态答案 ans=0; t1=0; t2=q.top().first-1; ll tans,nows; if(cal_mul>0) nows=t2-1; else nows=t1; tans=cal_mul*nows+cal_num; if(tans>ans){ ans=tans; anss=nows; } while((t1=q.top().first)<=Len-glg[n])//range [t1,t2] { p=q.top().second; q.pop(); while((t2=q.top().first)==t1)//same { do_advance(p); p=q.top().second; q.pop(); } do_advance(p); if(cal_mul>0) nows=t2-1; else nows=t1; tans=cal_mul*nows+cal_num; if(tans>ans){ ans=tans; anss=nows; } } cout<<anss/10<<'.'<<anss%10<<' '<<ans/10<<'.'<<ans%10<<endl; return 0; } /* 样例 4 5 0 1 2 3 4 4 1 2 3 输出 0.5 2.5 */ ``` 时间复杂度nmlog(nm)，约等于n^2logn，上界比较松。 出题的说std是n^3的。 ```cpp using namespace std; int main(){} #include<cstdio> #include<algorithm> #include<cctype> #include<cmath> const double eps=1e-1; struct _Main{ typedef long long ll; template <typename Type> void read(Type &a){ char t; while(!isdigit(t=getchar())); a=t-'0'; while(isdigit(t=getchar())) { a*=10; a+=t-'0'; } } double left; double ans[2]; double calc(){ double ret=0; int i,j,k; j=0; for(i=0;i<m;i++){ while(j+1<n && fabs(d[j+1]+left-p[i])<fabs(d[j]+left-p[i])){ j++; } ret+=fabs(d[j]+left-p[i]); }return ret; } int l,m,n; int p[305],d[305]; _Main(){ double temp; int i,j,k; read(l); read(m); for(i=0;i<m;i++){ read(p[i]); } read(n); for(i=1;i<n;i++){ read(d[i]); } left=0; ans[0]=calc(); ans[1]=left; left=l-d[n-1]; temp=calc(); if(temp>ans[0]){ ans[0]=temp; ans[1]=left; } for(i=1;i<n;i++){ for(j=0;j<m;j++){ left=p[j]-(d[i]-d[i-1])/2.0-d[i-1]; if( left>-eps && (left +d[n-1] < l+eps )){ temp=calc(); if(temp>ans[0]+eps || ((temp>ans[0]-eps) && left<ans[1]-eps)){ ans[0]=temp; ans[1]=left; } } } } printf("%.1lf %.1lf",ans[1],ans[0]); fclose(stdout); } }boat; //反正出题人给的std就是这个，这是个什么东西我也不知道，我也不敢问。 //也不知道能不能运行。 ``` 网上唯一的一篇题解[链接](https://blog.csdn.net/MintGreenTZ/article/details/73159272)，可能也是n^3的（并不确定）。 不知道之前有没有n^2logn做法，按照出题人（**并不是毕克**）的反应，可能是没有。 ~~回头试试卡掉n^3算法把这题再出一遍。~~ 仔细研究了这个优化的原理，准备把总用时最大出成最小值最大/最大值最小。~~然后卡掉n^3。~~