TIOJ 1161 4.虛擬番茄online

poao899    1161    Accepted    11748K    1373MS    G++    0.87K    2010-03-31 11:08:14                       .




聽說這題可以線性解O(n)



不過                Heap     O(      n lg n      )              頗直覺

















//**************************************

#include<algorithm>
struct skill{
	int s, a;
	bool operator< (const skill &b)const{return a< b.a;}
	void get(){scanf("%d%d", &s, &a);}
}s[1000010], h[1000010];
bool cmp(skill a, skill b){return a.s< b.s;}
int t, k, n, min, top;
int main(){
	scanf("%d", &t);
	while(t--){
		top= 0; min= 2147483647;
		scanf("%d%d", &n, &k);
		for(int i=0; i<n; i++)
			s[i].get();
		std::sort(s, s+n, cmp);
		for(int i=0; i<n; ){
			int ns= s[i].s;
			while(i<n && s[i].s== ns){
				h[top++]= s[i];
				std::push_heap(h, h+top);
				i++;
			}
			if(top< k)continue;
			while(top> k){
				std::pop_heap(h, h+top--);
			}
			ns+= h[0].a;
			if(ns< min)min= ns;
		}
		printf("%d\n", min);
	}
}