QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#634235 | #8242. V-Diagram | cy325 | WA | 74ms | 4088kb | C++20 | 2.5kb | 2024-10-12 16:55:21 | 2024-10-12 16:55:21 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
scanf("%d", &n);
vector<long long> a(n + 2);
a[0] = LLONG_MAX;
a[n + 1] = LLONG_MAX;
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
// 找到 V 图的最低点(即转折点)
int tip = -1;
for (int i = 2; i <= n - 1; i++) {
if (a[i - 1] > a[i] && a[i] < a[i + 1]) {
tip = i;
break;
}
}
if (tip == -1) {
// 如果没有找到转折点,整个序列可能是单调的,但根据题目保证,这种情况不会发生
tip = 1;
}
double maxAvg = a[tip]; // 初始化最大平均值为 tip 位置的元素值
long long sum = a[tip];
int len = 1;
// 从 tip 开始,向右扩展
int r = tip;
while (r + 1 <= n && a[r + 1] > a[r]) {
r++;
sum += a[r];
len++;
double avg = (double)sum / len;
if (avg > maxAvg) {
maxAvg = avg;
}
}
// 重置 sum 和 len
sum = a[tip];
len = 1;
// 从 tip 开始,向左扩展
int l = tip;
while (l - 1 >= 1 && a[l - 1] > a[l]) {
l--;
sum += a[l];
len++;
double avg = (double)sum / len;
if (avg > maxAvg) {
maxAvg = avg;
}
}
// 同时向两侧扩展
sum = a[tip];
len = 1;
l = tip;
r = tip;
while (true) {
bool moved = false;
// 尝试向右扩展
if (r + 1 <= n && a[r + 1] > a[r]) {
r++;
sum += a[r];
len++;
double avg = (double)sum / len;
if (avg > maxAvg) {
maxAvg = avg;
}
moved = true;
}
// 尝试向左扩展
if (l - 1 >= 1 && a[l - 1] > a[l]) {
l--;
sum += a[l];
len++;
double avg = (double)sum / len;
if (avg > maxAvg) {
maxAvg = avg;
}
moved = true;
}
if (!moved) {
break;
}
}
// 考虑整个序列
sum = 0;
for (int i = 1; i <= n; i++) {
sum += a[i];
}
double avg = (double)sum / n;
if (avg > maxAvg) {
maxAvg = avg;
}
// 输出结果,保证精度
printf("%.10f\n", maxAvg);
}
int main() {
int t;
scanf("%d", &t);
while (t--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3800kb
input:
2 4 8 2 7 10 6 9 6 5 3 4 8
output:
6.7500000000 5.8333333333
result:
ok 2 numbers
Test #2:
score: -100
Wrong Answer
time: 74ms
memory: 4088kb
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 ...
output:
843938490.0000000000 454252473.5000000000 770302316.6666666269 608562705.0000000000 296293261.6666666865 365718784.0000000000 571816312.6666666269 237830983.0000000000 45613183.0000000000 474479951.5000000000 742247812.0000000000 779975824.3333333731 503399231.5000000000 645879534.5000000000 4327618...
result:
wrong answer 1st numbers differ - expected: '833782882.6666666', found: '843938490.0000000', error = '0.0121802'