牛客 Wall Builder II 题解

思路

外部预处理

首先，知道n之后我们可以求出所有矩形的面积之和S，在面积相同的情况下矩形的长宽差距越小，周长越小

因为n最大就100，所以我们就对每一个n暴力求解出周长最短情况的长与宽：S=a*b下令a+b最小

求得的结果存到pair<int,int>数组中，解题代码中n输入几就用第几个就好了

在知道长宽之后确定每个砖的位置就很好处理了，因为一定能放完，令长宽的较小值作为墙的高度，一层层的放就行了

每种长度的砖有多少块用一个数组存着

先从最长的砖开始放，然后遍历寻找还能放到当层的砖，每层遍历时设定一个now变量作为横坐标指针，因为高度都为1是固定的就不格外增加变量了

AC代码

#include<bits/stdc++.h>
using namespace std;#define int long long//外部预处理出的1-100的n对应的墙的长宽值
pair<int,int> hv[101]={{0,0},{1,1},{2,2},{2,5},{4,5},{5,7},{7,8},{7,12},{10,12},{11,15},
{11,20},{13,22},{14,26},{13,35},{20,28},{20,34},{24,34},{19,51},{30,38},{35,38},{35,44},
{23,77},{44,46},{46,50},{50,52},{45,65},{52,63},{58,63},{58,70},{31,145},{62,80},{62,88},
{68,88},{77,85},{84,85},{74,105},{76,111},{37,247},{95,104},{82,130},{82,140},{43,287},
{86,154},{110,129},{115,132},{115,141},{94,184},{98,188},{140,140},{119,175},{130,170},
{106,221},{156,159},{159,165},{165,168},{154,190},{152,203},{59,551},{145,236},{122,295},
{155,244},{183,217},{192,217},{208,210},{208,220},{143,335},{187,268},{134,391},{230,238},
{161,355},{213,280},{219,284},{222,292},{185,365},{190,370},{266,275},{266,286},{143,553},
{260,316},{270,316},{270,328},{249,369},{287,332},{238,415},{301,340},{215,493},{319,344},
{319,356},{330,356},{273,445},{345,364},{322,403},{188,713},{235,589},{376,380},{380,388},
{388,392},{291,539},{385,420},{330,505},{404,425}};int n;
int kuan,gao,nd,now;
int chai[101]; //存每个长度的砖有多少块void solve(){cin>>n;for(int i=1;i<=n;++i){chai[i]=n+1-i;}cout<<(hv[n].first+hv[n].second)*2<<'\n';kuan=hv[n].second; gao=hv[n].first;for(int i=0;i<gao;++i){nd=kuan; now=0;for(int j=n;j>0 && nd;){ //倒着找从最长的砖开始if(nd>=j && chai[j]){cout<<now<<' '<<i<<' '<<now+j<<' '<<i+1<<'\n';nd-=j;now=now+j;--chai[j];}else --j; //不符合当前情况就找长度更短的}}}signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int _=1;cin>>_;while(_--){solve();}    return 0;
}