UVAILIVE-3135 Ags優先列

1931 ワード

ACM-データ構造

各フリップフロップには番号と間隔があります.その後、トリガーイベントによって前のkのフリップフロップの番号を出力してください.トリガ時間が同じなら、番号の小さいのを出力します.
問題解決の考え方:優先列のテンプレート問題

#include
#include
using namespace std;
struct Item {
    int QNum, Period, Time;
    bool operator < (const Item &s) const {
        return Time > s.Time || (Time == s.Time && QNum > s.QNum);  
    }
};
int main() {
    priority_queue pq;
    char temp[20];
    while(scanf("%s",temp) != EOF && temp[0] != '#') {
        Item item;
        scanf("%d%d",&item.QNum,&item.Period);
        item.Time = item.Period ;
        pq.push(item);
    }
    int K;
    scanf("%d",&K);
    while(K--) {
        Item t = pq.top();
        pq.pop();
        printf("%d
",t.QNum);
        t.Time += t.Period;
        pq.push(t)  ;
    }
    return 0;
}

hrbustoj 1551:基礎データ構造——文字列2ウイルスII(文字列マッチング、BMアルゴリズム練習)