【求助】求助一道站外题
  • 板块学术版
  • 楼主达·芬奇
  • 当前回复10
  • 已保存回复10
  • 发布时间2022/3/6 14:20
  • 上次更新2023/10/28 07:09:10
查看原帖
【求助】求助一道站外题
550462
达·芬奇楼主2022/3/6 14:20

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;
} 
2022/3/6 14:20
加载中...