首先断环成链，变成两倍长度。
然后二(fen)分(shu)答(gui)案(hua)，查看答案为ans的长度在[L, R]之间的链存不存在。
我们可以维护前缀和，用单调队列O(n)判断是否和大于0
又学习了个黑科技。。。::x表示全局变量x。。。
1 /************************************************************** 2 Problem: 3316 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:1960 ms 7 Memory:5492 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <cmath> 12 #include <algorithm> 13 14 using namespace std; 15 typedef long double llf; 16 typedef long long ll; 17 const int N = 200005; 18 const llf eps = 1e-10; 19 20 int n, L, R, mx, a[N]; 21 llf sum[N]; 22 ll ans1, ans2, gcd; 23 int q[2][N], h[2], t[2]; 24 25 inline int read() { 26 int x = 0; 27 char ch = getchar(); 28 while (ch < '0' || '9' < ch) 29 ch = getchar(); 30 while ('0' <= ch && ch <= '9') { 31 x = x * 10 + ch - '0'; 32 ch = getchar(); 33 } 34 return x; 35 } 36 37 bool check(llf x) { 38 int i; 39 for (i = 1; i <= n; ++i) 40 sum[i] = sum[i - 1] + a[i] - x; 41 h[0] = h[1] = t[0] = t[1] = 0; 42 for (i = L; i <= n; ++i) { 43 int *q = ::q[i & 1], &h = ::h[i & 1], &t = ::t[i & 1], now = i - L; 44 while (h < t && sum[q[t]] > sum[now]) --t; 45 q[++t] = now; 46 while (i - q[h + 1] > R) ++h; 47 if (sum[i] - sum[q[h + 1]] >= 0) { 48 ans2 = i - q[h + 1]; 49 return 1; 50 } 51 } 52 return 0; 53 } 54 55 llf work() { 56 llf l = 0, r = mx, mid; 57 while (r - l > eps) { 58 mid = (l + r) / 2.0; 59 if (check(mid)) l = mid; 60 else r = mid; 61 } 62 return (l + r) / 2.0; 63 } 64 65 int main() { 66 int i; 67 n = read(), L = read(), R = read(); 68 if (L & 1) ++L; 69 if (R & 1) --R; 70 for (i = 1; i <= n; ++i) { 71 a[i] = a[n + i] = read(); 72 mx = max(mx, a[i]); 73 } 74 n <<= 1; 75 76 ans1 = (ll) (work() * ans2 + 0.5); 77 gcd = __gcd(ans1, ans2); 78 ans1 /= gcd, ans2 /= gcd; 79 if (ans2 == 1) printf("%lld ", ans1); 80 else printf("%lld/%lld ", ans1, ans2); 81 return 0; 82 }