資訊學奧賽一本通 1983：【19CSPJ普及組】公交換乘

【題目連結】

ybt 1983：【19CSPJ普及組】公交換乘

【題目考點】

1. 模拟

【解題思路】

• 設定數組tk儲存優惠票，優惠票的屬性有：獲得時間，價格。

  設下标st，tk[st]是目前時間下，時間最早的有效的票。當i<st時tk[i]是過期的票。當i>=st時，tk[i]是有效的票。

• 循環輸入資料
  • 如果是乘坐地鐵，那麼添加一張優惠票
  • 如果是乘坐公交
    • 先更新st的值
    • 從st位置開始周遊數組tk，尋找第一個價格高于目前公交票價的優惠票，使用該優惠票。

• 算法複雜度分析

  因為每次獲得優惠票的時間是有序的，因而設定變量st，每次從st開始周遊。相比于每次從頭周遊，這樣做可以減少對無效票的周遊，降低時間複雜度。

  tk[st]的獲得時間到目前時間最多45分鐘，題中指出“不會有兩次乘車記錄出現在同一分鐘”，因而有效的優惠票不會超過45個，每次周遊有效優惠票的循環次數不會超過45次。

  整個程式的複雜度為O(45*n) = O(n)

【題解代碼】

解法1：

#include <bits/stdc++.h>
using namespace std;
#define N 100005
typedef struct Ticket
{
    int time;//time:獲得票的時間 
    int price;//price:買地鐵票時的價格，即價格小于等于price的公共汽車可以用這張票 
    bool isUsed;//标記這張票是否使用過 
    Ticket(){}
    Ticket(int a, int b):time(a),price(b),isUsed(false){}
}Ticket;
Ticket tk[N];//儲存生成的票
int tk_i, st;//tk_i:記錄tk數組中待存儲的位置 st: i >= st時，tk[i]是有效的票，i < st時，tk[i]是過期的票 
int main()
{
    int n, cost = 0, type, price, time;// cost:總花費 
    cin>>n;
    for(int i = 0; i < n; ++i)
    {
        cin>>type>>price>>time;
        if(type == 0)//地鐵
        {
            tk[tk_i++] = Ticket(time, price);//添加優惠票      
            cost += price;
        }
        else//公交 
        {
            while(st < tk_i && time - tk[st].time > 45)//更新過期票和有效票的分界點，使tk[st]是最早的有效的票 
                st++;
            bool usedTk = false;//是否使用了優惠票    
            for(int j = st; j < tk_i; ++j)//搜尋優惠票，看能用哪張。循環次數不會超過45次。 
            {
                if(tk[j].price >= price && tk[j].isUsed == false)//如果這張票标價比公交票價高，且沒用過，那麼可以用。 
                {
                    usedTk = true;
                    tk[j].isUsed = true;
                    break;
                }
            }
            if(usedTk == false)
                cost += price;
        }
    }
    cout<<cost;
    return 0;
}