PKU Judge Online 2456 Aggressive cows

■2456 Aggressive cows

□Problem
プログラミングコンテストチャレンジブック参照

□Solution
プログラミングコンテストチャレンジブック参照

□Code

view plainprint?

1. package p2456;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6. import java.io.*;  
7.   
8. import static java.lang.Math.*;  
9. import static java.util.Arrays.*;  
10.   
11. // AC  
12. public class Main{  
13.   
14.     Scanner sc=new Scanner(System.in);  
15.   
16.     int INF=1<<28;  
17.     double EPS=1e-9;  
18.   
19.     int n, c;  
20.     int[] a;  
21.   
22.     void run(){  
23.         n=sc.nextInt();  
24.         c=sc.nextInt();  
25.         a=new int[n];  
26.         for(int i=0; i<n; i++)  
27.             a[i]=sc.nextInt();  
28.         Arrays.sort(a);  
29.   
30.         int low=0, up=INF;  
31.   
32.         for(int i=0; i<100; i++){  
33.             int mid=(low+up)/2;  
34.             if(C(mid))  
35.                 low=mid;  
36.             else  
37.                 up=mid;  
38.         }  
39.         println(""+low);  
40.     }  
41.   
42.     boolean C(int x){  
43.         int last=0;  
44.         for(int i=1; i<c; i++){  
45.             int next=last+1;  
46.             while(next<n&&a[next]-a[last]<x)  
47.                 next++;  
48.             if(next==n)  
49.                 return false;  
50.             last=next;  
51.         }  
52.         return true;  
53.     }  
54.   
55.     void print(String s){  
56.         System.out.print(s);  
57.     }  
58.   
59.     void println(String s){  
60.         System.out.println(s);  
61.     }  
62.   
63.     public static void main(String[] args){  
64.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
65.         new Main().run();  
66.     }  
67. }  

package p2456;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

    Scanner sc=new Scanner(System.in);

    int INF=1<<28;
    double EPS=1e-9;

    int n, c;
    int[] a;

    void run(){
        n=sc.nextInt();
        c=sc.nextInt();
        a=new int[n];
        for(int i=0; i<n; i++)
            a[i]=sc.nextInt();
        Arrays.sort(a);

        int low=0, up=INF;

        for(int i=0; i<100; i++){
            int mid=(low+up)/2;
            if(C(mid))
                low=mid;
            else
                up=mid;
        }
        println(""+low);
    }

    boolean C(int x){
        int last=0;
        for(int i=1; i<c; i++){
            int next=last+1;
            while(next<n&&a[next]-a[last]<x)
                next++;
            if(next==n)
                return false;
            last=next;
        }
        return true;
    }

    void print(String s){
        System.out.print(s);
    }

    void println(String s){
        System.out.println(s);
    }

    public static void main(String[] args){
        // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
        new Main().run();
    }
}