深信服笔试(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;
}
#深信服笔试#