企业官网建设流程全解析

厦门国外网站建设公司,搜索微信公众号平台,名城苏州,电商网站设计教程题目描述 一家公司生产统一直径的管道#xff0c;这些管道需要存储在矩形容器中。容器有不同尺寸#xff0c;管道在容器内按行排列#xff0c;同一行内管道紧贴#xff08;相切#xff09;#xff0c;行与行之间也紧贴#xff08;或紧贴容器底部#xff09;。 有两种排…题目描述一家公司生产统一直径的管道这些管道需要存储在矩形容器中。容器有不同尺寸管道在容器内按行排列同一行内管道紧贴相切行与行之间也紧贴或紧贴容器底部。有两种排列方式网格grid\texttt{grid}grid和交错skew\texttt{skew}skew如下图所示题目中给出示意图网格排列管道按行列对齐排列。交错排列管道在行与行之间交错排列使得相邻行的管道位于间隙中。输入为一系列矩形容器横截面的尺寸单位是管道直径每个尺寸由两个实数表示。输出对于每个横截面能够容纳的最大管道数以及达到该最大数时所采用的排列模式grid\texttt{grid}grid或skew\texttt{skew}skew。如果两种模式结果相同则输出grid。题目分析与解题思路1. 网格排列grid\texttt{grid}grid在网格排列中管道整齐地排成行和列。假设容器宽度为widthwidthwidth高度为heightheightheight那么能容纳的管道数为grid⌊width⌋×⌊height⌋ grid \lfloor width \rfloor \times \lfloor height \rfloorgrid⌊width⌋×⌊height⌋这里使用向下取整是因为管道是整数个不能有部分管道。2. 交错排列skew\texttt{skew}skew交错排列较为复杂需要仔细计算行数和每行的管道数。行数计算在交错排列中相邻两行的垂直距离为32\frac{\sqrt{3}}{2}23​​因为管道直径为单位长度三个管道中心构成等边三角形高为32\frac{\sqrt{3}}{2}23​​。若第一行紧贴底部那么第iii行的垂直位置为(i−1)×32(i-1) \times \frac{\sqrt{3}}{2}(i−1)×23​​。要求最后一行不能超出容器高度即(layers−1)×321≤height(layers - 1) \times \frac{\sqrt{3}}{2} 1 \le height(layers−1)×23​​1≤height。解得最多行数layers⌊2(height−1)3⌋1 layers \left\lfloor \frac{2(height - 1)}{\sqrt{3}} \right\rfloor 1layers⌊3​2(height−1)​⌋1注意若height1height 1height1则无法放置任何管道。每行管道数奇数行从第一行开始计数管道数为⌊width⌋\lfloor width \rfloor⌊width⌋。偶数行管道数通常为⌊width⌋−1\lfloor width \rfloor - 1⌊width⌋−1但若width−⌊width⌋≥0.5width - \lfloor width \rfloor \ge 0.5width−⌊width⌋≥0.5则偶数行也可以放下与奇数行相同数量的管道。这是因为交错排列中偶数行管道会向左偏移0.50.50.5个单位若剩余空间足够则可多放一个。总管道数设奇数行有oddRows⌈layers/2⌉oddRows \lceil layers / 2 \rceiloddRows⌈layers/2⌉偶数行有evenRows⌊layers/2⌋evenRows \lfloor layers / 2 \rfloorevenRows⌊layers/2⌋则总数为skewoddRows×pipesPerOddRowevenRows×pipesPerEvenRow skew oddRows \times pipesPerOddRow evenRows \times pipesPerEvenRowskewoddRows×pipesPerOddRowevenRows×pipesPerEvenRow注意由于容器可以旋转因此需要计算skew(width,height)skew(width, height)skew(width,height)和skew(height,width)skew(height, width)skew(height,width)并取最大值。3. 比较与输出比较网格排列和交错排列的最大管道数输出较大者及其模式若相等则输出grid。代码实现// Pipe Fitters// UVa ID: 121// Verdict: Accepted// Submission Date: 2011-12-18// UVa Run Time: 0.056s//// 版权所有C2011邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intgrid(doublewidth,doubleheight){intnGrid0;nGridfloor(width)*floor(height);returnnGrid;}intskew(doublewidth,doubleheight){if(height1.0)return0;intlayersfloor(2.0*(height-1.0)/sqrt(3.0)1.0);intpipes_per_odd_full_rowfloor(width);intpipes_per_even_full_rowpipes_per_odd_full_row-1;if((width-pipes_per_odd_full_row)0.5)pipes_per_even_full_rowpipes_per_odd_full_row;intnSkewceil(layers/2.0)*pipes_per_odd_full_rowfloor(layers/2.0)*pipes_per_even_full_row;returnnSkew;}intmain(intac,char*av[]){doublea,b;while(cinab){intnGridgrid(a,b);intnSkewmax(skew(a,b),skew(b,a));if(nGridnSkew)coutnGrid gridendl;elsecoutnSkew skewendl;}return0;}复杂度分析对于每个输入尺寸计算grid\texttt{grid}grid和skew\texttt{skew}skew均为常数时间操作因此总时间复杂度为O(1)O(1)O(1)每个测试用例整体为O(n)O(n)O(n)其中nnn为测试用例数。空间复杂度为O(1)O(1)O(1)。总结本题主要考察几何建模和取整运算。关键在于理解交错排列的行距与每行管道数的计算并正确处理浮点数比较与取整。通过分别计算两种排列方式的管道数并比较即可得到答案。