QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#345103 | #8242. V-Diagram | oscaryang# | TL | 1ms | 5968kb | C++20 | 1.2kb | 2024-03-06 08:38:53 | 2024-03-06 08:38:54 |
Judging History
answer
#include<bits/stdc++.h>
#define db double
#define vc vector
#define pb emplace_back
#define pii pair<int, int>
#define mkp make_pair
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define lep(i, a, b) for(int i = (a); i >= (b); --i)
using namespace std;
inline int read() {
int x = 0, w = 0; char ch = getchar(); while(!isdigit(ch)) w |= (ch == '-'), ch = getchar();
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar(); return w ? -x : x;
}
const int N = 3e5 + 5;
const db eps = 1e-10, inf = 1e15;
int n, pos;
db a[N], s[N];
inline int check(db v) {
db mx1 = -inf, mx2 = -inf;
rep(i, 1, n)
if(i < pos) mx1 = max(mx1, s[i] - (pos - i) * v);
else if(i > pos) mx2 = max(mx2, s[i] - (i - pos) * v);
return mx1 + mx2 + a[pos] - v >= 0.0;
}
inline void testcase() {
n = read();
rep(i, 1, n) a[i] = read(), s[i] = 0;
rep(i, 2, n) if(a[i] < a[i - 1] && a[i] < a[i + 1]) pos = i;
rep(i, pos + 1, n) s[i] = s[i - 1] + a[i];
lep(i, pos - 1, 1) s[i] = s[i + 1] + a[i];
db l = 0, r = 1e9, mid;
while(l + eps <= r) {
mid = (l + r) / 2.0;
if(check(mid)) l = mid;
else r = mid;
}
printf("%.30lf\n", r);
}
signed main() {
int t = read(); while(t--) testcase();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5968kb
input:
2 4 8 2 7 10 6 9 6 5 3 4 8
output:
6.750000000024964919020931120031 5.833333333352900496038273558952
result:
ok 2 numbers
Test #2:
score: -100
Time Limit Exceeded
input:
100000 3 948511478 739365502 813471668 3 881046825 27458122 398507422 3 987554257 399092415 924260278 3 984128569 125199021 716360525 3 529589236 45783262 313507287 3 645443456 85994112 226010681 3 914820717 228360911 572267310 3 418958362 56703604 195276041 3 64461646 26764720 26995581 3 914535039 ...