题解 P5661 【公交换乘【民间数据】】

· · 题解

CSP-J 2019 T2 Transfer 交通换乘题解

这道题表面看着比较乱，实际只要理清思路，就非常的简单

本题重点：优惠票 可使用队列进行储存

头文件、命名空间不用说，如下

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

进入主函数，第一步：创建变量、队列

分别创建：

第一行，乘车记录的数量（n）

第二行，交通工具（g）、票价（p）、时间（t）

第三行，总花费（sum）

第四行，优惠票总数（ques）

第五行，优惠票时间队列（q1）

第六行，优惠票价钱队列（q2）

    long long n ;
    long long g[100010] , p[100010] , t[100010] ;
    long long sum = 0 ;
    long long ques = 0 ;
    queue<long long>q1 ;
    queue<long long>q2 ;

第二步，依次循环各条记录

先输入记录的条数（n）

    cin >> n ;

开始循环

    for ( int i = 1 ; i <= n ; i++ ){

输入三项数值（gpt）

        cin >> g[i] >> p[i] >> t[i] ;

第三步，判断地铁

先判定地铁（g为0）

        if ( g[i] == 0 ){

因为地铁一定要花钱，所以将总花费（sum）加上票价（p）

坐地铁一定会拿到一张优惠票，我们将优惠票的时间压入时间队列（q1），将票价压入价钱队列（q2），并将优惠票的数量（ques）加1

            sum += p[i] ;
            q1.push(t[i]) ;
            q2.push(p[i]) ;
            ques++ ;

第四步：筛除废票

当优惠票超过45时间后，该优惠票就会失效，因为队列FIFO的特性，只要队首的那张没超时，就代表后面的都没超时。因此使用while循环（附加非空判定以防万一）

        while ( t[i] - q1.front() > 45 && !q1.empty() ){

只要循环进去了，说明这张票废了，把两个队列（q1q2）的队首都弹出，并把优惠票数量（ques）减1

            q1.pop() ;
            q2.pop() ;
            ques-- ;

第五步：判断公交

这一步是最难的，因为在优惠票的选择上有一点绕，我们一步一步来

创建两个变量：优惠票使用状态（f）和优惠票备用数量（quesd）备用

        long long f = 0 ;
        long long quesd = ques ;

判定公交（g为1）

        if ( g[i] == 1 ){

接下来为保险起见分为有优惠票（优惠票队列（q1q2）非空）和无优惠票（优惠票队列（q1q2）为空）两种情况考虑。先写出判断语句

            if ( !q1.empty() ){

当无优惠票时，无论如何都要花钱，所以先不管if里面的，直接在下面打else，else里面将总花费（sum）加上票价（p）。注意：一定要加上一个continue以直接进行下次循环，在后面会说为什么

            else{
                sum += p[i] ;
                continue ;
            }

接下来进入重头戏，就是当有优惠票时，因为优惠票可能会不能用，而且没有规律（不像时间队列（q1）有规律），在这里所有的优惠票肯定都不会超时（超时的全弹出去了）。我们在这里使用这样的方法：把队列（q1q2）从头到尾检索一次，即使已经有符合的了也要全检索完（因为优惠票需要按时间顺序排列，其顺序不能更改）。如何检索呢？只需要把队首压入队尾，再把队首弹出就可以了，这样第一位就会变到最后一位，第二位变到第一位，以此类推。当全部走完后，第一位又会变回第一位。

首先，进行循环

                for ( int j = 1 ; j <= quesd ; j++ ){

为什么这里要用备用数量（quesd）呢？因为假设有优惠票被使用，那么此票就会被弹出，数量（ques）会减1（参见上文第四大步），因为数量会变，所以需要存一个固定的值，也就是quesd

紧接着分两种情况，一种是该票可以使用，一种是该票不能使用。可以使用即是价钱队列（q2）的队首大于等于乘坐此次公交所花的钱，不可以使用则反之。为判断方便，以可以使用为条件，不可以使用为该条判断的else

                    if ( f == 0 && p[i] <= q2.front() ){

此处的使用状态（f）为后期进行判定时使用，f为0表示本轮还没有使用优惠票，f为1表示本轮使用了优惠票

当满足条件时，表示可以使用优惠票，f的值改为1，并将该票弹出队列（q1q2），优惠票数量（ques）减1

                        f = 1 ;
                        q1.pop() ;
                        q2.pop() ;
                        ques-- ;

当不满足条件时，把队首压入队尾，把队首弹出，达到循环效果

                    else{
                        q1.push(q1.front()) ;
                        q2.push(q2.front()) ;
                        q1.pop() ;
                        q2.pop() ;
                    }

之后跳出整个 if ( !q1.empty() ){ 及其附带的else语句，判断假设没有使用优惠票（f为0），总花费（sum）加上票价（p）

            if ( f == 0 ){
                sum += p[i] ;
            }

队列（q1q2）为空的else语句中的continue就是为了防止进行二次判定

第六步：输出

很简单不用多说

    cout << sum ;

别忘了加上

    return 0 ;

放出AC（貌似）代码

仅供参考、理解，禁止复制、抄袭！

/*
    Name: Transfer
    Copyright: No
    Author: ThaiMinda Simens
    Date: 16/11/19
    Description: CSP-J 2019 T2
*/
#include <iostream>
#include <cmath>
#include <cstring>
#include <bits/stdc++.h>
#include <cstdio>
using namespace std ;
long long n ;
long long g[100010] , p[100010] , t[100010] ;
long long sum = 0 ;
long long ques = 0 ;
int main(){
    freopen("transfer.in","r",stdin) ;
    freopen("transfer.out","w",stdout) ;
    queue<long long>q1 ;
    queue<long long>q2 ;
    cin >> n ;
    for ( int i = 1 ; i <= n ; i++ ){
        cin >> g[i] >> p[i] >> t[i] ;
        if ( g[i] == 0 ){
            sum += p[i] ;
            q1.push(t[i]) ;
            q2.push(p[i]) ;
            ques++ ;
        }
        while ( t[i] - q1.front() > 45 && !q1.empty() ){
            q1.pop() ;
            q2.pop() ;
            ques-- ;
        }
        long long f = 0 ;
        long long quesd = ques ;
        if ( g[i] == 1 ){
            if ( !q1.empty() ){
                for ( int j = 1 ; j <= quesd ; j++ ){
                    if ( f == 0 && p[i] <= q2.front() ){
                        f = 1 ;
                        q1.pop() ;
                        q2.pop() ;
                        ques-- ;
                    }
                    else{
                        q1.push(q1.front()) ;
                        q2.push(q2.front()) ;
                        q1.pop() ;
                        q2.pop() ;
                    }
                }
            }
            else{
                sum += p[i] ;
                continue ;
            }
            if ( f == 0 ){
                sum += p[i] ;
            }
        }
    }
    cout << sum ;
    return 0 ;
}