QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#345104#8242. V-Diagramoscaryang#TL 1ms5872kbC++201.2kb2024-03-06 08:39:302024-03-06 08:39:32

Judging History

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

  • [2024-03-06 08:39:32]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:5872kb
  • [2024-03-06 08:39:30]
  • 提交

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-8, 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: 5872kb

input:

2
4
8 2 7 10
6
9 6 5 3 4 8

output:

6.750000003385991931281751021743
5.833333337201818125095087452792

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: