题解 | #[CSP2019]公交换乘#环形数组解法

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

struct go_log{
    int tool;
    int price;
    int time;
};

int main(){
    int n = 0;
    cin >> n;
    
    int queue_max = 50;
    go_log gl_list[queue_max];

    int l = 0; //left point to subway
    int r = 0; //right point to subway
    int price_min = 0;
    
    for(int i = 0; i < n; i++){
        go_log gl;
        cin >> gl.tool >> gl.price >> gl.time;

        //remove > 45 mintue
        while(r > l){
           if((gl.time - gl_list[l % queue_max].time) <= 45) break;
           l = l + 1;
        }

        //subway
        if(gl.tool == 0){
            gl_list[r % queue_max] = gl;
            r = r + 1;
        }
        
        //bus
        if(gl.tool == 1){
            //has ticket in queue ?
            for(int k = l; k < r; k++){
                if(gl_list[k % queue_max].price >= gl.price){
                    gl.price = 0;
                    gl_list[k % queue_max].price = -1; //it is not use
                    break;
                }  
            }
        }
        
        price_min = price_min + gl.price;      
        //printf("[%d][%d][%d]\n", i + 1, gl.tool, gl.price);
    }
    
    cout << price_min << endl;
    return 0;
}