蓝桥试题 算法提高 Java分割项链

问题描述

两个强盗刚刚抢到一条十分珍贵的珍珠项链，正在考虑如何分赃。由于他们不想破坏项链的美观，所以只想把项链分成两条连续的珍珠链。然而亲兄弟明算账，他们不希望因为分赃不均导致不必要的麻烦，所以他们希望两条珍珠链的重量尽量接近。于是他们找到了你，希望让你帮忙分赃。

我们认为珍珠项链是由n颗不同的珍珠组成的，我们可以通过称重，分别称出每颗珍珠的重量（我们忽略连接珍珠的“链”的重量）。你要求的是每个人至少能得到多重的珍珠（即分赃少的那个人能得到多重的珍珠）。

输入格式

第一行一个整数n，表示这个珍珠项链有多少颗珍珠。第二行n个整数，顺时针给出每颗珍珠的重量wi。（你要注意的是，第一课珍珠和最后一颗珍珠是相连的）

输出格式

一个整数，表示分赃少的那个人能得到多重的珍珠。

样例输入

71 2 3 4 3 2 1

样例输出

7

数据规模和约定

对于30%的数据，n<=200；

对于60%的数据，n<=2000；

对于100%的数据，n<=50000，0<wi<=1000。

题解：

第一次拿到这个题目得了50分，就单纯考虑从第一个数开始向右遍历数组和从第一个数到最后一个数，再从最后一个数往左遍历数组，没有考虑到其实第一个数是可以不为头个数，是在不断变化的。

所以正解是利用滑动窗口，当满足那个条件近似均分的条件后，不断变化整个窗口的左右两边的值，在每个数确保都当过第一个头数后，选取最大的作为答案。

import java.util.Scanner;public class 算法提高分割项链 {static int sum,Max;//sum为整个项链重量，Max为最终答案public static void main(String[] args) {// TODO Auto-generated method stubScanner in=new Scanner(System.in);int n=in.nextInt();int a[]=new int[n];for (int i=0;i<n;i++) {a[i]=in.nextInt();sum+=a[i];}int l=0,r=0,total=0;//l窗口左值，r窗口右值，total不断变化的总和for (int i=0;i<n;i++) {//如果没接近总值的一半，窗口右值不断增大，并加上当前重量while (total<sum/2) {total+=a[r%n];r++;}//如果超过总值的一半，窗口左值增大，并减去当前重量while (total>sum/2) {total-=a[l%n];l++;}Max=Math.max(total, Max);}System.out.println(Max);}}