先二分z 然后将序列调整成相邻数字的差都不超过z 计算对于每个位置i将它调成0，维护序列需要的操作次数，比如计算左侧的贡献，用j表示最左一个点不满足abs(a[i]-a[j])<=(i-j)*z，随i的增加j单调递增，且因为之前已经将序列调整过使得相邻数字差不超过z，所以可以O(1)算出j~i调整的操作次数，对于右侧点类似
code：
#include<set>#include<map>#include<deque>#include<queue>#include<stack>#include<cmath>#include<ctime>#include<bitset>#include<string>#include<vector>#include<cstdio>#include<cstdlib>#include<cstring>#include<climits>#include<complex>#include<iostream>#include<algorithm>#define ll long long#define lowbit(x) x&(-x)using namespace std;void read(ll &x){ char c; while(!((c=getchar())>='0'&&c<='9')); x=c-'0'; while((c=getchar())>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0';}const int maxn = 1100000;ll n,m,a[maxn];ll b[maxn];ll l,r;ll s[maxn];ll lx[maxn],rx[maxn];ll judge(ll x){ ll sum=0; for(ll i=1;i<=n;i++) s[i]=0,b[i]=a[i]; for(ll i=2;i<=n;i++) { if(b[i]>b[i-1]+x) sum+=b[i]-b[i-1]-x,b[i]=b[i-1]+x; } for(ll i=n-1;i>=1;i--) { if(b[i]>b[i+1]+x) sum+=b[i]-b[i+1]-x,b[i]=b[i+1]+x; } if(sum>m) return 0; for(ll i=1;i<=n;i++) s[i]=s[i-1]+b[i]; ll left,right; left=1; for(ll i=1;i<=n;i++) { while(left<i&&b[left]<=(i-left)*x) left++; lx[i]=left==i?0:s[i-1]-s[left-1]-x*(i-left+1ll)*(i-left)/2ll; } right=n; for(ll i=n;i>=1;i--) { while(right>i&&b[right]<=(right-i)*x) right--; rx[i]=right==i?0:s[right]-s[i]-x*(right-i+1ll)*(right-i)/2ll; } for(ll i=1;i<=n;i++) if(sum+lx[i]+rx[i]+b[i]<=m) return i; return 0;}ll solve(ll &ans){ ll temp; while(l<=r) { ll mid=(l+r)>>1; if(temp=judge(mid)) r=mid-1,ans=temp; else l=mid+1; } return r+1;}int main(){ read(n); read(m); l=r=0; for(ll i=1;i<=n;i++) { read(a[i]); if(r<a[i]) r=a[i]; } ll Z,K; Z=solve(K); PRintf("%lld %lld/n",K,Z); return 0;}新闻热点
疑难解答
