蓝桥杯练习系统 【试题】【算法训练】 礼物

题目链接

http://lx.lanqiao.cn/problem.page?gpid=T2990

大致题意

需要在一个非负的整数数组中选择一个长度为偶数的子数组，这个子数组需要满足前一半元素的和需要小于等于$S$，并且后一半元素的和需要小于等于$S$，找出所有满足上述条件中最长一个子数组长度。

思路

本题的数据量非常大，达到了$1e6$，需要在$O(nlogn)$的时限内解决。回到问题，很直观的是我们可以枚举答案子数组中间靠左的一个元素位置$X$（也就是前半段的最后一个元素位置或者理解成前半段的右端点），二分地考虑前半段的左端点在哪里，由于元素非负，则前缀和数组是单调增加的，在$X$的左侧找左端点的过程中，如果二分出来的左端点$Y$过小，使得前半段的和$sum={\sum }_{i=Y}^{i=X}value[i]$过大，导致$sum$大于$S$，那我们需要调整二分区间为$[mid+1,r]$；否则我们调整区间为$[l,mid]$，因为$sum<=s$是满足条件的，我们可以取到这种情况下的左端点位置$mid$。左半部分考虑结束，右半部分的考虑是类似的。

参考代码（C++）

#include <bits/stdc++.h>

using namespace std;

bool cinT = false; // 多组数据

typedef long long LL;

const int N = 1e6 + 10;

int n;
LL sum;
LL s[N];

void solve() {
	cin >> n >> sum;
	for(int i = 1; i <= n; i ++) {
		cin >> s[i];
		s[i] += s[i - 1];
	}
	
	int res = 0;
	for(int i = 1; i < n; i ++) {
		int l = 0, r = i;
		while(l < r) {
			int mid = l + r >> 1;
			if(s[i] - s[mid] <= sum) r = mid;
			else l = mid + 1;
		}
		
		if(s[i] - s[r] > sum) continue;
		
		int x = (i - r);
		
		l = i, r = n;
		while(l < r) {
			int mid = l + r + 1 >> 1;
			if(s[mid] - s[i] <= sum) l = mid;
			else r = mid - 1;
		}
		
		if(s[r] - s[i] > sum) continue;
		
		int y = (r - i);
		res = max(res, 2 * min(x, y));
	}
	
	cout << res << "\n";
}

int main() {
    cin.tie(0); cout.tie(0);
    std::ios::sync_with_stdio(false);

    int T = 1;
    if(cinT) cin >> T;
    while(T --) {
        solve();
    }

    return 0;
}