P1315 [NOIP 2011 提高组] 观光公交 completed!

Wild_Of_The_World · 2025-02-16 16:54:45 · 个人记录

费劲千辛万苦终于过了！！！

正解还是很好想的，每次选会对总时间影响最大的边去加速就好了。

然后是每条边加速后的影响，从这个角度去想,想清楚了这道题就差不多拿下了。

问题在于我想到正解后，代码好久都没写出来，卡在了下面注释的地方QAQ。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,k,d[N];
struct people{
    int time,t;
}p[N];
int down[N],arrive[N],late[N];
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<n;i++) cin>>d[i];
    int t;
    for(int i=1;i<=m;i++){
        cin>>p[i].time>>t>>p[i].t;
        down[p[i].t]++;
        late[t]=max(late[t],p[i].time);
    }
    int time=0;
    for(int i=1;i<=n;i++){
        arrive[i]=time;
        time=max(time,late[i]);
        time+=d[i]; 
    }
    int max_time,aim,js;
    while(k--){
        max_time=0;
        for(int i=2;i<=n;i++){
            if(!d[i-1]) continue;
            js=0;
            for(int j=i;j<=n;j++){
                js+=down[j];
                if(arrive[j]<=late[j]) break;
            }
            if(js>max_time){
                max_time=js;
                aim=i;
            }
        }
        d[aim-1]--;
        for(int i=aim;i<=n;i++){
            arrive[i]--;
            if(arrive[i]<late[i]) break;        //此处是已经加速后的，如果加速后相等的话那离开时间也是比一开始早了一秒 
//          if(arrive[i]<=late[i]){
//              arrive[i]--;
//              break;
//          }
//          arrive[i]--;
        }
    }
    int ans=0;
    for(int i=1;i<=m;i++){
        ans+=arrive[p[i].t]-p[i].time;
    }
    cout<<ans<<endl;

    return 0;
}