今天遇到這題因為以前沒見到過，當時就是想著應該有著一個很簡單的方法可以過但是奈何就是沒思路。后來看了別人思路寫了下來。學習了尺取法

poj3061

題目介紹：

Description
A sequence of N positive integers (10 < N < 100 000), each of them less than or equal 10000, and a positive integer S (S < 100 000 000) are given. Write a program to find the minimal length of the subsequence of consecutive elements of the sequence, the sum of which is greater than or equal to S.
(給出N個正整數(shù)（10 <100 000）的序列，每個正整數(shù)小于或等于10000，并且給出正整數(shù)S（S <100 000 000）。編寫程序以找到序列的連續(xù)元素的子序列的最小長度，其總和大于或等于S.)
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.
(第一行是測試用例的數(shù)量。對于每個測試用例，程序必須從第一行讀取數(shù)字N和S，以間隔分隔。序列的編號在測試用例的第二行中給出，以間隔分開。輸入將以文件結尾結束。)
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
2
10 15
5 1 3 5 10 7 4 9 2 8
5 11
1 2 3 4 5
Sample Output
2
3

思路的萌發(fā)：

最開始的傻D思路：暴力破解，從長度1開始暴力。o(n3)超時。

前綴和 二分：把前面的和用sum[]求出來。然后從第一項到最后一項一個個求，因為有sum[],所以每一個都用二分查找,然后剪枝考慮省去一些不必要的步驟。可以獲得答案。復雜度o(nlogn)；

尺取法：這個方法非常巧妙，復雜度是o(n)，他核心思想就是用一個段長當作可移動伸縮的尺子（左，右點向右移動）。求最短長就相當于 一個卷尺從頭開始移動到各個點拉長，在這過程中。如果尺子長度大于需要的長，那么左面一直往前面移動，并且做相應記錄，知道短了右側需要繼續(xù)加長。這種情況可以遍歷所有滿足的情況，復雜度非常低。
所有這題的尺取法就是 用一個sum從開始記錄和，尺取法跑一圈

二分：

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintWriter; import java.io.StreamTokenizer; import java.util.Scanner;public class poj3601 { /** 二分法*/public static void main(String[] args) throws IOException {// TODO 自動生成的方法存根StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));in.nextToken();int t=(int)in.nval;for(int i=0;i<t;i++){in.nextToken();int a=(int)in.nval;in.nextToken();int b=(int)in.nval;int c[]=new int[a]; int len=Integer.MAX_VALUE;long sum[]=new long[a+1];//for(int j=0;j<a;j++){in.nextToken();c[j]=(int)in.nval;sum[j+1]+=sum[j]+c[j];} int left=0;int right=a;for(int j=0;j<a;j++){int l=j;int r=(len==Integer.MAX_VALUE?a:(len+l>a?a:len+l));//右面長度存在不，不存在從a二分。如果存在加上這個點保證不能越界boolean jud=false;//用于終止循環(huán)while(true){ if(sum[r]-sum[l]>=b)//如果大于目標進行二分{if(r-l<len) {len=r-l;}r=(l+r)/2; }else//小于目標直接向右增加尋找目標，找到的第一個就是極限最短，在這區(qū)間不能越界，長度不能超多已經(jīng)知道最短長度{for(;r<=a+1;r++){ if(r>a) {jud=true;break;}if(r-l>=len) {jud=true;break;}if(sum[r]-sum[l]>=b) {len=r-l;break;}} }if(jud) {break;}}}if(len!=Integer.MAX_VALUE) {out.println(len);}else out.println(0);}out.flush();}}

尺取法：

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintWriter; import java.io.StreamTokenizer; import java.util.Scanner;public class poj3602尺取 { /** 尺取法*/public static void main(String[] args) throws IOException {// TODO 自動生成的方法存根StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));in.nextToken();int t=(int)in.nval;for(int i=0;i<t;i++){in.nextToken();int a=(int)in.nval;in.nextToken();int b=(int)in.nval;int c[]=new int[a]; int len=Integer.MAX_VALUE;long sum=0;for(int j=0;j<a;j++){in.nextToken();c[j]=(int)in.nval; } sum=c[0];int l=0;int r=1;for(int j=1;j<a;j++){sum+=c[j];while(sum>b){if(len>j-l) {len=j-l;}if(len<=0) {break;}sum-=c[l++];}}if(len!=Integer.MAX_VALUE) {out.println(len+1);}else out.println(0); }out.flush();}}

• 如果對后端、爬蟲、數(shù)據(jù)結構算法等感性趣歡迎關注我的個人公眾號交流：bigsai
  

總結

以上是生活随笔為你收集整理的poj3061尺取法/前缀和 二分(java)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。