QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#442377#8524. Weather Forecastucup-team3282#WA 0ms3840kbC++141.6kb2024-06-15 11:28:402024-06-15 11:28:40

Judging History

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

  • [2024-06-15 11:28:40]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3840kb
  • [2024-06-15 11:28:40]
  • 提交

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) {
//	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){
				flag=true;
				break;
			}
		}
//		cout<<nw<<endl;
		if(!flag)return false;
		for(nw++;nw<=n;nw++){
			if(a[nw]>mid||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;
}

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;
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3840kb

input:

7 3
1 3 1 2 2 2 1

output:

0

result:

wrong answer 1st numbers differ - expected: '1.66667', found: '0.00000', error = '1.66667'