poj2566Bound Found尺取法进阶(java)

题目链接:
这个尺取法的思想挺好的，如果第一次做尺取法题，不妨看下尺取法入门题。
题目大意：

多组测试数据（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() {
		@Override
		public int compare(int[] o1, int[] o2) { // TODO 自动生成的方法存根 return o1[1]-o2[1];
		}
	};

}

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
 

如果代码有什么错误请大佬指正！?；

• 如果对后端、爬虫、数据结构算法等感性趣欢迎关注我的个人公众号交流：bigsai
  

文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。

原文链接：bigsai.blog.csdn.net/article/details/88721347