洛谷P3466-KLO-Building blocks(主席树)

题目链接:洛谷P3466-KLO-Building blocks

题意:

给n个数,然后每次操作可以把任意一个数加一或者减一,要求使连续k个相等,输出最少操作次数和最后得到的数组。

题解:

为了使操作次数最小,所以我们选择区间的中位数作为最终结果是最优的。主席树维护即可。

参考代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e6 + 6;
const int inf = 0x3f3f3f3f;
int n, k;
int a[MAXN];
int tot, Tree[MAXN * 20], ls[MAXN * 20], rs[MAXN * 20], sum[MAXN * 20];
ll S[MAXN * 20];
void update(int las, int val, int l, int r, int &rt)
{
    rt = ++tot;
    ls[rt] = ls[las], rs[rt] = rs[las];
    sum[rt] = sum[las] + 1;
    S[rt] = S[las] + val;
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    if (val <= mid)
        update(ls[las], val, l, mid, ls[rt]);
    else
        update(rs[las], val, mid + 1, r, rs[rt]);
}
int query(int L, int R, int l, int r, int K)
{
    if (l == r)
        return l;
    int mid = (l + r) >> 1;
    int lson = sum[ls[R]] - sum[ls[L]];
    if (K <= lson)
        return query(ls[L], ls[R], l, mid, K);
    else
        return query(rs[L], rs[R], mid + 1, r, K - lson);
}
ll siz = 0, Sum = 0;
void query_sum(int L, int R, int l, int r, int lt, int rt)
{
    if (L <= l && r <= R)
    {
        siz += sum[rt] - sum[lt];
        Sum += S[rt] - S[lt];
        return;
    }
    int mid = (l + r) / 2;
    if (L <= mid)
        query_sum(L, R, l, mid, ls[lt], ls[rt]);
    if (R > mid)
        query_sum(L, R, mid + 1, r, rs[lt], rs[rt]);
}
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        update(Tree[i - 1], a[i], 0, 1000000, Tree[i]);
    ll ans = 0x7f7f7f7f7f7f7f7f;
    int l, r, flag;
    for (int i = 1; i <= n - k + 1; i++)
    {
        int j = i + k - 1;
        int now = query(Tree[i - 1], Tree[j], 0, 1000000, k / 2 + 1);
        ll tmp = 0;
        Sum = siz = 0;
        query_sum(0, now, 0, 1000000, Tree[i - 1], Tree[j]);
        tmp += abs(Sum - siz * now);
        Sum = siz = 0;
        query_sum(now + 1, 1000000, 0, 1000000, Tree[i - 1], Tree[j]);
        tmp += abs(Sum - siz * now);
        if (ans > tmp)
            ans = tmp, l = i, r = j, flag = now;
        // ans=min(ans,tmp);
    }
    printf("%lld\n", ans);
    for (int i = 1; i < l; i++)
        printf("%d\n", a[i]);
    for (int i = l; i <= r; i++)
        printf("%d\n", flag);
    for (int i = r + 1; i <= n; i++)
        printf("%d\n", a[i]);
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。