QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#442393#8524. Weather Forecastucup-team3282#TL 0ms0kbC++14864b2024-06-15 11:36:092024-06-15 11:36:09

Judging History

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

  • [2024-06-15 11:36:09]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-06-15 11:36:09]
  • 提交

answer

#include <bits/stdc++.h>
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++;
	}
	if(nw>n)return false;
	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 < r) {
		double mid = (l + r) / 2.0;
		if (check(mid)) {
			ans = mid;
			l = mid;	
		} else r = mid;
	}
	
	cout << ans;
	return 0;	
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

7 3
1 3 1 2 2 2 1

output:


result: