題目鏈接:
這個尺取法的思想挺好的，如果第一次做尺取法題，不妨看下尺取法入門題。
題目大意：

多組測試數據（0，0）截止。
每組數據輸入 n,k（n數字個數，k詢問次數）
下一行n個數表示序列。
接下一行k個表示詢問，表示找到一個子序列和的絕對值最接近k。每個詢問輸出三個數 分別是子序列和的絕對值，子序列頭和尾。

分析：

• 傳統暴力，數值量太高O(n^2)肯定直接爆炸。
• 本來從別人尺取法看到本題。發現這有負數，sum不單調怎么玩。苦苦沒有想法。后來簡單看了別人思路：求和排序 尺取法。
• sum好求。求完排序初始的序列不是都亂了么，最后還怎么輸出？所以這個要用到結構體或者二維數組根據sum排序。你可以用sum[][2]數組其中一個是sum求和，另一個是初始標記。我們在執行的過程中不需要考慮標記，只需要最后輸出時候再考慮。
• 求和數組排完序列的處理也是棘手的，因為sum就算單調了，但是sum有正負之分。如果這樣處理起來也很麻煩，但是有一個好方法：sum求差。sum差的含義是兩點之間的序列和。這樣我只在乎序列和的大小。不用在乎你的正負關系。我只需要知道你們兩之間的序列差的絕對值是那么大。但是這樣缺少一種情況—sum[i];但是我們可以引入一個sum[0]，sum[1]到sum[n]減去sum[0]就是自身。就能保證所有情況。
• 所以具體思路就是：先把數組求和，然后排序，并把對應的初始序號也計下。然后使用尺取法，left,right=0,right從1到n遍歷，看sum[right]-sum[left]是否與已知絕對值靠近，如果滿足情況更新對應的L，R，和value.因為他不需要找最短或者最長序列，找到滿足即可。也減少了難度。最后L和R是對應value=sum[R]-sum[L].找到R和L對應的序列編號，min對應小的，max對應大的(min,max對應L,R排序前實際位置一個為小編號一個為大)，其實|value|=|sum[max]-sum[min]|,實際上序列不包含min那個節點，所以最后輸出value min 1 max.

還有一點比較坑的是，他的測試用例有問題。。他又16個-1.是挺坑的，打斷點調了很久。

下面附上java ac代碼

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.Arrays; import java.util.Comparator;public class poj2566 {static int left=0;static int right=0; static int minlen=0;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));while(in.nextToken()!=StreamTokenizer.TT_EOF){int n=(int)in.nval;in.nextToken();int k=(int)in.nval;if(n==0&&k==0) {break;}int a[]=new int[n];int sum[][]=new int[n 1][2];for(int i=0;isum[right][0]?sum[left][0]:sum[right][0];System.out.println((min 1) " " max);} }}private static void chiqu(int[][] sum2, int team) {// TODO 自動生成的方法存根int l=0;for(int i=1;i=team&&lcomparator=new Comparator() {@Overridepublic int compare(int[] o1, int[] o2) {// TODO 自動生成的方法存根return o1[1]-o2[1];}};}

如果代碼有什么錯誤請大佬指正！?；

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

總結

以上是生活随笔為你收集整理的poj2566Bound Found尺取法进阶(java)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。