第十五届蓝桥杯C/C++B组拔河问题详解

解题思绪

这道题目的难点在于枚举所有区间，而且区间不能重合，那么这样感觉就很难了。但是用下面这种方法就会好许多。

我们只需要将左边的所有区间的各种和放在一个set中，然后我们在枚举右边的所有区间的和去和它进行比较，然后求出差值，如果差值比最小的小，那么就更新答案，那么我们只需要去从左边到右边移动线的位置就行。
代码实现

1. #include<iostream>
2. #include<vector>
3. #include<iostream>
4. #include<vector>
5. #include<set>
6. using namespace std;
7. const int N=1e4;
8. int p[N];
9. long long sum[N];
10. typedef long long LL;
11. set<LL>a;
12. int main()
13. {
14.     ios::sync_with_stdio(false);
15.         int n;
16.         cin>>n;
17.         for(int i=1;i<=n;i++){
18.                 cin>>p[i];
19.                 sum[i]=sum[i-1]+p[i];//前缀和
20.         }
21.     LL res=1e15;
22.     a.insert(1e15);//防止找不到比右边区间大的左边的
23.     a.insert(-1e15);//防止找不到比右边区间小的左边的
24.     for(int i=1;i<=n;i++)//枚举中间的线
25.     {
26.         for(int l=1;l<=i-1;l++)//枚举左边的所有区间
27.         {
28.             a.insert(sum[i-1]-sum[l-1]);//插入前面的区间[l,i-1];
29.         }      
30.         for(int r=i;r<=n;r++)
31.         {
32.             LL s=sum[r]-sum[i-1];//枚举右边的所有区间和
33.             auto it= a.lower_bound(s);//大于这个数的最小数
34.             res=min(res,(*it-s));
35.             it--;//找到小于这个数的最大数
36.             res=min(res,(s-*it));
37.         }
38.     }
39.     cout<<res;
40.     return 0;
41. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。