rt,调了2个小时,60pts,求助各位大佬错哪里了
2、发送快递
问题描述
小华有n 本不同的书(编号为1,2,3,.....,n),重量分别是a1、
a2、……、an 公斤(重量可以相同)。他想把这些书以快递的方式发给自己
的好朋友,要求每个包裹的重量不能超过m 公斤(可以等于m 公斤),并且
小华想把其中一些书(一组书,用书的编号给出来)放在一个包裹里,应该
如何打包才能使得快递件数最少。
【输入】
输入文件名为express.in
第一行,包含两个整数n、m,之间用一个空格隔开,分别表示书的数量
和快递包裹的最大重量。
第二行n 个整数ai,表示n 本书的重量,每两个整数之间用一个空格隔
开。
第三行一个整数s,表示一共有s 组书(每组书需要打包在一起)。如
果s=0,则无此限制。数据保证每组书的重量不超过m。
第四行开始共s 行,每行若干个整数,表示必须放在一个包裹里的书的
编号,每两个整数之间用一个空格隔开。
【输出】
输出文件一行,一个整数,即快递最少件数。
【输入输出样例1】
5 10
8 4 8 2 5
0
3
【输入输出样例1 说明】
第1 本和第4 本打包,重量是10 公斤。第2 本和第5 本打包,重量是9
公斤。第3 本单独打包,重量是8 公斤。所以一共3 件快递。
【输入输出样例2】
10 80
49 11 44 18 28 24 19 10 27 29
2
1 5
4 8 2
4
【输入输出样例2 说明】
第1 本和第5 本打包,第2 本、第4 本、第8 本和第10 本打包,第3
本和第7 本打包,第6 本和第9 本打包。所以一共4 件快递。
【数据范围和限制】
对于40%的数据,1 ≤ n ≤ 105,1 ≤ ai ≤ 100,s=0,m 的值保证有解。
对于100%的数据,1 ≤ n ≤ 105,1 ≤ ai ≤ 100,0 ≤ s ≤ 100,m
的值保证有解。
我的代码:
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int a[100005]={0};
int b[100005]={0};
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
int s;
cin>>s;
int sum=0;
for(int i=1;i<=s;i++)
{
int k;
while(cin>>k)
{
a[k]=0;
b[k]=1;
}
sum++;
}
sort(a+1,a+n+1);
for(int i=n;i>=1;i--)
{
if(b[i]==1)
continue;
if(b[i]==0)
{
int sum1=a[i];
a[i]=0;
for(int j=i-1;j>=1;j--)
{
int sum2=sum1+a[j];
if(sum2<=m)
{
a[j]=0;
b[j]=1;
sum1=sum2;
}
}
b[i]=1;
sum++;
}
}
cout<<sum;
return 0;
}