Description

题目链接

Solution

对于 $1$ 操作,每次选择 $[1, n]$ 必然不劣。

对于 $2$ 操作,由于求的是最大子段和,因此不难发现每次选择 $[1, n]$ 还是最优的。

这样本题看起来很奇怪的两个地方就都解决了。

接下来考虑枚举进行 $2$ 操作之后二分 $1$ 操作,由于这道题数据范围不小,因此会炸 long long

我实在不想卡了,所以贺了个代码。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef unsigned long long uLL;
typedef long long LL;

LL a[100010];
LL n, s, sa, sb, cnt2, ans = 1LL << 62 - 1LL;

bool check(LL mid) {
    LL sum = 0, max = -2e18;
    for (int i = 1; i <= n; ++i) {
        sum = std::max(sum + a[i] + mid, a[i] + mid);
        max = std::max(max, sum);
    }
    return max >= ceil(s * 1.0 / (1LL << cnt2));
}

int main() {
    ans = ans * 2LL;
    read(n), read(sa), read(sb), read(s);
    for (int i = 1; i <= n; ++i)    read(a[i]);
    for (cnt2 = 0; cnt2 <= 32; ++cnt2) {
        LL l = 0, r = 2e18, md;
        while (l <= r) {
            LL mid = (l + r) >> 1LL;
            if (check(mid))    md = mid, r = mid - 1;
            else    l = mid + 1;
        }
        ans = std::min(ans, sa * md + sb * cnt2);
    }
    printf("%lld\n", ans);
    return 0;
}
Last modification:September 2nd, 2021 at 02:18 am