深信服笔试(C++)

第一题：貌似是计算一下每个字符有多少段，答案就是大于n段的字符数量。

第二题：编辑距离leetcode原题，dp一下即可。

第三题：生命游戏，直接模拟即可，注意上下边界是相邻的。

第四题：题目大意是最后分成两个子序列，使得两边子序列之和最大值最小？

刚开始写了个错解，过了60%，后面想一下感觉挺容易的。考虑二分答案，我们枚举断开点，看左边子序列和小于等于二分的值的元素个数最多能有多少个，然后看右边子序列和小于等于二分的值的元素个数最多能，若这两边相加大于等于k个，说明这个答案一定可以。那么我们需要怎么进行求解答案呢？其实求左边和求右边道理都一样，那么我们不妨求左边，我们把每个a[i]看成价值，我们最大可以拿二分的答案值，那么就可以基于反悔贪心的思想去拿到最大的个数，复杂度是nlognlogn

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
void solve()
{
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	
	auto check = [&](ll v) {
		vector<int> l(n);
		priority_queue<int> Q;
		ll rv = v;
		for (int i = 0; i < n; i ++) {
			if (rv >= a[i]) {
				rv -= a[i];
				Q.push(a[i]);
			} else {
				if (!Q.empty() && Q.top() > a[i]) {
					rv += Q.top();
					Q.pop();
					rv -= a[i];
					Q.push(a[i]);
				}
			}
			l[i] = Q.size();
		}
		while (Q.size()) {
			Q.pop();
		}
		rv = v;
		for (int i = n - 1; i >= 0; i--) {
			if (rv >= a[i]) {
				rv -= a[i];
				Q.push(a[i]);
			} else {
				if (!Q.empty() && Q.top() > a[i]) {
					rv += Q.top();
					Q.pop();
					rv -= a[i];
					Q.push(a[i]);
				}
			}
			if (Q.size() + (i > 0 ? l[i - 1] : 0) >= k) {
				return true;
			}
		}
		return false;
	};

	ll l = 1, r = 1e18;
	while (l <= r) {
		ll m = (l + r) >> 1;
		if (check(m)) {
			r = m - 1;
		} else {
			l = m + 1;
		}
	}
	cout << l << '\n';
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	int _ = 1;
	cin >> _;
	while (_--) {
		solve();
	}
	return 0;
}