服务器怎么做网站,宁波网络公司装修怎么选,加强网站建设和信息公开,手机网站 返回顶部Problem - 7314
题目大意#xff1a;有n个数组#xff0c;从每个数组中取一个数构成数组b#xff0c;求b中最大值和最小值的差的最小值
1n1e6;总数字数量1e6;-1e9数字大小1e9
思路#xff1a;要想最大值和最大值的差最小#xff0c;所以我们要对他…Problem - 7314
题目大意有n个数组从每个数组中取一个数构成数组b求b中最大值和最小值的差的最小值
1n1e6;总数字数量1e6;-1e9数字大小1e9
思路要想最大值和最大值的差最小所以我们要对他们进行排序前排提醒1e6的排序在时间上非常极限读写优化一定要有常数尽可能小越靠近的话差值就最小我们给每个数字标上他们是第几个数组的然后放在一个数组num里按照数字的大小排序然后我们要做的就是找到一个尽可能小的区间使其包含每一个数组中的数至少一个我们建立l,r双指针初始都指向0用vis记录每个数组中的数出现的个数cnt记录当前区间出现了几个数组中的数在cntn之前扩展区间右端点r,维护vis和cntcntn之后再尝试缩小左端点l直到cntn这时num[r-1]-num[l-1]即为满足题目要求的差值在双指针移动的过程中维护此最小值即可
//#include__msvc_all_public_headers.hpp
#includebits/stdc.h
using namespace std;
const int N 1e6 5;
int vis[N];
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin t;while (t--){int n;cin n;vectorpairint, intnum;//将数字都放在一个数组里便于排序for (int i 1; i n; i){int x;cin x;vis[i] 0;for (int j 1; j x; j){int y;cin y;num.push_back(make_pair(y, i));//记录数组编号}}sort(num.begin(), num.end()); //按数值大小排序int len num.size()-1;int r 0, l 0;int cnt 0;int mi 0x7fffffff; while(1){bool flag 1;//还有没有符合条件的区间while (cnt ! n r len){//在找到合法区间前扩大区间if (!vis[num[r].second]){ cnt;//记录出现过几个数组的数}vis[num[r].second];r;}if (cnt n){flag 0;while (cnt n){//找到合法区间后缩小区间直到不合法vis[num[l].second]--;if (vis[num[l].second] 0){cnt--;}l;if (l len)break;}mi min(mi, num[r - 1].first - num[l-1].first);//维护答案最小值} if (flag)break;}cout mi endl;}return 0;
}
