基础maoge的农场WA50分

常规
1 
#include<iostream>
using namespace std;
int n,m;
long long a[100005];
bool check(int x){
	long long t=0,sum=0;
	for(int i=1;i<=n;i++){
		t+=a[i];
		if(t>=x){
			t=a[i];
			sum++;
		}
	}
	return sum<=m;
}
int main(){
	cin>>n>>m;
	long long l=0,r=0;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		l=max(l,a[i]); 
		r+=a[i];
	}	
	while(l<r){
		long long mid=(l+r+1)/2;
		if(check(mid)){
			r=mid-1;
		}
		else{
			l=mid+1;
		}
	}
	cout<<l;
	return 0;
}
1 个赞
2

where is 题面?

1 个赞
3

9. maoge的农场

XJOI - 题目ID：9334选做题100分

最新提交：

Wrong Answer

0 分

历史最高：

Wrong Answer

50 分

时间限制: 200ms

空间限制: 65535kB

题目描述

题目描述
maoge是一个农场主。运营农场需要精打细算。他计算出并记录下了接下来 N ( 1 ≤ N ≤ 100 , 000 ) 天里每天需要的开销。

maoge打算为连续的 M ( 1 ≤ M ≤ N )个财政周期创建预算案，每个财政周期包含一天或连续的多天，每天被恰好包含在财政周期中。

请你帮忙设计程序，使得开销最多的财政周期的开销尽可能少。

输入
第一行包含两个整数 N , M 用单个空格隔开。
接下来 N 行，每行包含一个 1 到 10000之间的整数，按顺序给出接下来 N 天里每天的开销。

输出
一个整数，即最大开销的最小值。

输入样例

7 5

100

400

300

100

500

101

400

输出样例

500

提示
若将前两天作为一个周期，第三、四两天作为一个周期，最后三天每天各作为一个周期，则最大月度开销为 500。其他任何分配方案都会比这个值更大。

C++14

评测规则

加载最近代码

1

最新编译结果

提交代码

1 个赞