www.网站建设/贴吧友情链接在哪

题意翻译

给定一个非负整数序列A，每次操作可以选择一个数然后减掉1，要求进行不超过m次操作使得存在一个Ak=0且max⁡(∣xi−xi−1∣)最小，输出这个最小值以及此时最小的k

(1≤n≤1 000 000，1≤m≤10^18)

题解：

最大值最小，还要输出，那就直接二分咯。

由于每次都只能减，所以，

每次二分的内部，可以先把max(|xi-xi-1|)调出来。

从左到右扫一遍，a[i]>a[i-1]+mid 那么a[i]=a[i-1]+mid tot+=a[i]-（a[i-1]+mid)

从右到左扫一遍，a[i-1]>a[i]+mid 同理。

注意循环顺序。因为不能先砍最高的。可能之后更低的会更低。

这样最少的次数保证了max(..)<=mid

然后改枚举最低点的k了。

如果不存在一个点为0

那么，这个点为k的话，两边一定是一个倒阶梯。

回文阶梯形状双等差数列

这个阶梯的L，R有单调性。（L即为i左边第一个可以不用删的位置。R为i右边第一个可以不用删的位置。）

可以直接移动。

具体一些，如果L+1位置比所需的小，那么可以右移L，

如果R不行，那么右移R，直到比所需的位置小。其实同理。

 

 

 

注意，正反循环顺序保证正确性。

双指针移动判定条件及边界。

等差数组求和别写错...

 

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000000+5;
int n;
ll m;
ll a[N],b[N],c[N];
ll ans,pos;
int lp;//min a[k]'s k
bool che(ll mid){memcpy(b,a,sizeof a);ll tot=0;lp=0;for(int i=n-1;i;i--){if(b[i]-b[i+1]>mid) tot+=b[i]-(b[i+1]+mid),b[i]=b[i+1]+mid; }for(int i=2;i<=n;i++){if(b[i]-b[i-1]>mid) tot+=b[i]-(b[i-1]+mid),b[i]=b[i-1]+mid;}if(tot>m) return false;ll L=1,R=1;ll sum=0;ll len=0,nd=0;for(int i=1;i<=n;i++){while(R<n&&b[R]>=(R-i)*mid) sum+=b[R],R++;while(L<i&&b[L]<=(i-L)*mid) sum-=b[L],L++;len=R-i-1;nd=(len+1)*len/2*mid;len=i-L;nd+=(len+1)*len/2*mid;if(sum-nd+tot<=m){lp=i;return true;}}return false;
}
int main()
{scanf("%d%lld",&n,&m);ll l=0,r=0;for(int i=1;i<=n;i++){scanf("%lld",&a[i]);r=max(r,a[i]);}while(l<=r){ll mid=(l+r)>>1;if(che(mid)) ans=mid,pos=lp,r=mid-1;else l=mid+1;}printf("%lld %lld",pos,ans);return 0;
}