洛谷P5661 公交換乘（CSP-J 2019 T2）

傳送門

題目可能排版有問題，導致出現一些亂碼，具體請參考洛谷原題

題目描述

著名旅游城市 B 市為了鼓勵大家采用公共交通方式出行，推出了一種地鐵換乘公交車的優惠方案：

1. 在搭乘一次地鐵后可以獲得一張優惠票，有效期為 45 分鐘，在有效期內可以消耗這張優惠票，免費搭乘一次票價不超過地鐵票價的公交車，在有效期內指開始乘公交車的時間與開始乘地鐵的時間之差小于等于 45 分鐘，即： t_{bus} - t_{subway} \leq 45tbus??tsubway?≤45
2. 搭乘地鐵獲得的優惠票可以累積，即可以連續搭乘若干次地鐵后再連續使用優惠票搭乘公交車，
3. 搭乘公交車時，如果可以使用優惠票一定會使用優惠票；如果有多張優惠票滿足條件，則優先消耗獲得最早的優惠票，

現在你得到了小軒最近的公共交通出行記錄，你能幫他算算他的花費嗎?

輸入格式

輸入檔案的第一行包含一個正整數 nn，代表乘車記錄的數量，

接下來的 nn 行，每行包含 3 個整數，相鄰兩數之間以一個空格分隔，第 ii 行的第 1 個整數代表第 ii 條記錄乘坐的交通工具，0 代表地鐵，1 代表公交車；第 2 個整數代表第 ii 條記錄乘車的票價 price_ipricei? ；第三個整數代表第 ii 條記錄開始乘車的時間 t_iti?（距 0 時刻的分鐘數），

我們保證出行記錄是按照開始乘車的時間順序給出的，且不會有兩次乘車記錄出現在同一分鐘，

輸出格式

輸出檔案有一行，包含一個正整數，代表小軒出行的總花費，

輸入輸出樣例

6
0 10 3
1 5 46
0 12 50
1 3 96
0 5 110
1 6 135

36

6
0 5 1
0 20 16
0 7 23
1 18 31
1 4 38
1 7 68 

32

說明/提示

【輸入輸出樣例 1 說明】

第一條記錄，在第 3 分鐘花費 10 元乘坐地鐵，

第二條記錄，在第 46 分鐘乘坐公交車，可以使用第一條記錄中乘坐地鐵獲得的優惠票，因此沒有花費，

第三條記錄，在第 50 分種花費 12 元乘坐地鐵，

第四條記錄，在第 96 分鐘乘坐公交車，由于距離第三條記錄中乘坐地鐵已超過 45 分鐘，所以優惠票已失效，花費 3 元乘坐公交車，

第五條記錄，在第 110 分鐘花費 5 元乘坐地鐵，

第六條記錄，在第 135 分鐘乘坐公交車，由于此時手中只有第五條記錄中乘坐地鐵獲得的優惠票有效，而本次公交車的票價為 6 元，高于第五條記錄中地鐵的票價 5 元，所以不能使用優惠票，花費 6 元乘坐公交車，

總共花費 36 元，

【輸入輸出樣例 2 說明】

第一條記錄，在第 1 分鐘花費 5 元乘坐地鐵，

第二條記錄，在第 16 分鐘花費 20 元乘坐地鐵，

第三條記錄，在第 23 分鐘花費 7 元乘坐地鐵，

第四條記錄，在第 31 分鐘乘坐公交車，此時只有第二條記錄中乘坐的地鐵票價高于本次公交車票價，所以使用第二條記錄中乘坐地鐵獲得的優惠票，

第五條記錄，在第 38 分鐘乘坐公交車，此時第一條和第三條記錄中乘坐地鐵獲得的優惠票都可以使用，使用獲得最早的優惠票，即第一條記錄中乘坐地鐵獲得的優惠票，

第六條記錄，在第 68 分鐘乘坐公交車，使用第三條記錄中乘坐地鐵獲得的優惠票，

總共花費 32 元，

【資料規模與約定】

對于 30\%30% 的資料，n \leq 1000n≤1000，t_i \leq 10^6ti?≤106，

另有 15\%15% 的資料，t_i \leq 10^7ti?≤107，price_ipricei? 都相等，

另有 15\%15% 的資料，t_i \leq 10^9ti?≤109，price_ipricei? 都相等，

對于 100\%100% 的資料，n \leq 10^5n≤105，t_i \leq 10^9ti?≤109，1 \leq price_i \leq 10001≤pricei?≤1000，

關于考試

本蒟蒻恨在ZJ，只能考個J組 QWQ

考試的時候一個break忘打了，調了半天，嚇死laozi了

T1是真的水，比去年還要水（盡管我去年復賽都沒進QWQ）

T2還好吧，結構體佇列比較容易想到

T3，，一眼看還以為是DP，調了半天出不來，只好放棄，騙了10分QWQ（才知道是完全背包）

T4蒟蒻根本沒想到奇偶數最短路，寫暴搜騙了40

總體和去年差不多，感覺第四題比較好騙分

ZJ CSP-J 250，還不能保證檔案問題，，，

自閉中QWQ

言歸正傳

T2我覺得比較容易想到結構體+佇列，看到別的dalao開兩個結構體，本蒟蒻參不透啊！我就開了一個，寫法和樓上有點類似，又有點不一樣，

****大致思路是，每次讀入，先去掉過期地鐵票，若乘地鐵，直接付錢，資訊入隊，若乘公交車，掃一遍佇列，找到符合要求的第一張票，并整理佇列；若沒有優惠，付錢吧，

貼上代碼：

#include<bits/stdc++.h>
using namespace std;
struct node{
    int a,pr,t;//a交通工具，pr即price價格，t時間 
}szh[100005];//結構體 
node q[100005];//結構體佇列，比較方便 
int n,head,tail,ans;//隊頭隊尾 ，隊首是q[head+1],隊尾是q[tail] ,非常關鍵 
int main()
{
    //freopen("transfer.in","r",stdin);
    //freopen("transfer.out","w",stdout);//剛考完，檔案不知道有沒有打錯，心慌慌，，，， 
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&szh[i].a,&szh[i].pr,&szh[i].t); 
        while(head<tail){//從隊頭開始掃，當發現時間相差>45，出隊，否則退出 ，注意不是<=  
            if(szh[i].t-q[head+1].t>45)
            head++;
            else break;//考試的時候break沒加，無限回圈，運行錯誤，慌得一比 ，查了半小時，，， 
        }
        if(szh[i].a==0){//乘地鐵，入隊，價格計入答案 
            ans+=szh[i].pr;
            q[++tail]=szh[i];
        }
        else{//公交車，分類討論 
            if(head==tail){//如果佇列為空，則價格計入答案 
                ans+=szh[i].pr;
            }
            else{//佇列不為空,掃描一遍 
                int p=head;// head在掃描程序中不能變，所以定義一個指標 
                int f=0;//flag標記 
                while(p<tail){//注意不是<=
                    if(q[p+1].pr>=szh[i].pr){//如果找到佇列中地鐵票價高于當前公交車票價，停止掃描,免費 
                        for(int j=p+1;j>=head+2;j--)//j的范圍需要仔細思考，模擬 
                        q[j]=q[j-1];//p+1之前的都前進一個單位 
                        f=1;//標記，表示已掃到符合要求
                        head++;//佇列長度-1 
                        break;//退出回圈 
                    }
                    else{
                        p++;//再往前掃 
                        continue;//進入下一次回圈（現在才發現是廢話） 
                    }
                }
                if(f==0) ans+=szh[i].pr;// 如果沒有符合要求的地鐵票，乖乖掏出錢包 
            }
        }
    }
    printf("%d",ans);//Van美 
    return 0;
}

本蒟蒻不會算復雜度，望大佬告知

PS：那個大樣例好像出問題了，題目里給的10^5，大樣例居然有10^6，還沒有換行（同學說是格式問題），就炸了

后記：

2019.11.17：成為本蒟蒻在洛谷第一篇通過的題解

2019.11.18：發現了一些檔案問題，檔案夾多嵌套一個，導致250直接爆零，當場吐血

標籤：其他

上一篇：歸并排序演算法

下一篇：二維陣列中的查找