编一道很难的c++一维数组题,并有6个输入输出样例,与正确代码
时间: 2023-08-08 19:04:17 浏览: 66
题目描述:
给定一个长度为 n 的一维数组,将这个数组分成 k 个连续的子数组,使得每个子数组的和最大值最小。
输入格式:
第一行包含两个整数 n 和 k。
第二行包含 n 个整数,表示数组中的元素。
输出格式:
输出一个整数,表示每个子数组的和最大值最小值,保留两位小数。
输入样例1:
5 3
2 4 5 3 1
输出样例1:
4.33
输入样例2:
6 4
1 2 3 4 5 100
输出样例2:
100.00
输入样例3:
5 1
1 2 3 4 5
输出样例3:
15.00
输入样例4:
10 5
1 2 3 4 5 6 7 8 9 10
输出样例4:
10.00
输入样例5:
10 1
1 2 3 4 5 6 7 8 9 10
输出样例5:
55.00
输入样例6:
5 5
2 4 5 3 1
输出样例6:
5.00
正确代码:
```c++
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, k;
double a[N];
bool check(double mid) {
int cnt = 0;
double sum = 0;
for (int i = 1; i <= n; i ++ ) {
if (sum + a[i] > mid) {
cnt ++;
sum = a[i];
}
else sum += a[i];
}
return cnt + 1 <= k;
}
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
double l = 0, r = 1e9 + 10;
while (r - l > 0.0001) {
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
printf("%.2f\n", r);
return 0;
}
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)