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;
}