在麦克雷的面前有 N 个数，以及一个 R*C 的矩阵。现在他的任务是从 N 个数中取出 R*C 个，并填入这个矩阵中。矩阵每一行的法值为本行最大值与最小值的差，而整个矩阵的法值为每一行的法值的最大值。现在，麦克雷想知道矩阵的最小法值是多少。
30%：1<=n,r,c<=100
50%: 1<=n,r,c<=1000
100%:1<=r,c<=10000,r*c<=n<=5*100000,0<p<1e9
一眼题，最大值最小，数据1e5，99.9%是二分。
于是考虑怎么check?只需要排序，贪心思想，统计当前的数与它刚好相隔c-1的数的差是否小于check的值，再统计有多少组满足，看能否达到r组
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; #define N 500500 int n,k,c,l,r,mid; int a[N]; inline void read(int &x) {x=0;char ch=getchar();while(ch<‘0‘||ch>‘9‘)ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();} inline int check(int x) { int i=1,ok=0,gro=0; while(i<=n) { if(i+c-1<=n&&a[i+c-1]-a[i]<=x)gro++,i+=c; else i++; if(gro>=k){ok=1;break;} } if(ok)return 1; return 0; } int main() { read(n);read(k);read(c); for(int i=1;i<=n;i++)read(a[i]); sort(a+1,a+1+n); l=0,r=a[n]; while(l<r) { mid=l+r>>1; if(check(mid))r=mid; else l=mid+1; } printf("%d",r); return 0; }
原文：https://www.cnblogs.com/NSD-email0820/p/9784950.html