QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#442385#8524. Weather Forecastucup-team3282#WA 0ms3860kbC++141.6kb2024-06-15 11:31:532024-06-15 11:31:53

Judging History

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

  • [2024-06-15 11:31:53]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3860kb
  • [2024-06-15 11:31:53]
  • 提交

answer

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

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;
//	cout << check(1.6) << "[[[[]";
	while (l + eps < r) {
		double mid = (l + r) / 2;
		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;
*/

詳細信息

Test #1:

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

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: 0ms
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: 3832kb

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: 3832kb

input:

3 2
2 4 4

output:

3.33333

result:

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