P7287 「EZEC-5」魔法
感觉好题有思维,但是我没认真读题,看到样例就我以为了,他让任意一个区间满足大于 \(S\) 即可不是全部。
我们手搓一下样例就可以发现,对于加法我们不加白不加的话肯定全部的数都加上,乘法肯定要等到加完后才开始,这些都是贪心思路。
然后就是开始搭配操作了,我遇到的一些题直接就开始暴搜了,但是这题数据不是很好,看到数据范围想到二分答案,我们 \(\times 2\) 操作明显更少,所以我们枚举乘、二分答案加。
我们将操作后的数赋到一个新的数组上,然后因为只要一个区间,所以直接最大子段和。
然后这道 easy 题就简单秒掉了!!!
#include <bits/stdc++.h>
#define int long long
#define ls p<<1
#define rs p<<1|1
#define re register
#define ll long long
const int N=1e5+10;
const int mod=998244353;
using namespace std;
int n,x,y,k;
int a[N];
__int128 b[N];
bool check(__int128 add,__int128 mul){
for(int i=1;i<=n;i++){
b[i]=(a[i]+add)*mul;
}
int maxx=0,now=0;
for(int i=1;i<=n;i++){
now=max(now+b[i],b[i]);
maxx=max(maxx,now);
}
return maxx>=k;
}
int getans(int mul){
int ans=mul*y;
int l=0,r=2e9+10,mid;
while(l<r){
mid=(l+r)>>1;
if(check(mid,1ll<<mul)){
r=mid;
}
else{
l=mid+1;
}
}
ans+=l*x;
return ans;
}
signed main(){
// freopen("kingdom3.in","r",stdin);
// freopen("a.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>x>>y>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int ans=1e18;
for(int i=0;i<=30;i++){
ans=min(ans,getans(i));
}
cout<<ans;
return 0;
}
标签:洛谷,int,题解,魔法,mid,P7287,EZEC
From: https://www.cnblogs.com/sadlin/p/18542593