Codeforces Round 963 D
题目描述
给定两个正整数 n 和 k 以及另一个由 n 个整数组成的数组 a 。
在一次操作中，可以选择 a 中大小为 k 的任意一个子数组，然后将其从数组中删除，而不改变其他元素的顺序。更正式地说，假设 (l, r) 是对子数组 a[l], a[l+1], ..., a[r] 的操作，使得 r-l+1=k ，那么执行此操作意味着将 a 替换为 [a[1], ..., a[l-1], a[r+1], ..., a[n]] 。
例如，如果 a=[1, 2, 3, 4, 5] 在这个数组上执行了 (3, 5) 操作，那么它就会变成 a=[1, 2] 。此外，操作 (2, 4) 的结果是 a=[1, 5] ，操作 (1, 3) 的结果是 a=[4, 5] 。
当 a 的长度大于 k （即 |a| > k ）时，你必须重复操作。处理后，数组 a 中所有剩余元素的最大中值是多少？
长度为 n 的数组的中位数是我们对元素进行非递减排序后索引为 ⌊ (n+1)/2 ⌋ 的元素。例如 median([2, 1, 5, 4, 3]) = 3 、 median([5]) = 5 和 median([6, 8, 2, 4]) = 4 。
解题思路
- 这题需要想到二分搜索可行解，复杂度在log(Max(a)).
- 需要理解，这题找的是最大解，所以对于二分的每一个x，只需要找是否有某个终态满足 其中的>=x的数字多于一半。例如1,2,4,5,5,6。对于4是满足的，对于5不满足。同时对于1也满足，可能会存在疑惑，1不可能是中位数，但是我们找的实际上是最大解，所以1可行的含义应该是这个解可以>=1。如果满足，二分会一直向后推导到4也就是答案。因为比4大的所有x都被认为不满足。
- 考虑如何进行判断，这里我们使用dp来访问可达状态，我们的目标应该是保证到达终态时>=x的数尽量的多。这时候其实就是看一个序列大于等于x的数有多少个。
- 考虑如何转移状态，这里我们对编号减一并且取模(把index都减1了方便后续判断)。对于每一个i，它可以由哪里转移过来？没有任何数字时>=x的数量为0设dp[0] = 0。第一个状态很显然，它可以由dp[0]转移而来，所以dp[1] = dp[0]+ (a[1] >= x ? 1 : -1)
- 为啥这里取-1和1，因为这样最后只要大于0就可以说明>=x数量多余<x，方便判断
- 对于不在第一行的序号，它首先可以继续由它左方的状态转移而来，并且它还可以放弃自身的位置，也就是继续让上一行的状态保留。
dp[i] = max(dp[i-1] + (a[i] >= x ? 1 : -1), dp[i-k]) - 但是对于每一行的第一个点，没有左端的状态给他转移，也就是它不能接续前面的序列，因为这个序列长度它不能>k。它现在面临两个选择，第一是新开一个序列，也就是把前一个状态ci更新为0，或者它还可以和其它点一样，放弃自己，继续继承上一行的0位置。表现在操作上就是index 1 2 3 4 选择删掉1 2 3还是删掉2 3 4。
- 至此整个题目就解决了。以下面的样例举例，实际上就是告诉你只能选两个位于0和1的数，并且0和1需要满足一个顺序，0选择的数字在a[i]中必须出现在1的前方。朴素做法是枚举所有可能组合来选择，但是最大数量是可以逐步转移过去的，所以只需要在n次操作里面dp。
n = 8, k = 3
index 1 2 3 4 5 6 7 8
mod 0 1 2 0 1 2 0 1
拆成多段 状态只能由左向右转移或者正下方替代正上方的状态
因为每次要删去连续的k个，可以亲手试试来验证。
0->1->2
| | |
0->1->2
| |
0->1
代码实现
#include <bits/stdc++.h>
using namespace std;
#define __DEBUG
#ifdef __DEBUG
#define DB(X) { cout << #X << " = " << (X) << '\n'; }
#define DB1(A, _) { cout << #A << "[" << _ << "] = " << (A[_]) << '\n'; }
#define DB2(A, _, __) { cout << #A << "[" << _ << "][" << __ << "] = " << (A[_][__]) << '\n'; }
#define DB3(A, _, __, ___) { cout << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << (A[_][__][___]) << '\n'; }
#define PR(A, l, r) { cout << '\n'; for (int _ = l; _ <= r; ++_) DB1(A, _); cout << '\n';}
#else
#define DB(X)
#define DB1(A, _)
#define DB2(A, _, __)
#define DB3(A, _, __, ___)
#define PR(A, l, r)
#endif
#define sz(x) ((int) (x).size())
#define fi first
#define se second
#define int long long
#define ULL unsigned long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
const int p=998244353;
int po(int a,int b) {if(b==0) return 1; if(b==1) return a; if(b%2==0) {int u=po(a,b/2);return (u*1LL*u)%p;} else {int u=po(a,b-1);return (a*1LL*u)%p;}}
int gc(int a, int b) {if(a == 0) return b;if(b == 0)return a;return gc(b, a%b);}
int exgcd(int a,int b,int &x,int &y){if(b==0){x=1;y=0;return a;}int r=exgcd(b,a%b,x,y);int temp=y; y=x-(a/b)*y;x=temp;return r;}
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
void Solve(){
int n, k;cin>>n>>k;
int a[n+1];
for(int i = 1; i <= n;i ++){
cin>>a[i];
}
int l = 0, r = 1e9 + 10, mid;
while(l < r){
mid = (l + r + 1) >> 1;
vector<int> dp(n+1, -LLONG_MAX);
dp[0] = 0;
for(int i = 1; i <= n; i++){
int ci;
ci = dp[i-1];
if((i-1) % k == 0) ci = 0;
int is = a[i] >= mid ? 1 : -1;
dp[i] = max(dp[i], ci + is);
if(i > k) dp[i] = max(dp[i], dp[i - k]);
}
//DB(l)DB(r)DB(mid)
//PR(dp,0,n)
if(dp[n] > 0){
l = mid;
}else{
r = mid - 1;
}
}
cout<<l<<endl;
}
int32_t main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;cin>>T;while(T--)
Solve();
return 0;
}
复杂度分析
- 时间复杂度: nlog(max(a))