Codeforces Round #559 (Div. 2) - B. Expansion coefficient of the array
解法
k = ai / max(i, n- i)を全て試せばよい。
例えば、Nを9としたとき
|i-j|の最大値は数列aiから
0 1 2 3 4 5 6 7 8 (要素)と並べたとき
8 7 6 5 4 5 6 7 8 (各要素の|i-j|の最大)
となる。
aiは、その都度、|i-j|の最大値で割るため
aiが最小だろうがなかろうが全て試すため気にしなくてよい。
#include<bits/stdc++.h> using namespace std; #define ALL(g) (g).begin(),(g).end() #define REP(i, x, n) for(int i = x; i < n; i++) #define rep(i,n) REP(i,0,n) #define F(i,j,k) fill(i[0],i[0]+j*j,k) #define P(p) cout<<(p)<<endl; #define EXIST(s,e) ((s).find(e)!=(s).end()) #define INF 1<<30 #define v(T) vector<T> #define vv(T) v(v(T)) typedef vector<int> vi; typedef vector<long long> vl; typedef vector<double> vd; typedef pair<int,int> pii; typedef pair<long,long> pll; typedef long long ll; template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; } int i, j, k; int main() { int n; k = INF; cin >> n; rep(i,n) { int v; cin >> v; k = min(k, v / max(i, (n - i - 1))); } cout << k << endl; return 0; }