QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#649333#8242. V-DiagramAa#TL 0ms6012kbC++17720b2024-10-17 22:51:492024-10-17 22:51:50

Judging History

你现在查看的是最新测评结果

  • [2024-10-17 22:51:50]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:6012kb
  • [2024-10-17 22:51:49]
  • 提交

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 ...

output:


result: