QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#649333 | #8242. V-Diagram | Aa# | TL | 0ms | 6012kb | C++17 | 720b | 2024-10-17 22:51:49 | 2024-10-17 22:51:50 |
Judging History
answer
#include <iostream>
#include <algorithm>
using namespace std;
const double INF=1e18;
int n;
int a[300010];
double s[300010];
bool check(double mid){
for(int i=1;i<=n;i++)
s[i]=s[i-1]+(double)a[i]-mid;
double mi=INF;
for(int i=2;i<=n;i++){
if(a[i]==a[i-1]){
mi=INF;
continue;
}
else if(a[i]<a[i-1]) mi=min(mi,s[i-2]);
else if(s[i]-mi>=0) return true;
}
return false;
}
signed main(){
int t;
scanf("%d",&t);
while(t--){
double l=0,r=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
r=max(r,(double)a[i]);
}
while(r-l>1e-9){
double mid=(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
printf("%.20lf\n",l);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 6012kb
input:
2 4 8 2 7 10 6 9 6 5 3 4 8
output:
6.74999999988358467817 5.83333333331393077970
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 ...