题面
在麦克雷的面前有 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; }