这个尺取法的思想挺好的，如果第一次做尺取法题，不妨看下尺取法入门题。
题目大意：
多组测试数据（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]; } }; }
如果代码有什么错误请大佬指正！?；
