题解 P7287 【「EZEC-5」魔法】

· · 题解

题意：

给定一个长度为 n 的数列，每次可以选择一段区间 \times2 或 +1 ，不同操作有不同的代价。问在有一段连续子区间和 >\ S 的情况下，最小代价为多少。

\mathcal{Sol:}

蒟蒻一开始看到题目毫无思路，便开始看数据范围。

发现 1 \le n \le 10^5 ！这不妥妥的 \mathcal{O(n\ log\ n)} 算法嘛。稍微一想便可以明确主要算法为二分。

好了回归正题：既然要使用二分，那么该问题的单调性是什么呢？

魔法1 ：如果使用 n 次可以满足要求，那么 n+1 次的魔法也一定满足要求 。

魔法2 ：如果使用 n 次可以满足要求，那么 n+1 次的魔法也一定满足要求 。

好了，单调性找到了。似乎两个魔法都可以二分，但是 魔法1 的最大操作次数是 S\ (1 \le S \le 10^9) ，如果枚举该魔法肯定凉凉。所以考虑枚举 魔法2 ，该魔法最大操作次数约为 \mathcal{log (S)} ，效率还是很可观的。

那么既然确定了二分的魔法是魔法1，那我们就来思考二分怎么写，首先二分的模版如下（笔者习惯的打法）：

bool check (int now) {
    //something
}
int l = 0, r = MAX;
while (l <= r) {
    int mid = l + (r - l) / 2;
   if ( check(mid) ) r = mid - 1; 
        else l = mid + 1;
}

这个 check 函数是用来判断 魔法1 使用次数为 now ，在枚举的 魔法2 使用次数下，能否满足有一个子序列和 >\ S 。

这里需要用到一个贪心的思想：因为 魔法2 使用的是乘法，对一个负数使用的话会使和更小，所以我们只对和为正数的子序列使用魔法。这就类似于求最大子段和的方法，若您想更对的地了解关于最大子段和的求法，可以参考这道题的题解，这里不再赘述，直接给出代码。

bool check (int now) {
    int t = 0, ans = (-1) * 1ll << 62;
    for (int i = 1 ; i <= n ; ++ i) {
        if (t < 0) t = 0;
        t += a[i] + x;
        ans = max(ans, t);
    }
    return ans >= ceil(S * 1.0 / (1ll << k));
    //这里的k就是枚举的魔法2次数，用除法是为了防爆long long
}

综上，我们得到了一个复杂度为 \mathcal{O}(n\times log(S)\times 63) 的算法。

Code:

#include <bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>
void read (T& x) {
    char c=getchar(); int w=0; x=0;
    for (;!isdigit(c);c=getchar()) w^=!(c^45);
    for (;isdigit(c);c=getchar()) x=(x*10)+(c^48);
    x=w?-x:x;
}
const int MAXN=2e5+10;
typedef long long ll;
int n,k,A,B,S;
int l,r,mid;
ll ans=1ll<<62-1ll;
ll a[MAXN];
bool check (int x) {
    int t=0,ans=(-1)*1ll<<62;
    for (int i=1;i<=n;++i) {
        if (t<0) t=0;
        t+=a[i]+x;
        ans=max(ans,t);
    }
    return ans>=ceil(S*1.0/(1ll<<k));
}
signed main () {
    ans=ans*2ll;
    read(n),read(A),read(B),read(S);
    for (int i=1;i<=n;++i) read(a[i]);
    for (k=0;k<=32;++k) {
        l=0; r=1e18; //上界记得开大，不然会WA
        while (l<=r) {
            mid=l+(r-l)/2;
            if (check(mid)) r=mid-1; else l=mid+1;
        }
        ans=min(ans,(ll)A*l+B*k);
    }
    printf("%lld",ans);
}

Upd:

1.感谢SSerxhs提醒，修改sb错误。

2.感谢SSerxhs的hack，修改了部分代码。