2056装果子TLE0help

问题讨论区 普及段
1

. 装果子

题目ID：2056必做题100分

最新提交：

Time Limit Exceeded

0 分

历史最高：

Time Limit Exceeded

0 分

时间限制: 1000ms

空间限制: 131072kB

题目描述

时间限制: 1s 空间限制: 128M

题目描述:

果园里有n颗果树，每棵果树都有一个编号i(1≤i≤n)。小明已经把每棵果树上的果子都摘下来堆在了这棵树的下方，每棵树下方的果子体积为ai。

现在小明将拿来m个袋子把这些果子都装进袋子里。每个袋子的体积为v。小明会按照如下规则把果子装进袋子里：

(a)从第1棵果树开始装起，由1到n一直装到第n棵果树。

(b)如果这棵果树下的果子能全部装进当前这个袋子，就装进去；如果不能，就关上当前这个袋子，打开一个新的袋子开始装。

小明希望在能把所有果子都装进袋子里的前提下，v尽量小。m个袋子并不一定都要装进果子。

输入格式：

输入第1行，包含两个整数n和m。

第2行，包含n个整数ai。

输出格式：

输出仅1行，表示最小的v。

样例输入1:

3 3
1 2 3

样例输出1:

3

样例输入2:

5 3
1 3 6 1 7

样例输出2:

7

样例输入3:

6 3
1 2 1 3 1 4

样例输出3:

4

数据范围：

对于40%的数据 1≤ai≤1000

对于70%的数据 1000≤ai≤100000

对于100%的数据小于 1≤n≤100000，1≤m≤1000，100000≤ai≤1000000000
TLE0,大佬HELP

#include<bits/stdc++.h>
using namespace std;
long long a[100005],n,x,sum,m; 
bool check(int v)
{
	long long  cnt=0,sum=0;

	for(int i=1;i<=n;i++)
	{
		if(a[i]<v){
			v-=a[i];
		}else{
          sum++;
          v=v-a[i];
        }
      if(sum>m){
        return 0;
      }
		
	}
	return 1;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
      sum+=a[i];
      x=max(a[i],x);
	}
	long long l=x,r=sum;
	while(l<=r)
	{
		long long mid=(l+r)>>1;
		if(check(mid))
		{
			r=mid-1;
		}
		else
		{
			l=mid;
		}
	}
	cout<<l;
	return 0;
}
1 个赞
2

1.l=mid+1;
2.在函数中定义一个值，赋值为“v” 在else中改成：定义的值=v-a[i];

可以试试

3

v>=a[i]
sum的的初始值为1

1 个赞
4

WA65


#include<bits/stdc++.h>
using namespace std;
long long a[100005],n,x,sum,m; 
bool check(int v)
{
	long long  cnt=v,sum=1;

	for(int i=1;i<=n;i++)
	{
		if(cnt>=a[i]){
			cnt-=a[i];
		}else{
          sum++;
          cnt=v-a[i];
        }
      if(sum>m){
        return 0;
      }
		
	}
	return 1;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
      sum+=a[i];
      x=max(a[i],x);
	}
	long long l=x,r=sum;
	while(l<=r)
	{
		long long mid=(l+r)>>1;
		if(check(mid))
		{
			r=mid-1;
		}
		else
		{
			l=mid+1;
		}
	}
	cout<<l;
	return 0;
}
5

还65
#include<bits/stdc++.h>
using namespace std;
long long a[100005],n,x,sum,m;
bool check(int v)
{
long long cnt=v,s=1;

for(int i=1;i<=n;i++)
{
	if(cnt>=a[i]){
		cnt-=a[i];
	}else{
      s++;
      cnt=v-a[i];
    }
  if(s>m){
    return 0;
  }
	
}
return 1;

}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
sum+=a[i];
x=max(a[i],x);
}
long long l=x,r=sum;
while(l<=r)
{
long long mid=(l+r)>>1;
if(check(mid))
{
r=mid-1;
}
else
{
l=mid+1;
}
}
cout<<l;
return 0;
}