【题解】评分 二分+DP bzoj4985 ——quhengyi11

题目

这里可爱的传门酱 (≧▽≦)

题解

这道题真的毒瘤 QAQ，首先我也想到了能不能二分答案再验证，可是这个对评分序列的操作实在是让我无从下手 QwQ

首先我们需要二分一个答案 x，将原序列通过大小关系转换为 01 序列，接着如何验证呢？

我们设 $f_i$表示当前位置变为 1 需要多少新的 1 补充进来。

对于原始序列，如果原本这里有数，那么如果为 0，则 $f_i=inf$（无论如何都不可能变为 1），如果为 1，那么 $f_i=0$，如果原本没有数，那么 $f_i=1$（只需添加一个 1 就能使当前位置变为 1）

也就是说，我们加入了 $S=\sum_{i=1}^n{f_i}$个大于等于 x 的数，就将原序列变为了全是 1 的序列。

接下来我们考虑变换原序列，题意的变换是将前三个数取出来取中间的数放到最后面并删掉其它两个数，而我们加入了 S 个 1，成功将整个序列都变成了 1，然而我们还想在每次变换后让整个序列剩下 1（直到最后一个数也是 1 满足条件）。易知新加入的数只需要前三个数中有两个数是 1，它就会是 1，因此它的 $f_i$值就是 $min\{f_1+f_2,f_2+f_3,f_1+f_3\}$了啦。

我们用队列去维护上述过程，于是我们就能 $O(n)$验证答案了，总复杂度 $O(nlogn)$

总结：这种题神仙构造性我还是太 naive 了。

代码（有点丑 QAQ）：

#include<bits/stdc++.h> 
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define N 100005
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mod 998244353
#define up 10000
int v, p, n, m, a[N], u[N], w[N], tot, cnt, t[N];
std::queue<ll> q;
inline bool check (int x)
{
    fo (i, 1, n)
        if (!a[i]) q.push(1); else q.push((a[i] < u[x]) ? 1ll << 60 : 0);
    ll d, e, f;
    while (!q.empty())
    {
        d = q.front(); q.pop(); if (q.empty()) return d <= t[x];
        e = q.front(); q.pop(); f = q.front(); q.pop();
        q.push(std::min(std::min(d + e, e + f), std::min(f + d, 1ll << 60)));
    }
}
int main ()
{
    scanf("%d %d", &n, &m);
    fo (i, 1, m)
    {
        scanf("%d %d", &v, &p);
        a[p] = v;
        w[++tot] = v;
        u[tot] = w[tot];
    }
    fo (i, 1, n - m)
    {
        scanf("%d", &w[++tot]);
        u[tot] = w[tot];
    }
    std::sort(u + 1, u + tot + 1);
    cnt = std::unique(u + 1, u + tot + 1) - u - 1;
    fo (i, 1, tot)
    {
        w[i] = std::lower_bound(u + 1, u + cnt + 1, w[i]) - u;
        if (m < i)
            ++t[w[i]];
    }
    fd (i, cnt, 1)
        t[i] += t[i + 1];
    int l = 1, r = cnt;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid))
            l = mid;
        else
            r = mid - 1;
    }
    printf("%d", u[l]);
}