题解 P1315 【观光公交】

· · 题解

2024/6/10: 很久以前写的题解不知为什么被打回了。。

立志写一篇明明白白且老少咸宜的贪心题解

本题的思维含量特别大，蒟蒻作者和同学讨论了好几天才把这道题整明白...

首先看题。题目内容特别冗长，认真读题后，可以发现对本题的处理可分以下几个步骤：

  1. 读入数据

  2. 规划出不用氮气加速时公交车的行驶过程

  3. 找一段区间，使得在这个区间使用氮气加速时，能使最多的乘客旅行时间缩短；本步骤重复 k 次

  4. 输出答案

本题的规划过程比较复杂。现对步骤 2 进行叙述。

对于第一个景点，我们已经知道了公交车抵达第一个景点的时间（即第 0 分钟）。按照题意，公交车必须等到从第一个景点上车的最后一个乘客到达后才能从第一个景点离开。记 Latest_i 为第i个景点最后一名乘客抵达该站点的时间。如果 Latest_1\le0，那么离开第一个景点的时间就是 0；如果 Latest_1>0，离开第一个景点的时间就是 Latest_1。

那么，对于第二个景点，抵达第二个景点的时间就是离开第一个景点的时间加 D_1。按照第一个景点递推的方式，我们可以规划出公交车初始的行驶过程。

假如公交车到达第 i 个景点时，仍有乘客尚未到达第 i 个景点，此时公交车将留在第 i 个景点，直到最后一个乘客上车。如果到达第 i 个景点时已不再是“车等人”而是“人等车”，此时公交车可以直接离开第 i 个景点。

在递推到每个景点时，记录到达第 i 个景点的时间为 Arrive_i。

int time=0;
for(register int i=1;i<=N;++i)
{
    Arrive=time;
    time=max(time,Latest[i]);
    time+=D[i];
}

进行完预处理，即可枚举所有的区间，并找出在每个区间使用氮气加速可以惠及多少乘客。不难发现，如果到达第 i 个景点的时间提前（即从第 i-1 个景点出发的时间提前），那么从第 i 个景点下车的乘客旅行时间都将减一。但关键点是，如果到达第 i 个景点的时间提前，也有可能对到达第 i+1 个景点的时间产生影响。

那么我们可以分情况讨论。如果 Arrive_i>Latest_i，并且在 D_i 区间使用氮气加速，Arrive_i 将减少 1，离开第 i 个景点的时间也将减 1，继续进行下一个景点的讨论；如果 Arrive_i\le Latest_i，Arrive_i 将减少 1，此时为了照顾最后一名乘客，离开第 i 个景点的时间不变，因此也不必对后面的景点进行讨论。每讨论到一个景点 i，表示到达第 i 个景点的时间将减 1，那么惠及的总人数便要加上从第 i 个景点下车的人数。

简单总结一下：如果在当前 Arrive 值减一后，出现“人等车”的情况，则说明下一个 Arrive 值也将减小，继续循环；如出现“车等人”的情况，则说明离开当前景点的时间不会更新，后续的 Arrive 值均不受影响，故跳出循环。

像这样枚举每个区间后，记录惠及人数最多的区间位置。

max_num=0;
for(register int i=2;i<=N;++i)
{
    if(!D[i-1]) continue;
    tmp_num=0;
    for(register int j=i;j<=N;++j)
    {
        tmp_num+=Leave[j];
        if(Arrive[j]<=Latest[j]) break;
    }
    if(tmp_num>max_num)
    {
        max_num=tmp_num;
        max_pos=i;
    }
}

记录下位置后，便可以对 Arrive 和 D 数组进行更新。更新方式与枚举区间方式类似，请自行体会。

D[max_pos-1]--;
for(register int i=max_pos;i<=N;++i)
{
    Arrive[i]--;
    if(Arrive[i]<Latest[i]) break;
}

将以上两段操作重复 k 次，便得到更新后的 Arrive 数组。根据每一个乘客旅行开始的时间和下车的景点，计算出 ans 即可。

标程如下：

#include<bits/stdc++.h>
using namespace std;

int N,M,K;
struct passenger
{
    int start,end;
}pas[100005];
struct station
{
    int off,latest,arrive;
}sta[1005];
int Dist[1005];

int main()
{
    scanf("%d%d%d",&N,&M,&K);
    for(register int i=1;i<N;++i) scanf("%d",&Dist[i]);
    int t;
    for(register int i=1;i<=M;++i)
    {
        scanf("%d%d%d",&pas[i].start,&t,&pas[i].end);
        sta[t].latest=max(sta[t].latest,pas[i].start);
        sta[pas[i].end].off++;
    }
    int time=0;
    for(register int i=1;i<=N;++i)
    {
        sta[i].arrive=time;
        time=max(time,sta[i].latest);
        time+=Dist[i];
    }
    int max_num,max_pos,tmp_num;
    while(K--)
    {
        max_num=0;
        for(register int i=2;i<=N;++i)
        {
            if(!Dist[i-1]) continue;
            tmp_num=0;
            for(register int j=i;j<=N;++j)
            {
                tmp_num+=sta[j].off;
                if(sta[j].arrive<=sta[j].latest) break;
            }
            if(tmp_num>max_num)
            {
                max_num=tmp_num;
                max_pos=i;
            }
        }
        Dist[max_pos-1]--;
        for(register int i=max_pos;i<=N;++i)
        {
            sta[i].arrive--;
            if(sta[i].arrive<sta[i].latest) break;
        }
    }
    int ans=0;
    for(register int i=1;i<=M;++i)
        ans+=sta[pas[i].end].arrive-pas[i].start;
    printf("%d",ans);
    return 0;
}