题解：P5661 [CSP-J2019] 公交换乘

__Aha__ · 2024-12-25 15:55:31 · 题解

思路

模拟题。

在《深入浅出基础版》中介绍过这类题目，这类题目一般只需按照题意模拟，特殊情况时需要使用数据结构及优化。

思路也很简单，直接暴力，乘坐地铁时，花费价格直接加到总和。

否则往前枚举，首先，如果时间相差超过 45 分钟，直接结束。之后判断：如果乘坐的是地铁，花费的价格更高，且优惠卷没被使用，那就使用优惠卷，否则原价购买。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,ans,b[100005],mi;
struct kun{
    long long p,t;// price 价格，time 时间
    bool c;//c 乘车种类
}a[100005];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].c>>a[i].p>>a[i].t;
        b[i]=1;//标记优惠卷未使用。
    } 
    for(int i=1;i<=n;i++){
        if(a[i].c==0) ans+=a[i].p;//如果是地铁直接坐。
        else{//如果是公交车，考虑使用优惠卷。
            mi=-1;
            for(int j=i-1;j>=1;j--){//枚举他前面的乘车记录。
                if(a[i].t-a[j].t>45) break;
                if(a[j].p>=a[i].p&&a[j].c==0&&b[j]==1){
                    mi=j;
                }//满足要求。
            }
            if(mi==-1) ans+=a[i].p;
            else b[mi]=0;   //记得标记已使用。
        }       
    }
    cout<<ans;
    return 0;
}