CodeForces - 1159B

佚名 5年前 (2019-07-26) 算法 1500人围观抢沙发百度已收录

题目链接：https://vjudge.net/problem/CodeForces-1159B

题目意思：任选选两个元素，分别为a[i],a[j]。

问都满足K*| i - j | <= min(a[i],a[j]),K的最大值是多少。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

K <= min(a[i],a[j] / | i - j |。

其实就是K要多小才能满足“任选选两个元素，分别为a[i],a[j]。还满足不等式”。

我们可以枚举每个元素，记当前元素下标为index，那么我们只需要选出 max(index - 开头，结尾 - index），然后选出min(a[index],a[离index最远的元素]），计算不等式。

那么我们总会得出那个K至少多小。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <queue>
 6 #include <map>
 7 #include <cmath>
 8 #include <iomanip>
 9 using namespace std;
10 
11 typedef long long LL;
12 #define inf (1LL << 30)
13 #define rep(i,j,k) for(int i = (j); i <= (k); i++)
14 #define rep__(i,j,k) for(int i = (j); i < (k); i++)
15 #define per(i,j,k) for(int i = (j); i >= (k); i--)
16 #define per__(i,j,k) for(int i = (j); i > (k); i--)
17 
18 const int N = 300010;
19 int arr[N];
20 
21 int main(){
22 
23     ios::sync_with_stdio(false);
24     cin.tie(0);
25 
26     int n;
27     cin >> n;
28     rep(i,1,n) cin >> arr[i];
29 
30     int ans = inf;
31     rep(i,1,n){
32 
33         int l = i - 1;
34         int r = n - i;
35 
36         if(l > r){
37             ans = min(ans, min(arr[1],arr[i])/l);
38         }
39         else if(l < r){
40             ans = min(ans, min(arr[n],arr[i])/r);
41         }
42         else if(l == r){
43             ans = min(ans, min(arr[1],arr[i])/l);
44             ans = min(ans, min(arr[n],arr[i])/r);
45         }
46     }
47 
48     cout << ans << endl;
49 
50 
51 
52     getchar();getchar();
53     return 0;
54 }