[TIOJ] 1161. 4.虛擬番茄online
題目連結:http://tioj.infor.org/problems/1161
考慮把力量跟敏捷當成兩維把所有技能繪製在平面上,接著用掃描線的概念,從左掃到右,那這時其實就是要對當前的點集尋找第k小,然後跟自己的值加上去。也可以想像成枚舉其中一維的最大值來做計算。而維護點集第k小,其實開個heap維護他的size是k就好了。(我原本寫平衡樹但一直MLE)
考慮把力量跟敏捷當成兩維把所有技能繪製在平面上,接著用掃描線的概念,從左掃到右,那這時其實就是要對當前的點集尋找第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;
}
留言
張貼留言