PKU Judge Online 3069 Saruman's Army

■3069 Saruman's Army

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

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

□Code

view plainprint?

1. package p3069;  
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.     final int INF=1<<28;  
17.     final double EPS=1e-9;  
18.   
19.     void run(){  
20.         for(;;){  
21.   
22.             int r=sc.nextInt();  
23.             int n=sc.nextInt();  
24.   
25.             if(r==-1&&n==-1)  
26.                 break;  
27.   
28.             int[] a=new int[n];  
29.             for(int i=0; i<n; i++)  
30.                 a[i]=sc.nextInt();  
31.             Arrays.sort(a);  
32.   
33.             int ans=0;  
34.             for(int i=0; i<n;){  
35.                 int s=a[i++];  
36.                 while(i<n&&a[i]<=s+r)  
37.                     i++;  
38.                 int p=a[i-1];  
39.                 while(i<n&&a[i]<=p+r)  
40.                     i++;  
41.                 ans++;  
42.             }  
43.             println(ans+"");  
44.         }  
45.     }  
46.   
47.     void print(String s){  
48.         System.out.print(s);  
49.     }  
50.   
51.     void println(String s){  
52.         System.out.println(s);  
53.     }  
54.   
55.     public static void main(String[] args){  
56.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
57.         new Main().run();  
58.     }  
59. }  

package p3069;

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);

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

    void run(){
        for(;;){

            int r=sc.nextInt();
            int n=sc.nextInt();

            if(r==-1&&n==-1)
                break;

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

            int ans=0;
            for(int i=0; i<n;){
                int s=a[i++];
                while(i<n&&a[i]<=s+r)
                    i++;
                int p=a[i-1];
                while(i<n&&a[i]<=p+r)
                    i++;
                ans++;
            }
            println(ans+"");
        }
    }

    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();
    }
}