第十五届蓝桥杯C/C++B组拔河问题详解
解题思路
这道题目的难点在于枚举所有区间,并且区间不能重合,那么这样感觉就很难了。但是用下面这种方法就会好很多。
我们只需要将左边的所有区间的各种和放在一个set中,然后我们在枚举右边的所有区间的和去和它进行比较,然后求出差值,如果差值比最小的小,那么就更新答案,那么我们只需要去从左边到右边移动线的位置就行。
代码实现
#include<iostream>
#include<vector>
#include<iostream>
#include<vector>
#include<set>
using namespace std;
const int N=1e4;
int p[N];
long long sum[N];
typedef long long LL;
set<LL>a;
int main()
{
ios::sync_with_stdio(false);
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>p[i];
sum[i]=sum[i-1]+p[i];//前缀和
}
LL res=1e15;
a.insert(1e15);//防止找不到比右边区间大的左边的
a.insert(-1e15);//防止找不到比右边区间小的左边的
for(int i=1;i<=n;i++)//枚举中间的线
{
for(int l=1;l<=i-1;l++)//枚举左边的所有区间
{
a.insert(sum[i-1]-sum[l-1]);//插入前面的区间[l,i-1];
}
for(int r=i;r<=n;r++)
{
LL s=sum[r]-sum[i-1];//枚举右边的所有区间和
auto it= a.lower_bound(s);//大于这个数的最小数
res=min(res,(*it-s));
it--;//找到小于这个数的最大数
res=min(res,(s-*it));
}
}
cout<<res;
return 0;
}