商务合作:179001057@qq.com

装木块问题

技术2022-05-11  3


某平台价值19860元的编程课程资料免费领取【点我领取】


Description

有一种很特别装箱子,箱子的所有长度都是L,还有N根木块,所有木块的长度都小于等于L,箱子可以装木块,但是有如下限制: 1.每个箱子只能装一根或两根木块。 2.如果装两根必须使得这两根木块的长度之和小于等于箱子的长度L。 你的任务是求出最少需要多少个这样的箱子才能装下所有的木块。

Input

第一行一个N,表示有N根木块。(1<=N<=105) 第二行一个L,表示箱子的长度。L<=10000 接下来N行,每行一个正整数,表示木块的长度。

Output

只有一行,最少需要的箱子数。

Sample Input

10 80 70 15 30 35 10 80 20 35 10 30

Sample Output

6 KEY:不是什么难题……但是wa好几次……居然是数组开小了……丢人啊…… #include<iostream> #include<algorithm> using namespace std; int a[100001]; int N; int L; int MAX; void input() { for(int i=1;i<=N;i++) cin>>a[i]; } void countmax() { MAX=0; int i=1,j=N; while(i<=j) { if(i==j) { MAX++; return ; } if(a[j]+a[i]<=L) { MAX++; j--; i++; } else { if(a[j]<=L) { MAX++; j--; } } } } int main() { // freopen("fjnu_1992.in","r",stdin); while(cin>>N) { cin>>L; input(); sort(a+1,a+N+1); countmax(); cout<<MAX<<endl; } }

最新回复(0)