题解 P2418 【yyy loves OI IV】

· · 题解

设F[i]表示将前i个人处理完毕所要用的最少寝室个数

考虑暴力的O(n^2)的转移，我们会发现，时间大多数用在了寻找最小且满足条件的情况

可以考虑分情况讨论，对于都是膜拜一个人的情况用数组记录，对于膜拜人数的绝对值不大于M的情况，化简得到一个不等式，然后用线段树（单点修改，区间最值）记录。

具体分析看我的代码和代码开头的注释。


//j~i可以放在一间宿舍(j<=i)  c01[i]表示前i个人中膜拜c01的人数，yyy[i]同理
//情况1：c01[j - 1] = c01[i]
//情况2：yyy[j - 1] = c01[i]
//情况3：设a = yyy[i] - yyy[j - 1]   b = c01[i] - c01[j - 1]
//       |a - b| <= M
//需满足：①a - b <= M 
//        =>(yyy[i] - yyy[j - 1]) - (c01[i] - c01[j - 1]) <=M
//        =>yyy[i] - yyy[j - 1] - c01[i] + c01[j - 1] <= M
//        =>c01[j - 1] - yyy[j - 1] <= M + c01[i] - yyy[i] 
//      ②b - a <= M
//        =>yyy[j - 1] - c01[j - 1] <= M + yyy[i] - c01[i]
//        =>c01[j - 1] - yyy[j - 1] >= c01[i] - yyy[i] - M
//整理可得 情况3等价于：
// c01[i] - yyy[i] - M <= c01[j - 1] - yyy[j - 1] <= M + c01[i] - yyy[i]

//情况1和情况2用数组记录，情况3用线段树处理 时间复杂度O(nlogn) 

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const size_t Max_N(500050);
const int Add(500000);
const int INF(0X3F3F3F3F);

void Get_Val(int &Ret)
{
    Ret = 0;
    char ch;
    while ((ch = getchar()), (ch > '9' || ch < '0'))
        ;
    do
    {
        (Ret *= 10) += ch - '0';
    }
    while ((ch = getchar()), (ch >= '0' && ch <= '9'));
}

struct node
{
    int l, r;
    int Min;
};

struct Segment_Tree
{
    node segt[Max_N << 3];
    void build_tree(const int&, const int&, const int&);
    void change(const int&, const int&, const int &);
    int rmq_min(const int&, const int&, const int&);
    inline
    void pushup(const int &cur)
    {
        segt[cur].Min = min(segt[cur << 1].Min, segt[(cur << 1) | 1].Min);
    }
};
Segment_Tree Space;

void Segment_Tree::build_tree(const int &cur, const int &l, const int &r)
{
    segt[cur].l = l, segt[cur].r = r, segt[cur].Min = INF;
    if (l == r)
        return;
    int mid = l + ((r - l) >> 1);
    build_tree(cur << 1, l, mid);
    build_tree((cur << 1) | 1, mid + 1, r);
}

void Segment_Tree::change(const int &cur, const int &i, const int &x)
{
    if (segt[cur].l == i && segt[cur].r == i)
    {
        segt[cur].Min = x;
        return;
    }
    int mid = segt[cur].l + ((segt[cur].r - segt[cur].l) >> 1);
    if (i <= mid)
        change(cur << 1, i, x);
    else
        change((cur << 1) | 1, i, x);
    pushup(cur);
}

int Segment_Tree::rmq_min(const int &cur, const int &l, const int &r)
{
    if (segt[cur].l == l && segt[cur].r == r)
        return segt[cur].Min;
    int mid = segt[cur].l + ((segt[cur].r - segt[cur].l) >> 1);
    if (r <= mid)
        return rmq_min(cur << 1, l, r);
    else
        if (l > mid)
            return rmq_min((cur << 1) | 1, l, r);
        else
            return min(rmq_min(cur << 1, l, mid), rmq_min((cur << 1) | 1, mid + 1, r));
}

int N, M;
int c01[Max_N], yyy[Max_N];

int F[Max_N];
int c01_dp[Max_N], yyy_dp[Max_N];
int Minus[Max_N << 1];

void init()
{
    int v;
    Get_Val(N), Get_Val(M);
    for (int i = 1;i <= N;++i)
    {
        Get_Val(v);
        yyy[i] = yyy[i - 1] + (v == 1);
        c01[i] = c01[i - 1] + (v == 2);
    }
}

void dp()
{
    memset(c01_dp, 0X3F, sizeof(c01_dp));
    memset(yyy_dp, 0X3F, sizeof(yyy_dp));
    memset(Minus, 0X3F, sizeof(Minus));
    Minus[0 + Add] = c01_dp[0] = yyy_dp[0] = F[0] = 0;
    Space.build_tree(1, -500000, 500000);
    Space.change(1, 0, 0);
    int a, b, c;
    for (int i = 1;i <= N;++i)
    {
        a = c01_dp[c01[i]];
        b = yyy_dp[yyy[i]];
        c = Space.rmq_min(1, c01[i] - yyy[i] - M, M + c01[i] - yyy[i]);
        F[i] = min(min(a + 1, b + 1), min(c + 1, F[i - 1] + 1));
        c01_dp[c01[i]] = min(c01_dp[c01[i]], F[i]);
        yyy_dp[yyy[i]] = min(yyy_dp[yyy[i]], F[i]);
        if (F[i] < Minus[c01[i] - yyy[i] + Add])
        {
            Minus[c01[i] - yyy[i] + Add] = F[i];
            Space.change(1, c01[i] - yyy[i], F[i]);
        }
    }
    printf("%d", F[N]);
}

int main()
{
    init();
    dp();
    return 0;
}