「题解」「POI2012」井 STU-Well

简单的 二分 题目。

题目链接:Luogu P3534/BZOJ 2792/LibreOJ 2692/POI2012 R1D1T5

题目

题目描述

一句话题意:给你一个正整数数列 $\{x _ n\}$,可以进行 $m$ 次操作,每次操作可以选择一个正整数 $x _ i$ 并将其减一。

在存在 $k$ 使得 $x _ k$ 的情况下,最小化
$$\max _ {i=1,2,\cdots,n-1}\{|x _ i-x _ {i+1}|\}$$

数据范围

变量数据范围
$n$$1\leq n\leq 10^6$
$m$$1\leq m\leq 10^{18}$
$x _ i$$1\leq x _ i\leq 10^9$

时空限制

题目编号时间限制空间限制
Luogu P3534$1\text{s}$$125\text{MiB}$
BZOJ 2792$10\text{s}$$168\text{MiB}$
LibreOJ 2692$1\text{s}$$64\text{MiB}$
POI2012 R1D1T5$1\text{s}$$64\text{MiB}$

题解

思路

不妨二分答案为 $a$,那么我们可以先预先处理出不考虑 $k$ 的限制的答案:

  1. 正序跑一遍,如果 $x _ i-x _ {i-1}>a$,那么我们要修改 $x _ i$ 并计算答案;
  2. 倒序跑一遍,如果 $x _ i-x _ {i+1}>a$,那么我们要修改 $x _ i$ 并计算答案。

回过头来考虑 $a _ k=0$ 的限制。

我们发现,可以枚举 $k$ 把 $a _ k=0$ 的限制转化为两条过 $(k,0)$ 的射线,如图所示:

然后可以发现,新增的答案其实就是超出两条射线的部分,求解即可。

具体的,我们先处理出前缀和,然后用两个指针维护即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline ll read(void){
    reg char ch=getchar();
    reg ll res=0;
    while(ch<'0'||'9'<ch)ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return res;
}

const int MAXN=1000000+5;

int n;
ll m;
int x[MAXN],a[MAXN];
ll sum[MAXN];

inline int check(reg int mid){
    reg ll cnt=0;
    for(reg int i=1;i<=n;++i)
        a[i]=x[i];
    a[n+1]=-1;
    for(reg int i=2;i<=n;++i)
        if(a[i]-a[i-1]>mid){
            cnt+=(a[i]-a[i-1])-mid;
            a[i]=a[i-1]+mid;
        }
    if(cnt>m)
        return 0;
    for(reg int i=n-1;i>=1;--i)
        if(a[i]-a[i+1]>mid){
            cnt+=(a[i]-a[i+1])-mid;
            a[i]=a[i+1]+mid;
        }
    if(cnt>m)
        return 0;
    for(reg int i=1;i<=n;++i)
        sum[i]=sum[i-1]+a[i];
    reg int l=1,r=1;
    for(reg int i=1;i<=n;++i){
        reg int temp=a[i];
        a[i]=0;
        while(a[l]<mid*(i-l))
            ++l;
        while(a[r+1]>=mid*(r-i+1))
            ++r;
        a[i]=temp;
        reg ll S=(1ll*mid*((1ll*(i-l)*(i-l+1)+1ll*(r-i)*(r-i+1))/2));
        if(m-cnt>=(sum[r]-sum[l-1])-S)
            return i;
    }
    return 0;
}

int main(void){
    n=read(),m=read();
    for(reg int i=1;i<=n;++i)
        x[i]=read();
    if(check(0)){
        printf("%d %d\n",check(0),0);
        return 0;
    }
    reg int l=0,r=1e9+1,mid;
    while(l+1!=r){
        mid=(l+r)>>1;
        if(check(mid)!=0)
            r=mid;
        else
            l=mid;
    }
    printf("%d %d\n",check(r),r);
    return 0;
}