搜索
房产
装修
汽车
婚嫁
健康
理财
旅游
美食
跳蚤
二手房
租房
招聘
二手车
教育
茶座
我要买房
买东西
装修家居
交友
职场
生活
网购
亲子
情感
龙城车友
找美食
谈婚论嫁
美女
兴趣
八卦
宠物
手机

【做题笔记】[NOIOJ,非NOIp原题]装箱问题

[复制链接]
查看: 78|回复: 0

1万

主题

1万

帖子

4万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
45261
发表于 2020-2-14 22:55 | 显示全部楼层 |阅读模式
题意:给定一些矩形,面积别离是 \(1\times 1,2\times 2,3\times 3,4\times 4,5\times 5,6\times 6\)。您现在晓得了这些矩形的个数 \(a,b,c,d,e,f\),必要将这些矩形一个不落的装到一种面积为 \(6\times 6\)的大矩形里面,问怎样使大矩形的数目最少(输入包含多组数据,以全数都是 0 结尾)。
样例输入:
  1. 0 0 4 0 0 17 5 1 0 0 00 0 0 0 0 0
复制代码
样例输出:
  1. 21
复制代码
分组考虑,首先,我们晓得对于 \(6\times 6,5\times 5,4\times 4\)的矩形一个大矩形中只能占一个。如图
【做题笔记】[NOIOJ,非NOIp原题]装箱问题  热点新闻 baDnEQhxBKY6I8g

因而设每次答案为 \(\text{ans}\),则答案最少为 \(\text{ans+d+e+f}\)。
顺着刚刚的思绪,零丁考虑对于 \(3\times 3\)的情况。不难发现,一个大矩形最多可以采取 4 个 \(3\times 3\) 的矩形,换而言之,4 个这样的小矩形占用一个大矩形。考虑到余数,则答案需再加上 \((c+3)/4\)。(补 3 除 4,在本题中这是一个很严重的思绪)。
因而当前答案有:int ans=(d+e+f+(c+3)/4);
接着,考虑面积为 \(2\times 2\) 的矩形的情况。留意到被蓝色和红色地域“并吞”的面积都没法采取 \(2\times 2\)的矩形,那末考虑已经装入 \(4\times 4\) 和 \(3\times 3\) 的。 \(4\times 4\)的比力好想,不言而喻的最多只能填入 5 个。对于 \(3\times 3\) 的矩形,别离考虑装入一个 \(3\times 3\),两个 \(3\times 3\) 和三个 \(3\times 3\) 的情况。思考可以发现对应的答案别离为 \(5,3,1\) 。由于 \(3\times 3\) 的数目不肯定,可以开一个数组记录,即 int mod[4]={0,5,3,1};,然后设变量 \(y\) 为当前答案下最多能装入的 \(2\times 2\) 的数目,把这个值与输入的 \(2\times 2\) 的数目作比力,若比输入的数目少,则说明剩下的此典范的矩形只要零丁放。按照“补 3 除 4”的原则易得还需加上的新矩形为 (b-y+8)/9 个。
末端,考虑 \(1\times 1\) 的矩形。这类矩形很特别,我们分析发现它的一本性质——它不触及填入后留空位的题目。啥意义呢?也就是说,我们采取“见缝插针”的方式,即,有几多空就都填满。可是,假如还像上面那样加加除除的话太麻烦了,因而,考虑以下的算法:
首先考虑,对于当前答案的全数面积,若都填一,则能填几多;然后减去其他占用的面积,末端依照如上的方式比力能否必要新增。
以上,就是本题的贪心计谋。自证不难
[code]#include #include using namespace std;int mod[4]={0,5,3,1};int main(){    int a,b,c,d,e,f;    while(1)    {        cin>>a>>b>>c>>d>>e>>f;        if(!a&&!b&&!c&&!d&&!e&&!f)break;        int ans=(d+e+f+(c+3)/4);        int y=5*d+mod[c%4];        if(b>y)ans+=(b-y+8)/9;        int x=36*ans-(36*f+25*e+16*d+9*c+4*b);        if(a>x)ans+=(a-x+35)/36;        cout

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Copyright © 2006-2014 全椒百姓网-全椒知名**,发布及时新鲜的全椒新闻资讯 生活信息 版权所有 法律顾问:高律师 客服电话:0791-88289918
技术支持:迪恩网络科技公司  Powered by Discuz! X3.2
快速回复 返回顶部 返回列表