问题标题: 酷町堂:4055

0
0
已解决
周明轩
周明轩
资深光能
资深光能

4055   小光头运木材经验值:0

题目描述 Description

伐木工小光头今天在森林里砍树,获得了N段木材,已知这些木头很粗,而且头尾相连。现在有许多载木头用的卡车,卡车的车厢长度不同,宽度跟这些木头的粗细一样,且车厢长度越长使用费用越贵。现在他的老板想租M辆一样的卡车按木材的排列顺序来运这些木材,就问小光头要运完这些木头,花费最少的时候卡车长度是多少。聪明的你知道该怎么帮助小光头回答老板吗?
例如这堆木材长度为4 2 4 5 1,要分成3辆车运输。将其如下分配:[4 2][4 5][1],第一辆车厢需要长度为6,第二辆车厢需要长度为9,第三辆车厢需要长度为1,需要卡车车厢长度最大值为9。将其如下分配:[4][2 4][5 1],第一辆车厢需要长度为4,第二辆车厢需要长度为6,第三辆车厢需要长度为6,需要卡车车厢长度最大值为6。并且无论如何分配,需要卡车车厢长度最大值不会小于6。所以可以得到要将5段木材4 2 4 5 1要分成3辆车运输的话,卡车车厢长度6时最便宜。

输入描述 Input Description

第一行包含两个正整数N,M。
第二行包含N个空格隔开的非负整数Ai,含义如题目所述。

输出描述 Output Description

一个正整数,即每段和最大值最小为多少。

样例输入 Sample Input

5 3 4 2 4 5 1

样例输出 Sample Output

6

数据范围及提示 Data Size & Hint

对于20%的数据,有N≤10;
对于40%的数据,有N≤1000;
对于100%的数据,有N≤100000,M≤N,Ai 之和不超过10^9 。

 

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
long long m,n,a[100005],b[100005];
bool cmp(int x,int y){
	return x>y;
}
bool check(int len){
	for(int i=1;i<=m;i++){
		b[i]=a[i];
	}
	sort(b+1,b+1+n,cmp);
	long long ans=0;
	for(int i=1;i<=(m-n+1);i++){
		ans+=b[i];
	}
	return ans>=len;
}
int main(){
    cin>>m>>n;
    long long sum=0;
    for(int i=1;i<=m;i++){
        cin>>a[i];
        sum+=a[i];
    }
    long long l=1,r=sum,ans=0;
    while(l<r){
        int mid=l+(r-l+1)/2;
        if(check(mid)){
            l=mid;
        } 
        else{
			r=mid-1;
		}
    }
    cout<<l;
    return 0;
}

排错

周明轩在2020-12-05 11:40:14追加了内容

111

周明轩在2020-12-05 11:40:47追加了内容

111

周明轩在2020-12-100 11:40:14追加了内容

111


0
0
0
我要回答