Codeforces Round 890 (Div. 2) C. To Become Max(二分 补写法 二分套二分)

题目

给定一个长度为n(n<=1e3)的数组，

在一次操作里，你可以选择一个满足a[i]<=a[i+1]的下标i(1<=i<=n-1)，对a[i]加一

问，你最多操作k次的情况下，数组的最大值是多少，输出最大值

思路来源

Submission #217368352 - Codeforces

题解

这题是n=1e3的，正常的写法的写法很多，对于每个值，二分其最大答案

比如我赛中的提交，Submission #217328890 - Codeforces

Bonus

这里给出一种n=1e5的做法，

Hint

以样例里最具代表性的case为例，

n=5,k=6

6 5 4 1 5

可以令a[4]+3，然后令a[3]+1，令a[2]+1，令a[1]+1，最后答案是7

最终序列是形如7 6 5 4 5，记做A数组，

而7 6 5 4是我们取得的一段，记做A[l,r]，

显然，需要满足，

①：A[r]>=a[r+1]-1

即所取区间的最后一个值，大于等于初始序列下一个位置的值减1，不然无法拔高a[r]

②：此外，A序列最终答案[l,r]还一定是一段连续的、后项=前项-1的区间，

所以，这启发我们先给a[i]用初值拉齐，构造b[i]=a[i]-(n-i)

a: 6 5 4 1 5

b: 1 1 1 -1 4

终态数组

这里用A、B，和初始a、b区分

A: 7 6 5 4 5

B: 2 2 2 2 4

最终我们取的B区间是[2,2,2,2]，

观察①限制，发现在新数组中，等价于B[r]<=b[r+1]

贪心最小代价时，需要找到[i,n]里满足>=B[r]的最左位置

而2就是最终的取值v（v=B[l]=...=B[r]），被还原回去，w=v+(n-i)，也就是7

Solution

1. 根据a序列，构造新序列b[i]=a[i]-(n-i)

2. ST表预处理出b[i]的区间最大值，预处理b[i]的前缀和

3. 二分最终答案w，w在B序列里考虑时，B[i]=w-(n-i)

4. 通过ST表+二分，找到满足b[j]>=B[i]的最小的j(j>=i)，

也就意味着，[i,j)这一段都是<B[i]的，都需要被拔高，利用前缀和，判断k次机会，是否可满足

代码

// #include<bits/stdc++.h>
#include<iostream>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=1e5+10,M=20,INF=0x3f3f3f3f;
int t,n,k,a[N],b[N],mx[N][M],lg[N];
ll sum[N];
void init(){
    for(int i=2;i<N;++i){
        lg[i]=lg[i>>1]+1;
    }
}
//最大值的最左位置
void ST(int n){
    for(int i=1;i<=n;++i)mx[i][0]=b[i];
	for(int len=1;(1<<len)<=n;++len){
		for(int i=1;i+(1<<len)-1<=n;++i){
			mx[i][len]=max(mx[i][len-1],mx[i+(1<<(len-1))][len-1]);
		}
	}
}
int RMQ(int l,int r){
	int k=lg[r-l+1];
    return max(mx[l][k],mx[r-(1<<k)+1][k]);
}
ll cal(int l,int r){
    return sum[r]-sum[l-1];
}
bool ok(int v){
    rep(i,1,n-1){
        int w=v-(n-i),p=RMQ(i+1,n);//[2,2,2,>=2] [i,p] b[l]=b[l+1]=...=b[p-1]<=b[p] [i,p-1)拔高,p不变
        if(p<w)continue;
        int l=i+1,r=n;//>=w的最左位置
        while(l<=r){
            int mid=(l+r)/2;
            if(RMQ(i+1,mid)>=w)r=mid-1;
            else l=mid+1;
        }
        if(cal(i,l-1)+k>=1ll*(l-i)*w){
            return 1;
        }
    }
    return 0;
}
int sol(){
	int ans=0;
	rep(i,1,n){
        ans=max(ans,a[i]);
        b[i]=a[i]-(n-i);
        sum[i]=sum[i-1]+b[i];
    }
    ST(n);
    int l=ans+1,r=ans+k;
    while(l<=r){
        int mid=(l+r)/2;
        if(ok(mid))l=mid+1;
        else r=mid-1;
    }
	return r;
}
int main(){
    init();
	sci(t);
	rep(j,1,t){
		sci(n),sci(k);
		rep(i,1,n)sci(a[i]);
        pte(sol());
	}
	return 0;
}
/*
3
31 1
99999997 99999997 99999997 99999997 99999997 99999999 100000000 99999999 100000000 100000000 99999998 99999999 100000000 99999997 99999998 99999998 99999999 100000000 99999998 100000000 99999998 100000000 99999997 99999997 99999997 99999998 100000000 99999997 99999998 99999997 100000000
*/