#include<bits/stdc++.h>
using namespace std;
struct pt{
int x;
int pos;
pt(int a,int b):x(a),pos(b){}
};
struct cmp{ //重写比较函数
bool operator()(const pt a,const pt b){
return a.x>b.x;
}
};
int main(){
int k,n;
while(cin>>k>>n){
vector<vector<pt>>all;
vector<int> vec;
for(int i = 0;i<k;i++){
vector<pt>temp;
for(int j = 0;j<n;j++){
int x;
cin>>x;
pt p(x,i);
temp.push_back(p);
}
all.push_back(temp);
vec.push_back(0);
}
vector<pt> sort;
priority_queue<pt,vector<pt>,cmp> qu; //优先队列
for(int i = 0;i<k;i++)
qu.push(all[i][0]);
while(!qu.empty()){
pt temp = qu.top();
qu.pop();
sort.push_back(temp);
vec[temp.pos]++;
if(vec[temp.pos]<=n-1){
qu.push(all[temp.pos][vec[temp.pos]]);
}
}
for(int i = 0;i<vec.size();i++)
vec[i] = 0;
int begin = 0;
int end = 0;
int start = 0;
int final = 0;
int length = INT_MAX;
bool flg = false;
vec[sort[0].pos]++;
while(begin<sort.size()-1||end<sort.size()-1){
bool flgg = true;
for(int i = 0;i<k;i++)
flgg = flgg&&(vec[i]>=1);
if(!flgg&&end<sort.size()){
if(end<sort.size()-1)
end++;
vec[sort[end].pos]++;
}
if(!flgg&&end==sort.size()-1)
break;
if(flgg&&begin<sort.size()){
int x = sort[end].x-sort[begin].x;
if(x<length){
start = sort[begin].x;
final = sort[end].x;
length = x;
}
vec[sort[begin].pos]--;
if(begin<sort.size()-1)
begin++;
}
int a = 1;
}
cout<<start<<" "<<final<<endl;
}
system("pause");
return 0;
}
题目描述
给定k个有序数组, 每个数组有个N个元素，找出一个最小的闭区间，使其包含每个数组中的至少一个元素。
给定两个区间[a,b], [c,d]：
如果 b-a < d-c，则认为[a, b]是更小的区间；
如果 b-a == d-c，且a < c，则认为[a, b]是更小的区间。
输入描述:
K
N
x11 x12 x13 ... x1n
...
xk1 xk2 xk3 ... xkn
输出描述:
两个数，分别为最小区间的左右边界
示例1
输入
复制
3
3
2 12 14
2 6 9
4 7 19
输出
复制
2 4
说明
