题目

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

题解

这道题真的毒瘤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]);
}
分类: 文章

quhengyi11

喵(ฅ>ω<*ฅ)

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *