地址

https://hihocoder.com/problemset/problem/1722

题目

时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
给定N个数组，每个数组都包含M个整数。
现在你被要求从每个数组中选出一个数，总共N个数，然后求出其中最大与最小的差值。
在MN种选法中，差值最小是多少？

输入
第一行包含两个整数N和M。
以下N行，每行包含M个整数。
对于50%的数据，1 ≤ N × M ≤ 10000
对于100%的数据，1 ≤ N × M ≤ 200000 0 ≤ 每个整数 ≤ 1000000
输出
最小的差值

样例输入

3 3  
8 1 6      
3 5 7  
4 9 2

样例输出

2

思路

考虑对于第一个数组里的一个数x，在其他数组中对答案有贡献的只能是第一个大于等于x的数和第一个比x小的数中的一个。把后面所有数组的这两个数找出来排序，然后就是在序列中找一个差值最短的对每个数组都至少包含一个数的问题了，直接扫一遍即可。

代码

#include <bits/stdc++.h>

using namespace std;

#define MP make_pair
#define PB push_back
typedef long long LL;
typedef pair<int,int> PII;
const double eps=1e-8;
const double pi=acos(-1.0);
const int K=2e5+7;
const int mod=1e9+7;

vector<int>vc[K];
pair<int,int>c[K*2];
int ff[K];

int main(void)
{
    int n,m,ans=mod;
    cin>>n>>m;
    for(int i=0,x;i<n;i++)
    for(int j=0;j<m;j++)
        scanf("%d",&x),vc[i].push_back(x);
    for(int i=0;i<n;i++)
        sort(vc[i].begin(),vc[i].end());
    for(int i=0;i<m;i++)
    {
        int cnt=1,num=0;
        c[0]=MP(vc[0][i],0);
        for(int j=1;j<n;j++)
        {
            auto it=lower_bound(vc[j].begin(),vc[j].end(),c[0].first);
            if(it==vc[j].end())
                c[cnt++]=MP(*(--it),j);
            else if(it==vc[j].begin())
                c[cnt++]=MP(*it,j);
            else
                c[cnt++]=MP(*it,j),c[cnt++]=MP(*(--it),j);
        }
        sort(c,c+cnt);
        for(int j=0,k=0;j<cnt;j++)
        {
            //printf("(%d,%d) ",c[j].first,c[j].second);
            while(num<n&&k<cnt)
            {
                if(!ff[c[k].second]) num++;
                ff[c[k++].second]++;
            }
            if(num==n)
                ans=min(ans,c[k-1].first-c[j].first);
            if(ff[c[j].second]==1)
                num--;
            ff[c[j].second]--;
        }
        for(int j=0;j<n;j++)
            ff[j]=0;
        //printf("\n");
    }
    printf("%d\n",ans);
    return 0;
}