QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#442385 | #8524. Weather Forecast | ucup-team3282# | WA | 0ms | 3860kb | C++14 | 1.6kb | 2024-06-15 11:31:53 | 2024-06-15 11:31:53 |
Judging History
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'