蓝桥杯---试题算法提高分割项链（尺取法）

本文主要是介绍蓝桥杯---试题算法提高分割项链（尺取法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

试题算法提高分割项链

资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
　　两个强盗刚刚抢到一条十分珍贵的珍珠项链，正在考虑如何分赃。由于他们不想破坏项链的美观，所以只想把项链分成两条连续的珍珠链。然而亲兄弟明算账，他们不希望因为分赃不均导致不必要的麻烦，所以他们希望两条珍珠链的重量尽量接近。于是他们找到了你，希望让你帮忙分赃。
　　我们认为珍珠项链是由n颗不同的珍珠组成的，我们可以通过称重，分别称出每颗珍珠的重量（我们忽略连接珍珠的“链”的重量）。你要求的是每个人至少能得到多重的珍珠（即分赃少的那个人能得到多重的珍珠）。
输入格式
　　第一行一个整数n，表示这个珍珠项链有多少颗珍珠。第二行n个整数，顺时针给出每颗珍珠的重量wi。（你要注意的是，第一课珍珠和最后一颗珍珠是相连的）
输出格式
　　一个整数，表示分赃少的那个人能得到多重的珍珠。
样例输入
7
1 2 3 4 3 2 1
样例输出
7
数据规模和约定
　　对于30%的数据，n<=200；
　　对于60%的数据，n<=2000；
　　对于100%的数据，n<=50000，0<wi<=1000。
思路：
尺取法，设置l,r两个游标，l为左边界，r右边界；
sum为1—n的和，找满足小于等于sum/2的最大值,
最后输出min(ans_,sum-ans_);
或找满足大于等于sum/2的最小值，
最后输出min(ans_,sum-ans_);
ac code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;int main()
{int n;scanf("%d",&n);ll a[n];ll sum=0;for(int i=0;i<n;i++){scanf("%lld",&a[i]);sum+=a[i];}int l=0;int r=0;ll ans=0;ll ans_=0;for(int i=0;i<n;i++){while(ans<sum/2){ans+=a[r%n];r++;}while(ans>sum/2){ans-=a[l%n];l++;}ans_=max(ans_,ans);}ans_=min(ans_,sum-ans_);printf("%lld",ans_);return 0;
}