45 lines
1.2 KiB
C++
45 lines
1.2 KiB
C++
// lanqiao 19713 拔河
|
||
#include<bits/stdc++.h>
|
||
using namespace std;
|
||
#define int long long
|
||
const int N = 1e3+10;
|
||
int a[N], s[N]; // s为前缀和数组
|
||
multiset<int> ms;
|
||
|
||
signed main(){
|
||
int n; cin>>n;
|
||
for(int i = 1; i<=n; i++){
|
||
cin >> a[i];
|
||
s[i] = s[i-1] + a[i];
|
||
}
|
||
// 使用set数组去维护所有的区间和
|
||
for(int i = 1; i<=n; i++){
|
||
for(int j = i; j<=n; j++){
|
||
ms.insert(s[j] - s[i-1]);
|
||
}
|
||
}
|
||
int ans = LLONG_MAX;
|
||
|
||
// 时间复杂度为 O(n^log2n)
|
||
for(int i = 1; i<=n; i++){
|
||
for(int j = 1; j<i; j++){
|
||
// 枚举以i结尾的区间
|
||
int sum = s[i] - s[j-1];
|
||
// 找到该区间和sum相似的区间和s1 and s2
|
||
auto it = ms.lower_bound(sum);
|
||
if(it!=ms.end()){ ans = min(ans, abs(*it - sum)); } // 找到了
|
||
if(it!=ms.begin()){
|
||
it--;
|
||
ans = min(ans, abs(*it - sum));
|
||
}
|
||
}
|
||
// 删除以i开头且以j结尾的区间，防止后续查询区间的时候出现区间重叠/交叉重复问题
|
||
for(int j = i; j<=n; j++) ms.erase(ms.find(s[j] - s[i-1]));
|
||
}
|
||
cout << ans << endl;
|
||
return 0;
|
||
}
|
||
/* test samples -> 1
|
||
5
|
||
10 9 8 12 14
|
||
*/ |