PKU Judge Online 3061 Subsequence

■3061 Subsequence

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

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

□Code

view plainprint?

1. package p3061;  
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, s;  
20.     int[] a;  
21.   
22.     void run(){  
23.         for(int t=sc.nextInt(); t>0; t--){  
24.             n=sc.nextInt();  
25.             s=sc.nextInt();  
26.             a=new int[n];  
27.             for(int i=0; i<n; i++)  
28.                 a[i]=sc.nextInt();  
29.             println(cal()+"");  
30.         }  
31.     }  
32.   
33.     int cal(){  
34.         int res=n+1;  
35.         int p=0, q=0, sum=0;  
36.   
37.         for(;;){  
38.             while(q<n&&sum<s)  
39.                 sum+=a[q++];  
40.             if(sum<s)  
41.                 break;  
42.             res=Math.min(res, q-p);  
43.             sum-=a[p++];  
44.         }  
45.         return res%(n+1);  
46.     }  
47.   
48.     void print(String s){  
49.         System.out.print(s);  
50.     }  
51.   
52.     void println(String s){  
53.         System.out.println(s);  
54.     }  
55.   
56.     public static void main(String[] args){  
57.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
58.         new Main().run();  
59.     }  
60. }  

package p3061;

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, s;
    int[] a;

    void run(){
        for(int t=sc.nextInt(); t>0; t--){
            n=sc.nextInt();
            s=sc.nextInt();
            a=new int[n];
            for(int i=0; i<n; i++)
                a[i]=sc.nextInt();
            println(cal()+"");
        }
    }

    int cal(){
        int res=n+1;
        int p=0, q=0, sum=0;

        for(;;){
            while(q<n&&sum<s)
                sum+=a[q++];
            if(sum<s)
                break;
            res=Math.min(res, q-p);
            sum-=a[p++];
        }
        return res%(n+1);
    }

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