题解：P1315 [NOIP 2011 提高组] 观光公交

Onsin · 2025-03-11 18:01:53 · 题解

贪心，最终复杂度是 O(kn)

一点题外话：当时写题时我还担心 O(kn) 过不了呢，结果交完发现别的题解最坏 O(kn^2) 都过了，~~数据还是比较随和的。~~

分析题意

其实我们可以分三步考虑这个问题：

不接乘客公交车开过全程。
要接完乘客开过全程。
加速后开过全程。

第一种情况只需要知道景点之间的距离 dis[i] 就可以做了，我们用 arrive 数组表示公交车到该点时的绝对时间，arrive 数组的值我们用折线图表示。（数据不重要，随便标） 第二种情况我们要注意，在当前景点的所有人到齐上车之前，车是不能开走的。容易想到用 threshold 数组储存每个景点的最晚到达乘客的到达时间，并表现在图上。
并且很明显 arrive 出发点不能低于 threshold 时间，所以我们需要抬升该出发点。这一做法又会影响后续所有点的 arrive。如图：

我们可以看到折线因此不再连续，我们把不连续的位置称为切断点（其满足 threshold_{i} \ge arrive_{i} ），用 cutPoint 储存，折线图最后变成这样： 最后一种情况最为复杂，我们要使用加速器在最好的那条路上。哪条路最好呢？我们考虑以下过程：（t 为该乘客旅行用时）

t_{i} \gets arrive_{B_{i}}-T_{i}

可以看到其实乘客的旅行时间只取决于其旅行终点的到达时间（T_{i} 恒定），所以我们只需要尽量减少旅行终点的 arrive 即可。我们可以用 welfare 数组记下每个景点是多少乘客的旅行终点，即这个景点的 arrive 减少后能造福多少乘客。
由于减少一条路的 dis 会减少后面一系列景点的 arrive，我们要知道的就是这一个减少区间的 welfare 总和。减少区间有什么特点呢？我们看图：

可以看到，arrive 减少的传递最多只能到达下一个切断点。这张图同样也能告诉我们一个贪心点——在两个切断点之间夹着的一个区间里，加速器越早用越好。显然用在这个区间的无论哪一条路上所产生的 arrive 影响都一定能传递到区间末尾。所以我们可以遍历 cutPoint 然后从那里开始求区间 welfare 和（这里遍历一遍就可以了），最后取最优解。把这个步骤循环 k 次，就可以用完所有的加速器了。每一次用加速器至多把每个景点遍历一遍，故复杂度最坏 O(kn)
但是还有一个点要注意，每一条路 dis \ge 0 ，所以如果 cutPoint 后面的那条路不能使用加速器的话，我们要找到其后面第一个 dis \ge 0 的点。（或者直到下一个切断点，这说明这个区间不可被加速）

我们结合代码把整个过程再过一遍：

首先，我们要从乘客数据中获取每个景点的 threshold 和 welfare

int T[N] , A[N] , B[N];
for( rint i=1; i <= m; ++i ){
    scanf("%d%d%d", T+i , A+i , B+i );
    threshold[ A[i] ] = max( threshold[ A[i] ] , T[i] );
    ++ welfare[ B[i] ];
}

其次，我们跑一遍获得初始 arrive 和 cutPoint

for( rint i=1; i <= n; ++i ){
    arrive[i] = max( arrive[i-1] , threshold[i-1] ) + dis[i-1];
    if( arrive[i] <= threshold[i] ) cutPoint[++p] = i;
}

最后，我们套 k 循环，先找到最适区间，再使用加速器。

while( k-- ){//挂加速器
    int maxn=-1 , tar=0;
    for( rint i=1; i <= p; ++i ){//找到最合适的切断点 
        int pos = cutPoint[i];
        while( !dis[pos] ){//该点不可用加速，找该点后一个 
            ++pos;
            if( arrive[pos]<=threshold[pos] || pos>=n ){//已经找到下一个切断点了，不属于本次循环的范畴 
                pos = -1;
                break;
            }   
        }   
        if( pos == -1 ) continue; //本区间不可加速，尝试下一个切断点 

        int decline=0;//该区间用加速器可以造福多少人（减少多少时间） 
        int ls = pos;//记一下在哪里用的加速器 
        while( ++pos ){//若把加速器用在该点后，能造福多少游客 
            decline += welfare[pos];
            if( arrive[pos]<=threshold[pos] || pos>=n ) break;
        }
        if( maxn < decline )    maxn = decline , tar = ls;//取最大造福点
    }
    -- dis[tar];//确定使用加速器
    while( ++tar ){ 
        -- arrive[tar];
        if( arrive[tar] == threshold[tar] ) cutPoint[++p] = tar;//造出了一个切断点 
        else if( arrive[tar] < threshold[tar] ) break;//本就存在的切断点，即查找时的终止点
    }
}

求出答案，完结。

for( rint i=1; i <= m; ++i )    ans += arrive[ B[i] ]-T[i];

最后是完整的代码。

#include <bits/stdc++.h>
#define N 10002
#define rint register int//有没有不影响 
using namespace std;
int n , m , k;
int dis[N] , arrive[N] , welfare[N] , threshold[N];
int cutPoint[N] , p=1;
long long ans; 

int main(){
    scanf("%d%d%d", &n , &m , &k );
    for( rint i=1; i < n; ++i ) scanf("%d", dis+i );//输入dis 
    int T[N] , A[N] , B[N];
    for( rint i=1; i <= m; ++i ){//输入、预处理乘客数据 
        scanf("%d%d%d", T+i , A+i , B+i );
        threshold[ A[i] ] = max( threshold[ A[i] ] , T[i] );
        ++ welfare[ B[i] ];
    }
    for( rint i=1; i <= n; ++i ){//预处理arrive并且找到切断点 
        arrive[i] = max( arrive[i-1] , threshold[i-1] ) + dis[i-1];
        if( arrive[i] <= threshold[i] ) cutPoint[++p] = i;
    }
    while( k-- ){//挂加速器
        int maxn=-1 , tar=0;
        for( rint i=1; i <= p; ++i ){//找到最合适的切断点 
            int pos = cutPoint[i];
            while( !dis[pos] ){//该点不可用加速，找该点后一个 
                ++pos;
                if( arrive[pos]<=threshold[pos] || pos>=n ){//已经找到下一个切断点了，不属于本次循环的范畴 
                    pos = -1;
                    break;
                }   
            }   
            if( pos == -1 ) continue; //本区间不可加速，尝试下一个切断点 

            int decline=0;  int ls = pos;//记一下在哪里用的加速器 
            while( ++pos ){//若把加速器用在该点后，能造福多少游客 
                decline += welfare[pos];
                if( arrive[pos]<=threshold[pos] || pos>=n ) break;
            }
            if( maxn < decline )    maxn = decline , tar = ls;//取最大造福点
        }
        -- dis[tar];//确定使用加速器
        while( ++tar ){ 
            -- arrive[tar];
            if( arrive[tar] == threshold[tar] ) cutPoint[++p] = tar;//造出了一个切断点 
            else if( arrive[tar] < threshold[tar] ) break;//本就存在的切断点 ，即查找时的终止点
        }
    }
    for( rint i=1; i <= m; ++i )    ans += arrive[ B[i] ]-T[i]; //获得总时间 
    printf("%lld", ans );//完结撒花 
    return 0;
}