蓝桥杯_拔河_java

 佬们能不能对思路二提供点建议，一直过不了T_T。

 题目

思路

        首先感觉有个坑点，就是可以不用把所有学生都选上，但是一定要保证两个部分学生的编号是连续的。比如一共5个人，编号是{1，2，3，4，5}，你可以选{1,2}，{5}；但是你不能选{1,3}，{5}，因为{1,3}是不连续的，缺了2。

   总思路：

        这题总思路是一致的，只不过在实现上可以尝试以下两种方式。

        根据那个坑点应该可以想到，我们可以找两个区间，让这两个区间里数据之和的差最小即可。但是我们怎么能够找到这两个区间就是个问题。

        一般涉及到区间求和，基本会和前缀和挂点勾，但是怎么运用前缀和又是个问题。

        这题我最开始就是踩了坑，后来看了大神的代码，归纳出了下边的总思路：

        就是我们可以把所有子区间的和都求出来，然后从小到大排个序，再求相邻数据的差(后一个-前一个)，取最小的就可以(因为升序嘛，肯定>=0)。

        下面拿样例举个例子：

                5个学生，力量值分别为10  9  8  12  14，

                我们先从第一个学生10开始求区间和：

                        [10]-->10

                        [10,9]-->19

                        [10,9,8]-->27

                        [10,9,8,12]-->39        

                        [10,9,8,12,14]-->53

                第二个学生9开始：

                        [9]-->9

                        [9,8]-->17

                        [9,8,12]-->29

                        [9,8,12,14]-->43

                同理，剩下三个学生也是这样。

                然后所有子区间的和升序排一下，结果应该是这样的：

                 list = [8 9 10 12 14 17 19 20 26 27 29 34 39 43 53]

                然后你用list[i] - list[i-1]求相邻的两个数据的差，最后取最小的就行。

可能有人会问，如果相邻的两个数，他们原来对应的区间有重合怎么办？

        有重合的话，你做差是不是就相当于把重合的部分减去了，只剩下非公共部分的了。

        比如：

        你看上边那个区间的值是s1+s2，下边的是s3+s4，又因为s2=s3，所以做完差之后，其实就是s4-s1的值，也就是说虽然一开始区间[0,5]和[3,7]有覆盖的部分，但是并不影响最后的结果。

        转化成题意可以这么理解，区间1选了[a,b]，区间2选了[c,d](a+b > c+d)，假设这个差就是最小的，但是你们老师觉得人有点少，给区间1，2分别找了一个人，对应e,f，恰好的是e,f力量一样。这么看最后他们的力量差还是不变的。我是这么理解的。

        思路一：没有很死板的先求前缀和数组

                就是没有直接求前缀和数组，而是通过两层for循环，直接把所有子区间求出来了。(这么看也不像个思路，感觉和废话一样，哈哈哈)

        思路二：把前缀和数组求了出来，然后求每个子区间的和，但是只过了15%，后续会补T_T

                这个就是把前缀和数组算出来，操作前缀和数组，去求个每个子区间的和。(这种的我还没整出来，对前缀和还是理解不透彻)

代码

注释掉的就是思路二(T_T)

也请大佬们看看思路二写的有什么问题，感谢！！

package 蓝桥;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class 拔河 {public static void main(String[]args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();ArrayList<Long> list = new ArrayList<>();int []a = new int[n + 1];for(int i = 1;i <= n;i ++) {a[i] = sc.nextInt();// 存力量}for(int i = 1;i <= n;i ++) {long sum = a[i];// 落单的，也就是单个数的，也要加到list里面，不排除老师每个队只找一个学生。// 虽然不加这句话也过了题。list.add(sum); for(int j = i+1;j <= n;j ++) {sum += a[j];list.add(sum);}}Collections.sort(list);long min = Long.MAX_VALUE;for(int i = 1;i < list.size();i ++) {min = Math.min(min,(list.get(i) - list.get(i-1)));}System.out.println(min);
//        int[] sum = new int[n+1];
//        sum[0] = 0;
//        for(int i = 1;i <= n;i ++) {
//            sum[i] = sum[i-1] + a[i];
//        }
//        for(int i = 1;i <= n;i ++) {
//            for(int j = i;j <= n;j ++) {
//                list.add(sum[j] - sum[i-1]);
//            }
//        }System.out.println();
//        int min = Integer.MAX_VALUE;
//        for(int i = 1;i < list.size();i ++) {
//            min = Math.min(min,(list.get(i) - list.get(i-1) ));
//        }
//        System.out.println(min);
//        Collections.sort(list);
//        for (Long integer : list) {
//            System.out.print(integer + " ");
//        }}
}