C++ 解法, 执行用时: 36ms, 内存消耗: 3468KB, 提交时间: 2020-10-03

/**
 * @Author:      G_bg
 * @DateTime:    2020-10-03 14:37:03
 * @Description: 
 */
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const double PI = 3.14159265358979323846264338327950288419;
const double E = 2.718281828459;
const int INF = 0x7fffffff;
const int mod = 1e9+7;
const int maxn = 1e3+10;
struct node{
	int x,type;
	node(int x,int type):x(x),type(type){}
};
struct cmp{
	bool operator()(const node& a,const node& b)const{
		return a.x > b.x;
	}
};
priority_queue<node,vector<node>,cmp> px;
int main(int argc, const char *argv[]) {
	ios::sync_with_stdio(0);cin.tie(0);
	int k,n;cin >> k >> n;
	vector<vector<int>> a(k+1,vector<int>(n+1));
	for(int i = 1;i <= k;++i){
		for(int j = 1;j <= n;++j){
			cin >> a[i][j];
		}
	}
	int mi = a[1][1],ma = a[1][1];
	for(int i = 1;i <= k;++i){
		node tmp = {a[i][++a[i][0]],i};
		px.push(tmp);
		mi = min(mi,tmp.x);
		ma = max(ma,tmp.x);
	}
	int maa = ma;
	while(px.size() == k){
		node tmp = px.top();px.pop();
		int type = tmp.type;
		if(a[type][0] < n){
			node add = {a[type][++a[type][0]],type};
			px.push(add);
			int mii = px.top().x;
			maa = max(maa,add.x);
			//cout << "mi" << mi << " " << ma << endl;
			//cout << "mii" << mii << " " << maa << endl;
			if(maa-mii < ma-mi){
				mi = mii;
				ma = maa;
			}
		}
	}
	cout << mi << " " << ma << endl;
	return 0;
}

C++ 解法, 执行用时: 54ms, 内存消耗: 3960KB, 提交时间: 2020-07-15

#include <bits/stdc++.h>
using namespace std;
struct node{
    int v;
    int ii;
    int jj;
};
vector<int> x[10100];
int n;
int k;
struct cmp{
    bool operator ()(node &a,node &b){
        return a.v>b.v;
    }
};
priority_queue<node,vector<node>, cmp> p;

// min priority_queue<int,vector<int>, greater<int> > q;
int main()
{
    scanf("%d%d",&k,&n);
    for(int i=0;i<k;i++){
        int xx;
        for(int j=0;j<n;j++){
            scanf("%d",&xx);
            x[i].push_back(xx);
        }
    }

    int ma = -1010100101;
    int mi = 1010100110;

    for(int i=0;i<k;i++){
        node tmp;
        ma = max(ma,x[i][0]);
        mi = min(mi,x[i][0]);
        tmp.v=x[i][0];
        tmp.ii=i;
        tmp.jj=0;
        p.push(tmp);
    }
    int ml = ma-mi;
    int res1=mi,res2=ma;

    int ff=0;
    while(true){
        node t=p.top();
        p.pop();
        if(t.jj == n-1){
            break;
        }
        node tt;
        tt.v = x[t.ii][t.jj+1];
        tt.ii = t.ii;
        tt.jj = t.jj+1;
        p.push(tt);
        mi = p.top().v,mi;
        ma = max(ma,tt.v);
        if(ma-mi<ml){
            ml=ma-mi;
            res1=mi;
            res2=ma;
        }

    }
    printf("%d %d\n",res1,res2);

    return 0;
}