您当前位置：首页 > php开源 > 综合技术 > 2-09. 装箱问题模拟（20） (ZJUPAT 模拟)

2-09. 装箱问题模拟（20） (ZJUPAT 模拟)

来源：程序员人生发布时间：2014-10-04 08:00:01 阅读次数：2318次

题目链接：http://pat.zju.edu.cn/contests/ds/2-09

假设有N项物品，大小分别为s₁, s₂, …, s_i, …, s_N，其中s_i为满足1<= s_i<=100的整数。要把这些物品装入到容量为100的一批箱子（序号1～N）中。装箱方法是：对每项物品, 顺序扫描箱子，把该物品放入足以能够容下它的第一个箱子中。请写一个程序模拟这种装箱过程，并输出每个物品所在的箱子序号，以及放置全部物品所需的箱子数目。

输入格式说明：

输入第1行给出物品个数N(<=1000)，第2行给出N个正整数s_i（1 <= s_i <= 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
2	6 100 90 80 70 60 50	100 1 90 2 80 3 70 4 60 5 50 6 6
3	1 2	2 1 1

代码如下：

#include <cstdio> #include <cstring> const int maxn = 1017; int a[maxn], b[maxn], c[maxn]; void init() { for(int i = 0; i < maxn; i++) b[i] = 100; } void solve(int n) { int maxx = 0; for(int i = 1; i <= n; i++) { for(int j = 1; ; j++) { if(b[j]>=a[i]) { b[j] -= a[i]; if(maxx < j) maxx = j; c[i] = j; break; } } } for(int i = 1; i <= n; i++) { printf("%d %d ",a[i],c[i]); } printf("%d ",maxx); } int main() { int n; while(~scanf("%d",&n)) { init(); for(int i = 1; i <= n; i++) { scanf("%d",&a[i]); } solve(n); } return 0; }

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 颜色(color)转换为三色值(r/g/b)（干货分享）

下一篇 UI设计

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点