QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#442387#8524. Weather Forecastucup-team3282#WA 1ms3960kbC++141.4kb2024-06-15 11:33:372024-06-15 11:33:38

Judging History

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

  • [2024-06-15 11:33:38]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3960kb
  • [2024-06-15 11:33:37]
  • 提交

answer

#include <bits/stdc++.h>
#define eps 1e-9
using namespace std;
const int N = 2e5+9;
int n, k; 
double a[N];
bool check(double mid) {
	int nw=1,cnt=0;
	while(cnt<k-1){
		double sum=0,num=0;
		bool flag=false;
		for(;nw<=n;nw++){
			sum+=a[nw];num++;
			if(sum>=mid*num){
				flag=true;
				break;
			}
		}
		if(!flag)return false;
		for(nw++;nw<=n;nw++){
			if(a[nw]>=mid||sum+a[nw]<mid*(num+1))break;
			sum+=a[nw];num++;
		}
		cnt++;
	}
	double sum=0,num=0;
	for(;nw<=n;nw++){
		sum+=a[nw];num++;
	}
	return sum>=num*mid;
}

int main() {
//	freopen("2.in", "r", stdin);
	cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> a[i];
	double l = 0.0, r = 1e9, ans = 0.0;
	while (l + eps < r) {
		double mid = (l + r) / 2.0;
		if (check(mid)) {
			ans = mid;
			l = mid;	
		} else r = mid;
	}
	
	cout << ans;
	return 0;	
}
/*
//	cout << mid << "----------------" <<endl;
	double cur = 0; int l = 1; double sum = 0;int cc = 0, ans = 0;
	while (l <= n && ans < k-1) {
		cur = 0;sum = 0;
		while (cur < mid && l <= n) {
			sum += a[l];
			l++; cc++;
			cur = (double) (sum / cc);
		}
		
		if (l > n) break;
	
		while (cur > mid && a[l] < mid && l<=n) {
			sum += a[l];
			l++; cc++;
			cur = double (sum / cc);
		}
		cc = 0;
		ans++;
//		cout<<l-1<<endl;}
	if(l>n)return false;
	if (cur < mid) return false;
		cur = 0;sum = 0;
	for(;l<=n;l++){
		cc++,sum+=a[l];
	}
	return sum/cc>=mid;
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3960kb

input:

7 3
1 3 1 2 2 2 1

output:

1.66667

result:

ok found '1.66667', expected '1.66667', error '0.00000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3852kb

input:

1 1
1

output:

1

result:

ok found '1.00000', expected '1.00000', error '0.00000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

2 1
2 1

output:

1.5

result:

ok found '1.50000', expected '1.50000', error '0.00000'

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3800kb

input:

3 2
2 4 4

output:

3.33333

result:

wrong answer 1st numbers differ - expected: '3.00000', found: '3.33333', error = '0.33333'