蓝桥杯 之 拔河(2024年C/C++ B组 H题)

• 本题是 2024年C/C++ B组的H题
• 首先看这个数据范围，个数也就在10^3,并且考察的还是连续区间的和的最小差值位置，注意的是这个区间是不能重合的
  • 连续区间和的问题，考虑用到这个前缀和
  • 由于考察的是左右两个区间，并且还不能重合，所以得考虑使用这个双指针，通过枚举左右区间的左右端点进行求解
  • 处理的细节：得使用一个列表存储每一个区间和，使用前缀和，进行两层遍历即可，得到store，然后进行一个升序排序
  • ==》 有一个很巧妙的思路，就是在store数组中，直接遍历相邻的元素，作差，然后直接更新答案在这里，即使有重复的元素，后面也可以进行作差减去，但是这个方法是存在一个问题的，没有处理重复的问题，但是在蓝桥杯官网这边的测试用例hack不掉
  • 正宗的做法是，逐步删除重合的区间，通过二分查找，找到最接近的区间和，进行作差，更新答案

下面的python的代码，作者自己写的，和官方的题解的差别在于这个下标是从0开始

import bisect
# 总体来说就是使用这个双指针进行暴力求解

n = int(input())
a = list(map(int, input().split()))

store = []
pre = [0]*(n+1)
for i in range(n):
  pre[i+1] = pre[i] + a[i]
# 求解前缀和的全部组合
# 这个l,r对应的是下标，
for l in range(n):
  for r in range(l,n):
    cur = pre[r+1] - pre[l]
    store.append(cur)
# 排个序
store = sorted(store)

res = float('inf')

# 现在开始双指针暴力枚举
# 枚举这个 左边队伍的右端点
for r1 in range(n):
  # 首先得将右边区间的以r1为左端点的值从这个store中去掉
  for l2 in range(r1,n):
    diff = pre[l2+1] - pre[r1]
    index = bisect.bisect_left(store,diff)
    if index < len(store) and store[index] == diff:
      store.pop(index)
  # 现在就开始枚举这个左边区间的左端点
  for l1 in range(r1+1):
    target = pre[r1+1] - pre[l1]
    index = bisect.bisect_left(store,target)
    if index < len(store):
      res = min(res,abs(target-store[index]))
    if index > 0:
      res = min(res,abs(target-store[index-1]))
print(res)

下面展示官方的题解

• C++

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
ll a[N], sum[N];
multiset<ll>se;
int main(){
    int n; cin >> n;
    for(int i = 1 ; i <= n ; i ++) cin >> a[i], sum[i] = sum[i - 1] + a[i];
    for(int i = 1 ; i <= n ; i ++) for(int j = i ; j <= n ; j ++){
        se.insert(sum[j] - sum[i - 1]);
    }
    se.insert(-INF);
    se.insert(INF);
    ll res = LONG_MAX;
    for(int i = 1 ; i <= n ; i ++){
        for(int r = i ; r <= n ; r ++){
            auto it = se.find(sum[r] - sum[i - 1]);
            se.erase(it);
        }
        for(int l = 1 ; l <= i ; l ++){
            auto x = se.lower_bound(sum[i] - sum[l - 1]);
            res = min(res, abs(sum[i] - sum[l - 1] - *x));
            x --;
            res = min(res, abs(sum[i] - sum[l - 1] - *x));
        }
    }
    cout << res << '\n';
    return 0;
}

• Java

import java.util.*;

public class Main {
    static final long INF = Long.MAX_VALUE;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long[] a = new long[n + 1];
        long[] sum = new long[n + 1];
        TreeSet<Long> set = new TreeSet<>();

        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextLong();
            sum[i] = sum[i - 1] + a[i];
        }

        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                set.add(sum[j] - sum[i - 1]);
            }
        }

        set.add(-INF);
        set.add(INF);

        long res = Long.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            for (int r = i; r <= n; r++) {
                long diff = sum[r] - sum[i - 1];
                set.remove(diff);
            }
            for (int l = 1; l <= i; l++) {
                long target = sum[i] - sum[l - 1];
                Long x = set.ceiling(target);
                if (x != null) {
                    res = Math.min(res, Math.abs(sum[i] - sum[l - 1] - x));
                }
                if (x != null && x != set.first()) {
                    x = set.lower(target);
                    res = Math.min(res, Math.abs(sum[i] - sum[l - 1] - x));
                }
            }
        }
        System.out.println(res);
    }
}

• python

import sys
import bisect

INF = float('inf')

def main():
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    a = [0] * (n + 1)
    sum = [0] * (n + 1)
    for i in range(1, n + 1):
        a[i] = int(data[i])
        sum[i] = sum[i - 1] + a[i]
    
    set_sum = []
    
    for i in range(1, n + 1):
        for j in range(i, n + 1):
            set_sum.append(sum[j] - sum[i - 1])
    
    set_sum.append(-INF)
    set_sum.append(INF)
    set_sum.sort()
    
    res = INF
    
    for i in range(1, n + 1):
        for r in range(i, n + 1):
            diff = sum[r] - sum[i - 1]
            idx = bisect.bisect_left(set_sum, diff)
            if idx < len(set_sum) and set_sum[idx] == diff:
                set_sum.pop(idx)
        
        for l in range(1, i + 1):
            target = sum[i] - sum[l - 1]
            idx = bisect.bisect_left(set_sum, target)
            if idx < len(set_sum):
                res = min(res, abs(sum[i] - sum[l - 1] - set_sum[idx]))
            if idx > 0:
                res = min(res, abs(sum[i] - sum[l - 1] - set_sum[idx - 1]))
    
    print(res)

if __name__ == "__main__":
    main()