肖宇睿
(人畜无害的小学生)
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];
可以试试
肖宇睿
(人畜无害的小学生)
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;
}