第十五届蓝桥杯C/C++B组拔河问题详解
https://i-blog.csdnimg.cn/direct/c35d4c46585b424ca99a4c3a00f84d83.png解题思绪
这道题目的难点在于枚举所有区间，而且区间不能重合，那么这样感觉就很难了。但是用下面这种方法就会好许多。
https://i-blog.csdnimg.cn/direct/0af057539fc149b19f8e85a09fe2410b.png
我们只需要将左边的所有区间的各种和放在一个set中，然后我们在枚举右边的所有区间的和去和它进行比较，然后求出差值，如果差值比最小的小，那么就更新答案，那么我们只需要去从左边到右边移动线的位置就行。
代码实现
#include<iostream>
#include<vector>
#include<iostream>
#include<vector>
#include<set>
using namespace std;
const int N=1e4;
int p;
long long sum;
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;
sum=sum+p;//前缀和
}
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-sum);//插入前面的区间;
}
for(int r=i;r<=n;r++)
{
LL s=sum-sum;//枚举右边的所有区间和
auto it= a.lower_bound(s);//大于这个数的最小数
res=min(res,(*it-s));
it--;//找到小于这个数的最大数
res=min(res,(s-*it));
}
}
cout<<res;
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]