#include<bits/stdc++.h> using namespace std; #define ll long long inline int read(){ int s=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); return s*w; } int a[1<<18]; signed main() { for(int T=read();T--;) { int n=read(),l=0,r=1e9,ans=r+1; for(int i=1; i<=n; ++i) a[i]=read(); while(l<=r) { int mid=(l+r)>>1,x=0; for(int i=1; i<=n&&x<=mid; ++i) { int wl=0,wr=min(10000,mid-x),ww=mid-x+1; while(wl<=wr) { int mm=(wl+wr)>>1; ll W=1ll*mm*(mm-1)*(mm-2)/6 +1ll*mm*(mm-1)/2*(mid-mm) +1ll*mm*x*(mid-mm-x); if(W<a[i]) wl=mm+1; else ww=mm,wr=mm-1; } x+=ww; } if(x<=mid) ans=mid,r=mid-1; else l=mid+1; } printf("%d\n",ans); } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | #include<bits/stdc++.h> using namespace std; #define ll long long inline int read(){ int s=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); return s*w; } int a[1<<18]; signed main() { for(int T=read();T--;) { int n=read(),l=0,r=1e9,ans=r+1; for(int i=1; i<=n; ++i) a[i]=read(); while(l<=r) { int mid=(l+r)>>1,x=0; for(int i=1; i<=n&&x<=mid; ++i) { int wl=0,wr=min(10000,mid-x),ww=mid-x+1; while(wl<=wr) { int mm=(wl+wr)>>1; ll W=1ll*mm*(mm-1)*(mm-2)/6 +1ll*mm*(mm-1)/2*(mid-mm) +1ll*mm*x*(mid-mm-x); if(W<a[i]) wl=mm+1; else ww=mm,wr=mm-1; } x+=ww; } if(x<=mid) ans=mid,r=mid-1; else l=mid+1; } printf("%d\n",ans); } return 0; } |