AOJ0600 バームクーヘン
問題ページ
バームクーヘン | Aizu Online Judge
考えたこと
最小値の最大化と言われたので二分探索。判定がO(f(n))であればO(f(n)log(max(A_i)))となる。始点を一箇所固定すればmid以上の最小となるように2箇所切っていくのが最善になる。全パターン確認すれば判定できるのでO(n^2)かけていいなら簡単。判定をO(nlogn)とかO(n)でできれば解けそう。累積和を取っておいて二分探索すれば各始点についてO(logn)で判定できそうなので全体でO(nlognlog(max(A_i)))で解けそう。
累積和が明らかにintに収まる範囲内ではないのでlong longを使う。円環を扱うときは二周分とっておくと実装が楽。
//#define __USE_MINGW_ANSI_STDIO 0 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<ll> VL; typedef vector<VL> VVL; typedef pair<int, int> PII; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define IN(a, b, x) (a<=x&&x<b) #define MP make_pair #define PB push_back const int INF = (1LL<<30); const ll LLINF = (1LL<<60); const double PI = 3.14159265359; const double EPS = 1e-12; const int MOD = 1000000007; #define int ll template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; int n; ll a[200010], b[200010]; bool check(int m) { REP(i, n) { int tmp = i==0 ? 0 : b[i-1]; int itr1 = lower_bound(b+i, b+i+n, tmp+m) - b; int itr2 = lower_bound(b+i, b+i+n, b[itr1]+m) - b; if(b[n+i-1] - b[itr2] >= m) return true; } return false; } signed main(void) { cin >> n; REP(i, n) cin >> a[i]; FOR(i, n, 2*n) a[i] = a[i-n]; b[0] = a[0]; FOR(i, 1, 2*n) b[i] = a[i] + b[i-1]; // [low, high) ll low=1, high=b[n-1]; while(high-low>1) { ll mid = (low+high)/2; if(check(mid)) { low = mid; } else { high = mid; } } cout << low << endl; return 0; }