BZOJ 1122 - [POI2008]账本BBB

#贪心 #滑动窗口 #单调队列
Published on 2016-09-22

题目地址

描述

一个长度为 nn 的记账单，+ 表示存 1 元，- 表示取 1 元。现在发现记账单有问题，一开始本来已经存了 pp 元，并且知道最后账户上还有 qq 元。你要把记账单修改正确，使得

  1. 账户永远不会出现负数
  2. 最后账户上还有 qq 元

你有 2 种操作：

  1. 对某一位取反，耗时 xx
  2. 把最后一位移到第一位，耗时 yy

分析

首先，第二种操作至多使用 n−1n - 1 次，所以我们枚举使用次数 。将账单翻倍，我们考虑对 [k,k+n)[k, k + n) 快速求出使用第一种操作的次数。
记录一下账单的前缀和 sis_i，设 x=∣p+sn−1−q∣2x = \frac {\mid p + s_{n - 1} - q\mid}{2}，这里只考虑 p+sn−1<qp + s_{n - 1} < q 的情况，另外一种情况是类似的。
为了满足最后还有 qq 元，我们要把 xx 个 - 变为 +，根据贪心，我们显然是要将最前面的 xx 个 - 变为 +，这样第一条要求更容易满足。在修改后，求出前缀和的最小值为 MM，则如果 M+p≥0M + p \ge 0，必然已经满足了第一条要求，否则令 y=⌊1−M2⌋y = \lfloor \frac {1 - M} 2\rfloor，我们需要将最前面的 yy 个 - 变为 +，最后面的 yy 个 + 变为 -，这样就能满足所有要求了。

使用单调队列来维护前缀和最小值，再用滑动窗口来维护 [k,j][k, j] 区间内有 xx 个 -，这应该都是基本功了。

代码

//  Created by Sengxian on 09/22/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 1122 贪心 + 单调队列
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 1000000 + 3;
int n, p, q, x, y;
int a[MAX_N * 2], s[MAX_N * 2];

int que[MAX_N * 2];
int l = 0, r = 0;

inline void insert(int k) {
    while (r - l >= 1 && s[que[r - 1]] > s[k]) r--;
    que[r++] = k;
}

inline void erase(int k) {
    if (que[l] == k) l++;
}

inline int front() {
    return que[l];
}

void solve() {
    int cnt = abs(s[n - 1] + p - q) / 2;

    ll ans = 0x3f3f3f3f3f3f3f3fLL;

    if (s[n - 1] + p >= q) {
        int j = n * 2 - 1, c = 0;
        while (c < cnt) c += a[j--] == 1;
        ++j;
        for (int k = n; k < j; ++k) insert(k);
        for (int i = n - 1; i >= 0; --i) {
            insert(i);
            if (a[i + n] == 1) {
                while (a[j - 1] != 1) erase(--j);
                erase(--j);
            }

            int m = s[front()] - (i == 0 ? 0 : s[i - 1]) + p;
            if (m >= 0) m = 1;
            ans = min(ans, (n - i) % n * (ll)y + (ll)(cnt + (1 - m) / 2 * 2LL) * x);
        }
    } else {
        int j = n, c = 0;
        while (c < cnt) c += a[j++] == -1;
        j--;
        for (int k = 2 * n - 1; k > j; --k) insert(k);
        for (int i = n - 1; i >= 0; --i) {
            erase(i + n);

            if (a[i] == -1) {
                insert(j--);
                while (a[j] != -1) insert(j--);
            }

            int m = j - i + 1 + p + s[front()] - s[j];
            if (m >= 0) m = 1;
            ans = min(ans, (n - i) % n * (ll)y + (cnt + ((1 - m) / 2) * 2LL) * x);
        }
    }
    printf("%lld\n", ans);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    n = ReadInt(), p = ReadInt(), q = ReadInt(), x = ReadInt(), y = ReadInt();
    static char str[MAX_N];
    scanf("%s", str);
    for (int i = 0; i < n; ++i)
        a[i] = a[i + n] = str[i] == '+' ? 1 : -1;
    s[0] = a[0];
    for (int i = 1; i < n * 2; ++i) s[i] = s[i - 1] + a[i];
    solve();
    return 0;
}
BZOJ 1128 - [POI2008]Lam