#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define rep(a, b) for(int a = 0; a < (b); ++a) #define st first #define nd second #define pb push_back #define all(a) a.begin(), a.end() const int LIM=2e5+7; ll T[LIM], n; ll calc(ll a, ll b, ll c) { return a*b*c + b*(b-1)/2 * (a+c) + b*(b-1)*(b-2)/6; } bool check(ll x) { ll y=0; rep(i, n) { if(!T[i]) continue; ll po=0, ko=x-y; if(x-y==0) return false; if(calc(y, 1, x-y-1)>=T[i]) { ++y; continue; } while(po<ko) { ll sr=(po+ko)/2; if(calc(y, sr, x-y-sr)<T[i]) po=sr+1; else ko=sr; } if(calc(y, po, x-y-po)<T[i]) return false; y+=po; } return true; } void solve() { cin >> n; rep(i, n) cin >> T[i]; ll po=0, ko=n+2000; while(po<ko) { ll sr=(po+ko)/2; if(check(sr)) ko=sr; else po=sr+1; } cout << po << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int _=1; cin >> _; while(_--) solve(); }
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 42 43 44 45 46 47 48 49 | #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define rep(a, b) for(int a = 0; a < (b); ++a) #define st first #define nd second #define pb push_back #define all(a) a.begin(), a.end() const int LIM=2e5+7; ll T[LIM], n; ll calc(ll a, ll b, ll c) { return a*b*c + b*(b-1)/2 * (a+c) + b*(b-1)*(b-2)/6; } bool check(ll x) { ll y=0; rep(i, n) { if(!T[i]) continue; ll po=0, ko=x-y; if(x-y==0) return false; if(calc(y, 1, x-y-1)>=T[i]) { ++y; continue; } while(po<ko) { ll sr=(po+ko)/2; if(calc(y, sr, x-y-sr)<T[i]) po=sr+1; else ko=sr; } if(calc(y, po, x-y-po)<T[i]) return false; y+=po; } return true; } void solve() { cin >> n; rep(i, n) cin >> T[i]; ll po=0, ko=n+2000; while(po<ko) { ll sr=(po+ko)/2; if(check(sr)) ko=sr; else po=sr+1; } cout << po << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int _=1; cin >> _; while(_--) solve(); } |