B. Expansion coefficient of the array
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Let's call an array of non-negative integers a1,a2,…,ana1,a2,…,an a kk-extension for some non-negative integer kk if for all possible pairs of indices 1≤i,j≤n1≤i,j≤n the inequality k⋅|i−j|≤min(ai,aj)k⋅|i−j|≤min(ai,aj) is satisfied. The expansion coefficient of the array aa is the maximal integer kk such that the array aa is a kk-extension. Any array is a 0-expansion, so the expansion coefficient always exists.
You are given an array of non-negative integers a1,a2,…,ana1,a2,…,an. Find its expansion coefficient.
Input
The first line contains one positive integer nn — the number of elements in the array aa (2≤n≤3000002≤n≤300000). The next line contains nn non-negative integers a1,a2,…,ana1,a2,…,an, separated by spaces (0≤ai≤1090≤ai≤109).
Output
Print one non-negative integer — expansion coefficient of the array a1,a2,…,ana1,a2,…,an.
Examples
input
Copy
代码语言：javascript复制4
6 4 5 5output
Copy
代码语言：javascript复制1input
Copy
代码语言：javascript复制3
0 1 2output
Copy
代码语言：javascript复制0input
Copy
代码语言：javascript复制4
821 500 479 717output
Copy
代码语言：javascript复制239Note
In the first test, the expansion coefficient of the array [6,4,5,5][6,4,5,5] is equal to 11 because |i−j|≤min(ai,aj)|i−j|≤min(ai,aj), because all elements of the array satisfy ai≥3ai≥3. On the other hand, this array isn't a 22-extension, because 6=2⋅|1−4|≤min(a1,a4)=56=2⋅|1−4|≤min(a1,a4)=5 is false.
In the second test, the expansion coefficient of the array [0,1,2][0,1,2] is equal to 00 because this array is not a 11-extension, but it is 00-extension.
题意：定义k为一个数组的关键参数，k满足任意的1<=i<=j<=n,有|i−j|≤min(ai,aj)，且k是满足此条件下最大的，求k
思路：有点小聪明的一道题，如果两重循环暴力的话铁憨憨超时，但我们不妨换个角度，k<=min(a[i],a[j])/abs(i-j),肯定这个k是要对所有的i，j满足，所有都满足这个条件就是取所有对（i，j）中的最小，从min(a[i],a[j])入手，无非就是每个元素值都跑一遍，假设是ax，那么对于给定的下标x的元素已被选中，分母要最大k最小（所有情况都要满足嘛），就是首尾（i-1.n-i）两种情况
代码语言：javascript复制// luogu-judger-enable-o2
#include<bits/stdc .h>
#include<unordered_set>
#define rg register ll
#define inf 2147483647
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define ll long long
#define maxn 300005
const double eps = 1e-6;
using namespace std;
inline ll read()
{
char ch = getchar(); ll s = 0, w = 1;
while (ch < 48 || ch>57) { if (ch == '-')w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) { s = (s << 1) (s << 3) (ch ^ 48); ch = getchar(); }
return s * w;
}
inline void write(ll x)
{
if (x < 0)putchar('-'), x = -x;
if (x > 9)write(x / 10);
putchar(x % 10 48);
}
ll n,a[maxn];
int main()
{
cin>>n;
ll minn=inf;
for(rg i=1;i<=n;i )a[i]=read(),minn=min(a[i]/(max(i-1,n-i)),minn);
cout<<minn<<endl;
return 0;
}
