[TIOJ 1161] 4.虛擬番茄online

作法：

題目簡單來說就是，給平面上的 n 個點，要求一個點 ( x,y ) 滿足 ( 0,0 ) 和 ( x,y ) 形成的矩形內(含邊界)有 >= k 個點，且 x+y 最小。想法是從小到大枚舉 x ，然後每次求最小的 y 使得它內部有 >= k 個點，而因為比這個點 x 坐標還小的點們，有用的就只有 y 坐標了，所以如果用一個資料結構，裡面裝現在有的 y 坐標們，然後每次要查詢的就是第 k 小的數。但因為 k 是固定的，所以只要用一個 multiset 加上當元素個數 > k 的時候把最大的丟掉，每次取 multiset 裡面的最大值即可。

code :

#include<bits/stdc++.h>
#define lowbit(x) (x&-x)
#define pii pair<int,int>
#define F first
#define S second
#define mkp(x,y) make_pair(x,y)
#define INF 10000000
using namespace std;
const int maxn=1000000+10 ;
 
int n ;
pii a[maxn] ;
multiset<int,greater<int> > mst ;
 
main()
{
    int T ; scanf("%d",&T) ;
    while(T--)
    {
        int k ; scanf("%d%d",&n,&k) ;
        for(int i=0;i<n;i++) scanf("%d%d",&a[i].F,&a[i].S) ;
        sort(a,a+n) ;
        mst.clear() ;
        int ans=INF ;
        for(int i=0;i<n;)
        {
            int i2 ;
            for(i2=i;i2<n && a[i2].F==a[i].F;i2++)
            {
                mst.insert(a[i2].S) ;
                if(mst.size()>k) mst.erase(mst.begin()) ;
            }
            i=i2 ;
            if(i>=k) ans=min(ans,a[i-1].F+(*mst.begin())) ;
        }
        printf("%d\n",ans) ;
    }
}