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