《数据分组》
题目描述 Description
给定一个正整数数组,长度为N,不打乱其顺序将其分为连续的若干组,每组之和小于等于S,问最少分多少组。
输入描述 Input Description
输入两行,第一行为N与S,用一个空格隔开。第二行为N个正整数。
【数据范围】
对于50%的数据,有N≤1000;
对于100%的数据,有N≤10000,S≤10^9,N个数都不大于S。
输出描述 Output Description
输出最少的划分数。
样例输入 Sample Input
5 6
1 2 4 2 1
样例输出 Sample Output
3
#include<iostream>
#include<algorithm>
using namespace std;
int n,w,cnt;
int a[10005];
int main(){
cin>>w>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+1+n);
int l=1,r=n;
while(l<=r){
if(a[r]+a[l]<=w){
cnt++;
l++;
r--;
}
else{
cnt++;
r--;
}
}
cout<<cnt;
return 0;
}
样例过了,但是完美WA0了。。。 请找错!谢谢!