[数据结构与算法]C语言经典例题：搬家了

题目

来源：牛客网

题目描述

韬神在工作了一段时间后，手头上有了一些积蓄，众所周知，韬神从不谈恋爱，所以韬神用这些钱付了新房子的首付，他现在准备搬家了，现在他有N项物品，大小分别为s1、s2、…、si、…、sN，其中si为满足1≤si≤100的整数，韬神要把这些物品装入到容量为100的一批箱子（序号1-N）中去，韬神有自己独特的装箱方法：对每项物品,
顺序扫描箱子，把该物品放入足以能够容下它的第一个箱子中去，现在请你写一个程序模拟这种装箱过程，并输出每个物品所在的箱子序号，以及放置全部物品所需的箱子数目。

输入描述:

输入第一行给出物品个数N（≤1000）；第二行给出N个正整数si（1≤si≤100，表示第i项物品的大小）。
输出描述:

按照输入顺序输出每个物品的大小及其所在的箱子序号，每个物品占1行，最后一行输出所需的箱子数目。
示例1

输入

8
60 70 80 90 30 40 10 20
输出

60 1
70 2
80 3
90 4
30 1
40 5
10 1
20 2
5

思路

首先是第一个物品放入，箱子数目加一 然后第二个物品放入，由于第一个箱子的容量不够，所以又找来了第二个箱子， 。。。。一直延续下去。

所以我们要定义两个数组和一个变量（记录箱子数目）来存储所需要的信息。

int arr[1000] = { 0 };//物品
int brr[1000] = { 0 };//箱子
int size = 1;//(箱子数目)

初始化：

for (int i = 0; i < 999; i++)
	{
		brr[i] = 100;
	}//初始化箱子的容量

将物品放在箱子里的过程：

int flag = 0;
	for (int i = 0; i < n; i++)
	{
		flag = 0;  //查看是否物品已经放入前面的箱子中了
		for (int j = 1; j <= size; j++)
		{
			if (brr[j] - arr[i] >= 0)  //假如容量足够，就可以将物品放入此箱子了
			{
				brr[j] = brr[j] - arr[i];
				printf("%d %d\n", arr[i], j);
				flag = 1;
				break;
			}
		}
		if (flag == 0)  //当前面的箱子放不下了时
		{
			size++;
			brr[size] = brr[size] - arr[i];
			printf("%d %d\n", arr[i], size);
		}
	}

所以我们就可以根据思路来写出我们所需要的代码了

代码的实现

#include<stdio.h>
#pragma warning(disable:4996)
int main()
{
	int n;
	scanf("%d", &n);
	int arr[1000] = { 0 };
	int brr[1000] = { 0 };
	getchar();
	for (int i = 0; i < 999; i++)
	{
		brr[i] = 100;
	}
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}
	int size = 1;
	int flag = 0;
	for (int i = 0; i < n; i++)
	{
		flag = 0;
		for (int j = 1; j <= size; j++)
		{
			if (brr[j] - arr[i] >= 0)
			{
				brr[j] = brr[j] - arr[i];
				printf("%d %d\n", arr[i], j);
				flag = 1;
				break;
			}
		}
		if (flag == 0)
		{
			size++;
			brr[size] = brr[size] - arr[i];
			printf("%d %d\n", arr[i], size);
		}
	}
	printf("%d", size);
	return 0;
}