C++ 基礎題 TIOJ 1161 虛擬番茄

用heap(priority_queue)實作

#include<bits/stdc++.h>
using namespace std;
#define INF 100000000
#define P pair<int,int>
#define F first
#define S second
#define PB push_back

P sl[1000000];

int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    
    int t;
    cin>>t;
    for(int iptNum=0;iptNum<t;iptNum++){
        int n,k,r=INF;
        
        priority_queue<int> pq;
        
        cin>>n>>k;
        for(int i=0;i<n;i++){
            cin>>sl[i].F>>sl[i].S;
        }
        
        sort(sl,sl+n);
        
        for(int i=0;i<n;i++){
            pq.push(sl[i].S);
            if(pq.size()==k){
                r=min(r,sl[i].F+pq.top());
                pq.pop();
            }
        }
        cout<<r<<"\n";
    }
    return 0;
}

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *