[TIOJ] 1161. 4.虛擬番茄online

題目連結:http://tioj.infor.org/problems/1161
考慮把力量跟敏捷當成兩維把所有技能繪製在平面上,接著用掃描線的概念,從左掃到右,那這時其實就是要對當前的點集尋找第k小,然後跟自己的值加上去。也可以想像成枚舉其中一維的最大值來做計算。而維護點集第k小,其實開個heap維護他的size是k就好了。(我原本寫平衡樹但一直MLE)
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define FF first
#define SS second

const int INF = 2e9;
const int N = 1000000 + 5;

int n, k;
PII arr[N];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int t;cin>>t;
	while(t--){
		cin>>n>>k;
		for(int i=0;i<n;i++) cin>>arr[i].FF>>arr[i].SS;
		sort(arr,arr+n);
		int ans=INF;
		priority_queue<int> pq;
		for(int i=0;i<n;i++){
			pq.push(arr[i].SS);
			while((int)pq.size() > k)pq.pop();
			if((int)pq.size() == k)
				ans=min(ans, arr[i].FF+pq.top());
		}
		cout<<ans<<'\n';
	}
	return 0;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology