測資生成器

#include <iostream>
#include <math.h>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
int N = 10, K = 20 , range = 1000;              
int main(){
    srand( time( NULL ) );
    freopen("10.in","w",stdout);
    printf("%d %d\n",N,K);
    for ( int i = 0 ; i < N ; i++ ){
        if ( i ) putchar( ' ' );
        printf("%d",rand()*rand()%range);
    }
    printf("\n");
    return 0;    
}

解答

#include <iostream>
#include <math.h>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
int N, K, arr[50005]; 
int main(){


    freopen("10.in", "r", stdin);
    freopen("10.out", "w", stdout);

        scanf("%d%d",&N,&K);

        for ( int i = 1 ; i <= N ; i++ )
            scanf("%d",&arr[i]);
        sort( arr+1, arr+N+1 );

        int l = 0, r = 1000000000;
        int ans = -1;

        while ( r >= l ){
            int mid = ( l + r ) >> 1;

            int cnt = 1, rZone = arr[1] + mid;

            for ( int i = 2 ; i <= N ; i++ )
                if ( arr[i] > rZone ){
                    rZone = arr[i] + mid;    
                    if ( ++cnt > K ) break;
                }

            if ( cnt <= K ){
                ans = mid;    
                r = mid-1;
            }
            else
                l = mid+1;

        }

        printf("%d\n",ans);


    return 0;    
}