QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#449439#7944. Max Minus MinmitpressWA 22ms3612kbC++141.7kb2024-06-21 10:19:242024-06-21 10:19:24

Judging History

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

  • [2024-06-21 10:19:24]
  • 评测
  • 测评结果:WA
  • 用时:22ms
  • 内存:3612kb
  • [2024-06-21 10:19:24]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int T, n, a[200010], b[200010], mix, mij, mx, 	mj;
bool check1(int x){
	int l = 1, r = n;
	for(int i = mij;i >= 1;i--){
		if(a[i] + x > mx){
			l = i + 1;
			break; 
		}
	}
	for(int i = mij;i <= n;i++){
		if(a[i] + x > mx){
			r = i - 1;
			break;	
		}
	}
	//cout<<x<<" "<<r<<" "<<l<<endl;
	if(r < l)return 0;
	int minx = 1e9;
	for(int i = 1;i <= l - 1;i++){
		minx = min(minx, a[i]);
	}
	for(int i = r + 1;i <= n;i++){
		minx = min(minx, a[i]);
	}
	if(mix + x > minx)return 0;
	return 1;
}
bool check2(int x){
	int l = 1,r = n;
	for(int i = mj;i >= 1;i--){
		if(a[i] - x < mix){
			l = i + 1;
			break; 
		}
	}
	for(int i = mj;i <= n;i++){
		if(a[i] - x < mix){
			r = i - 1;	
			break;
		}
	}
		
		//cout<<x<<" "<<r<<" "<<l<<endl;
	if(r < l)return 0;
	int mjx = 0;
	for(int i = 1;i <= l-1;i++){
		mjx = max(mjx, a[i]);
	}
	for(int i = r+1;i <= n;i++){
		mjx = max(mjx, a[i]);
	}
	if(mx - x < mjx)return 0;
	return 1;
}
int main(){
	cin >> T;
	while(T--){
		cin >> n;
		if(n == 1) cout << 0 << endl; 
		mix = 999999999, mx = -1, mij = 0,mj = 0;
		for(int i = 1;i <= n;i++){
			cin >> a[i];
			if(a[i] < mix) {
				mix = a[i];
				mij = i;
			}
			if(a[i] > mx) {
				mx = a[i];
				mj = i;
			}
		}
		int l1 = 0, r1 = mx - mix;
		while(l1 <= r1){
			int mid = (l1 + r1) >> 1;
			if(check1(mid)) l1 = mid + 1;
			else{
				r1 = mid - 1;
			}
		}
		int l2 = 0,r2 = mx - mix;
		while(l2 <= r2){
			int mid = (l2 + r2) >> 1;
			if(check2(mid))l2 = mid + 1;
			else{
				r2 = mid - 1;
			}
		}
	//	cout<<r1<<" "<<r2<<" hj "<<endl;
		cout<<mx - mix - max(r1, r2)<<endl;
		for(int i = 1;i <= n;i++){
			a[i] = 0;
		}
	}
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3596kb

input:

4
3
42 42 42
4
1 2 2 1
5
1 100 1 100 1
6
1 2 3 4 5 6

output:

0
0
99
2

result:

ok 4 number(s): "0 0 99 2"

Test #2:

score: -100
Wrong Answer
time: 22ms
memory: 3612kb

input:

19530
6
2 3 3 3 4 3
6
2 4 4 2 5 5
6
2 5 2 5 1 3
6
4 4 1 2 4 1
5
5 4 5 3 3
5
2 2 1 5 1
6
3 1 2 4 2 3
5
5 5 4 4 5
6
5 3 3 1 4 2
6
3 3 2 4 2 4
6
1 2 4 5 2 5
5
3 4 5 5 3
6
4 3 3 3 4 3
6
1 5 1 2 3 1
5
5 5 2 1 4
6
1 2 5 3 5 2
6
4 5 2 4 5 2
5
2 4 2 4 1
4
2 3 3 3
6
1 2 2 1 4 5
6
3 2 1 3 3 2
6
2 1 1 2 5 3
6
...

output:

1
2
3
3
1
1
2
0
3
2
3
1
1
2
1
2
3
2
0
1
1
2
0
3
2
2
3
2
2
2
3
3
2
2
1
2
2
2
2
2
2
1
2
1
2
1
2
2
2
1
1
2
2
1
2
2
1
1
1
2
1
2
2
1
2
2
3
2
2
1
1
2
1
2
3
2
0
2
1
1
2
1
1
2
2
2
1
3
2
1
2
3
2
1
1
2
2
3
1
1
1
2
2
1
1
1
1
2
2
2
2
2
3
2
1
2
0
1
1
1
1
1
1
2
2
2
2
2
2
1
2
1
2
4
1
1
1
3
2
2
2
1
2
1
2
1
2
2
1
3
...

result:

wrong answer 3910th numbers differ - expected: '1', found: '0'