2259: matrix

/*
解法

考虑矩阵中的两行a和b，a1<a2<...<aC
，b1<b2<...<bC，如果aC>b1

，那么交换aC和b1可以得到更优的答案。
所以每一行的值域是不会有交集的。

将所有数升序排序。
设已知答案为ans；
顺序枚举每一个数，如果a[i+C?1]?a[i]<=ans

，我们就可以贪心地把这C个数放进矩阵，枚举完后判断一下是否能够凑齐R行。
证明：
设选取a[i+k]..a[i+k+C-1]会比选取a[i]..a[i+C-1]更优。
设f(x)为[x..n]的最大答案。
那么选取a[i+k]..a[i+k+C-1]能够得到的最大答案即为f(i+k+C)+1；
选取a[i+k]..a[i+C-1]能够得到的最大答案即为f(i+C)+1；
显然f(x)是减函数。
所以与假设违背。

二分答案ans。
就可以将原问题转化为上述问题。


*/


#include<iostream>
#include<algorithm>

using namespace std ;

#define maxn 1100000
int n , r , c ; 
int num[maxn] ; 

bool check(int max_ans){
    int cnt = 0 ;
    for(int i=c ; i<=n ; i++){
        if(num[i] - num[i-c+1] <= max_ans){
            cnt++ ;
            i = i + c-1 ; //后续的 i++ 会修正i值
            if(cnt>=r){
                return true ; 
            }
        }
    }
    return false ; 
}/*
bool check(int limit){
    
    int cnt=0;
    for (int i=1;i<=n-c+1;i++){
        if (num[i+c-1]-num[i]<=limit){
            cnt++;
            i=i+c-1;
            if (cnt>=r) return true;
        }
    }
    return false;
}
*/
int main(){
    int  right =0; 
    cin>>n>>r>>c ; 
    for(int i=1 ; i<=n ; i++)
        cin>>num[i] , right = max(right,num[i]);

    sort(num+1 , num+1+n) ; 

    int left = 0 ;//, right = 1000000001 ; 
    int mid ; 
    while(left<right){
        mid = (left+right)/2 ; 
        if(check(mid)){
            right = mid ; 
        }else{
            left = mid+1 ; 
        }
    }

    cout<<left<<endl ; 
    return 0 ; 
}