[POI2014]Freight

题目大意：
　　有两个城镇$A$和$B$，有$n(n\le10^6)$辆车从$A$地出发前往$B$再返回$A$地。两地之间的行驶时间为$s(s\le10^9)$，每辆车从$A$地出发的最早时间是$t_i(0\le t_1\le t_2\le\ldots\le t_n\le10^9)$。行驶过程中需要保证每辆车出发时间至少相差$1$，且每个时刻运行的车都是同一个方向，问所有车都返回$A$地至少需要多少时间？

思路：
　　“行驶过程中需要保证每辆车出发时间至少相差$1$”相当于令$t_i=\max(t_i,t_{i-1}+1)$。
　　“每个时刻运行的车都是同一个方向”说明我们只需要对这些车分批，一批往返结束后下一批开始往返（一批车留在$B$地，另一批从$A$地过来一定存在一种等价的方案使得第一批往返完成后第二批出发）。
　　有了以上两个信息，不难得到状态转移方程$f_i=\min\{\max(t_i,f_j+i-j-1)+2s+i-j-1\}$。
　　由于$f_j+i-j-1$是单调递增的，所以$\max(t_i,f_j+i-j-1)$中一定可以找到一个转折点$j$使得$j$的左边取到$t_i-i$，右边取到$f_j-j-1$。左边是定值因此$j$越大越好，右边相当于求区间$[j,i)$的最小值，用树状数组维护即可，时间复杂度$O(n\log n)$。已经能AC了。
　　事实上，因为$f_i$的增长速度$\ge2i$，所以取最左边即转折点的一定更优，这样就可以省掉树状数组。考虑到转折点位置是单调递增的，因此只需要每次把上一次的转折点位置记录下来，累加到当前转折点即可。时间复杂度$O(n)$。

 #include<cstdio>

 #include<cctype>

 #include<climits>

 #include<algorithm>

 typedef long long int64;

 inline int getint() {

     register char ch;

     while(!isdigit(ch=getchar()));

     register int x=ch^'';

     while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');

     return x;

 }

 const int N=1e6+;

 int t[N]={-};

 int64 f[N];

 int main() {

     const int n=getint(),s=getint();

     for(register int i=,j=;i<=n;i++) {

         f[i]=LLONG_MAX;

         t[i]=std::max(getint(),t[i-]+);

         for(j--;j<i&&std::max((int64)t[i],f[j]+i-j-)+s*+i-j-<f[i];j++) {

             f[i]=std::max((int64)t[i],f[j]+i-j-)+s*+i-j-;

         }

     }

     printf("%lld\n",f[n]);

     return ;

 }

巴特西

[POI2014]Freight

最新文章

热门文章