第一題：貌似是計(jì)算一下每個(gè)字符有多少段，答案就是大于n段的字符數(shù)量。

第二題：編輯距離leetcode原題，dp一下即可。

第三題：生命游戲，直接模擬即可，注意上下邊界是相鄰的。

第四題：題目大意是最后分成兩個(gè)子序列，使得兩邊子序列之和最大值最??？

剛開始寫了個(gè)錯(cuò)解，過(guò)了60%，后面想一下感覺(jué)挺容易的。考慮二分答案，我們枚舉斷開點(diǎn)，看左邊子序列和小于等于二分的值的元素個(gè)數(shù)最多能有多少個(gè)，然后看右邊子序列和小于等于二分的值的元素個(gè)數(shù)最多能，若這兩邊相加大于等于k個(gè)，說(shuō)明這個(gè)答案一定可以。那么我們需要怎么進(jìn)行求解答案呢？其實(shí)求左邊和求右邊道理都一樣，那么我們不妨求左邊，我們把每個(gè)a[i]看成價(jià)值，我們最大可以拿二分的答案值，那么就可以基于反悔貪心的思想去拿到最大的個(gè)數(shù)，復(fù)雜度是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;
}