草稿

对于 floyd 记录最短路数目及最短路必经点的一些细节:
注意初始边权 \(w[i][i]\) 的设定（ \(0\) or \(Inf\)），以及 floyd 时的转移要特判 \(i!=j\ \&\&\ i!=k\ \&\&\ j!=k\) 。
若我们把 \(w[i][i]\) 设成 \(Inf\) 且不特判，会出现 \(f[i][i]>f[i][k]+f[k][i]\) 的奇怪现象。
若我们把 \(w[i][i]\) 设成 \(0\) 且不特判，会出现 \(f[i][j]=f[i][i]+f[i][j],(k==i)\) 的现象，导致必经点被删去（自己走自己（雾））
综上，还是特判一下比较好。

这个问题一定要记下来，因为想不出来QwQ

#include<bits/stdc++.h>
#define R register int
#define ll long long
using namespace std;
namespace Luitaryi {
inline ll g() { register ll x=0,f=1;
    register char ch; while(!isdigit(ch=getchar())) f=ch=='-'?-1:f;
    do x=x*10+(ch^48); while(isdigit(ch=getchar())); return x*f;
} const int N=1000010;
int n,a[N],mem[N]; ll m,f[N],s[N],ans;
inline bool ck(int x) { ll res=0; memcpy(a,mem,sizeof mem);
    for(R i=2;i<=n;++i) if(a[i]-a[i-1]>x) res+=(a[i]-a[i-1]-x),a[i]=a[i-1]+x;//此处一定要手玩
    if(res>m) return false;
    for(R i=n-1;i;--i) if(a[i]-a[i+1]>x) res+=(a[i]-a[i+1]-x),a[i]=a[i+1]+x;//此处一定要手玩
    if(res>m) return false;
    for(R i=1;i<=n;++i) s[i]=s[i-1]+a[i];
    for(R i=1,j=1;i<=n;++i) {
        while(j<i&&a[j]<=1ll*x*(i-j)) ++j;//找到最靠做左的，会产生代价的点
        f[i]=s[i-1]-s[j-1]-1ll*(i-j)*(i-j+1)/2*x;
    } for(R i=n,j=n;i;--i) {
        while(j>i&&a[j]<=1ll*x*(j-i)) --j;//找到最靠右的，会产生代价的点
        f[i]+=s[j]-s[i]-1ll*(j-i)*(j-i+1)/2*x;
    } for(R i=1;i<=n;++i) if(f[i]+a[i]+res<=m) return ans=i;//计算每个点的代价
    return false;
}
inline void main() { R l=0,r=0; ans=1;
    n=g(),m=g(); for(R i=1;i<=n;++i) mem[i]=g(),r=max(mem[i],r);
    while(l<r) { R md=l+r>>1;//二分答案
        if(ck(md)) r=md;
        else l=md+1;
    } printf("%lld %d\n",ans,l);
}
} signed main() {Luitaryi::main(); return 0;}

边双是可以每个点度数为2，但是不一定每个点度数为2的图就是边双。

要好好利用直径最长性。