C++14(g++5.4) 解法, 执行用时: 112ms, 内存消耗: 1504K, 提交时间: 2019-04-17 21:19:04

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
int cmp(P a,P b)
{
	return a.first>b.first;
}
int main()
{
	int n,k;
	cin>>n>>k;
	P a[n];
	for(int i=0;i<n;i++)
		cin>>a[i].first>>a[i].second;
    sort(a,a+n,cmp);
    int res = 0;
    priority_queue<int,vector<int>,greater<int> > q;
    for(int i=0;i<n;++i) 
	{
        q.push(a[i].second);
        if(q.size()>k) 
			q.pop();
        if(q.size()==k){
        	res=max(res,q.top()+a[i].first);		
		} 
    }
    printf("%d\n",res);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 63ms, 内存消耗: 3320K, 提交时间: 2019-05-12 20:32:35

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
pair<int,int> D[N];
int main()
{
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++){
		scanf("%d%d",&D[i].first,&D[i].second);	
	}
	sort(D,D+n);
	priority_queue<int> Q;
	int ans=0;
	for(int i=n-1;i>=0;i--){
		Q.push(-D[i].second);
		if(Q.size()>k){
			Q.pop();
		}
		if(Q.size()==k){
			ans=max(ans,D[i].first+(-Q.top()));
		}	
	}
	printf("%d\n",ans);
	return 0;
}