UVa-1203, POJ-2051, ZOJ-2212, LiveArchive-3135, TJU-1093 : Argus
問題概要
(A[i]*k, B[i])(k in [1,inf) i in [1..N(<1000)])をソートしたときの上からK(<10^4)個を求める問題。
解法
優先順位付きキューから取り出しては時間を進めて再び突っ込んでいく。
acceptされたコード
計算量O(K * log N + N)。
#include <cstdio> #include <cstring> #include <queue> using namespace std; const int MAX_N = 1000; int N, K; struct query{ int id, interval, cur; }; query qs[MAX_N]; bool operator<(const query& lhs, const query& rhs){ return lhs.cur != rhs.cur ? lhs.cur > rhs.cur : lhs.id > rhs.id; } void init(){ char buf[16]; N = 0; while(scanf("%s ", buf)){ if(!strcmp(buf, "#")){ break; } int id, term; scanf("%d %d ", &id, &term); qs[N++] = (query){id, term, term}; } scanf("%d", &K); } void solve(){ priority_queue<query> que(qs, qs+N); for(int i=0; i<K; i++){ query tp = que.top(); que.pop(); printf("%d\n", tp.id); tp.cur += tp.interval; que.push(tp); } } int main(){ init(); solve(); return 0; }