poj3061(尺取法)-java教程-PHP中文网

poj3061(尺取法)

PHP中文网

发布： 2017-07-08 18:12:43

原创

1939人浏览过

Subsequence

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 14927		Accepted: 6312

Description

A sequence of N positive integers (10

Input

The first line is the number of test cases. For each test case the program has to read the numbers N and S, separated by an interval, from the first line. The numbers of the sequence are given in the second line of the test case, separated by intervals. The input will finish with the end of file.

Output

For each the case the program has to print the result on separate line of the output file.if no answer, print 0.

Sample Input

<span style="font-size: 18px"><strong>2
10 15
5 1 3 5 10 7 4 9 2 8
5 11
1 2 3 4 5</strong></span>

登录后复制

Sample Output

<span style="font-size: 18px"><strong>2
3</strong></span>

登录后复制

Source

Southeastern Europe 2006

算法设计：

代码

<span style="color: #0000ff">import</span><span style="color: #000000"> java.util.Scanner;

</span><span style="color: #0000ff">public</span> <span style="color: #0000ff">class</span><span style="color: #000000"> Main{

    </span><span style="color: #008000">/**</span><span style="color: #008000">
     * </span><span style="color: #808080">@param</span><span style="color: #008000"> args
     </span><span style="color: #008000">*/</span>
    <span style="color: #0000ff">static</span> <span style="color: #0000ff">int</span><span style="color: #000000"> n,s;
    </span><span style="color: #0000ff">static</span> <span style="color: #0000ff">int</span> map[]=<span style="color: #0000ff">new</span> <span style="color: #0000ff">int</span>[100000+3<span style="color: #000000">];
    </span><span style="color: #0000ff">static</span> <span style="color: #0000ff">int</span> sum[]=<span style="color: #0000ff">new</span> <span style="color: #0000ff">int</span>[100000+3<span style="color: #000000">];
    </span><span style="color: #0000ff">public</span> <span style="color: #0000ff">static</span> <span style="color: #0000ff">void</span><span style="color: #000000"> main(String[] args) {
        </span><span style="color: #008000">//</span><span style="color: #008000"> TODO Auto-generated method stub</span>
        Scanner scan=<span style="color: #0000ff">new</span><span style="color: #000000"> Scanner(System.in);
        </span><span style="color: #0000ff">int</span> t=<span style="color: #000000">scan.nextInt();
        </span><span style="color: #0000ff">while</span>(t>0<span style="color: #000000">){
            n</span>=<span style="color: #000000">scan.nextInt();
            s</span>=<span style="color: #000000">scan.nextInt();
            </span><span style="color: #0000ff">for</span>(<span style="color: #0000ff">int</span> i=0;i<n;i++<span style="color: #000000">){
                map[i]</span>=<span style="color: #000000">scan.nextInt();
            }
            sovle();
            t</span>--<span style="color: #000000">;
        }
        
    }
    </span><span style="color: #0000ff">private</span> <span style="color: #0000ff">static</span> <span style="color: #0000ff">void</span><span style="color: #000000"> sovle() {
        </span><span style="color: #008000">//</span><span style="color: #008000"> TODO Auto-generated method stub</span>
        <span style="color: #0000ff">int</span> res=n+1<span style="color: #000000">;
        </span><span style="color: #0000ff">int</span> ss=0,t=0,sum=0<span style="color: #000000">;
        </span><span style="color: #0000ff">for</span><span style="color: #000000">(;;){
            </span><span style="color: #0000ff">while</span>(t<n&&sum<<span style="color: #000000">s){
                sum</span>+=map[t++<span style="color: #000000">];
            }
            </span><span style="color: #0000ff">if</span>(sum<<span style="color: #000000">s){
                </span><span style="color: #0000ff">break</span><span style="color: #000000">;
            }
            res</span>=Math.min(res, t-<span style="color: #000000">ss);
            sum</span>-=map[ss++<span style="color: #000000">];
        }
        </span><span style="color: #0000ff">if</span>(res><span style="color: #000000">n){
            res</span>=0<span style="color: #000000">;
        }
        System.out.println(res);
    }

}</span>

登录后复制

以上就是poj3061(尺取法)的详细内容，更多请关注php中文网其它相关文章！