P13778 「o.OI R2」=+#-

· · 题解

思路：

先转化一下题意，设 cnt_i 为 c 中 i 的个数。

于是本质上，可以看作在一个数轴考虑，如果当前在位置 i，有 cnt_i 次向右的移动次数，否则可以选择做错一道题，向左走；然后使得向右走的次数最大。

继续分析一下，考虑 cnt_i > 0 的那些极长连续段 [l, r]，如果在其中某个位置的话，可以一直连续往上跳到 r + 1。

于是对于 k 来说，如果 cnt_k = 0，那么它只能往左走到 k - 1，所以只有 \le k - 1 的题它可能做出来，令 R = k - 1；否则 cnt_k > 0，找到它所在连续段的右端点 r，那么 \le r 的题它都可能做出来，令 R = r。

然后枚举 k 最后变成了什么，假设它最后一次做对题后变成了 k' + 1，考虑中间最多能做对多少题，设对了 a 道，错了 b 道，那么显然：

k + a - b = k' + 1

于是 b = k + a - k' - 1，然后因为 a + b \le n 可以带入进去，得到 2a + k - k' - 1 \le n，所以 a \le \frac{n - k + k' + 1}{2}；这是一个上界。

设 k' 所在连续段是 [l, r]，那么显然最多只能做对 [l, R] 中所有题，设为 sum；我们容易证明 a = \min(\lfloor \frac{n - k + k' + 1}{2} \rfloor, sum) 是能取到的，这是因为我们用来下降的错题是管够的。

于是枚举 k'，答案是：

\max_{k'} \min(\sum_{pre_{k'} \le k'\le R} cnt_i, \lfloor \frac{n - k + k' + 1}{2} \rfloor)

预处理前缀和就可以算出来了，时间复杂度为 O(n)。

完整代码：

#include<bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define popcnt(x) __builtin_popcount(x)
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e6 + 10;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
int T, n, k, ans, m = 1e6;
int cnt[N], s[N], pre[N];
inline void solve(){
    ans = 0;
    for(int i = 0; i <= m; ++i)
      cnt[i] = s[i] = pre[i] = 0;
    n = read(), k = read();
    for(int x, i = 1; i <= n; ++i){
        x = read();
        ++cnt[x];
    }
    for(int i = 1; i <= m; ++i)
      s[i] = s[i - 1] + cnt[i];
    int R = k;
    if(!cnt[R])
      --R;
    else{
        while(cnt[R + 1])
          ++R;
    }
    for(int i = 1; i <= m; ++i){
        if(!cnt[i])
          continue;
        pre[i] = cnt[i - 1] ? pre[i - 1] : i;
    }
    for(int k_ = 1; k_ <= R; ++k_){
        if(!cnt[k_])
          continue;
        int l = pre[k_], r = R;
        ans = max(ans, min(s[r] - s[l - 1], (n - k + k_ + 1) >> 1));
    }
    write(ans);
    putchar('\n');
}
int main(){
    T = read();
    while(T--)
      solve();
    return 0;
}