华为机试100分值Java版-2024最新

<link rel="stylesheet" href="./index.css"> <div class="blog-content-box"> <div class="article-header-box"> <div class="article-header"> <div class="article-title-box"> <h1 class="title-article" id="articleContentId">华为OD机试 - 总最快检测效率（Java &amp; JS &amp; Python）</h1> </div> </div> </div> <article class="baidu_pl"> <div id="article_content" class="article_content clearfix"> <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css"> <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-25cebea3f9.css"> <div id="content_views" class="htmledit_views"> <h2 id="main-toc"><a name="t0"></a>题目描述</h2> <p>在系统、网络均正常的情况下组织核酸采样员和志愿者对人群进行<a href="https://so.csdn.net/so/search?q=%E6%A0%B8%E9%85%B8%E6%A3%80%E6%B5%8B&amp;spm=1001.2101.3001.7020" target="_blank" class="hl hl-1" data-report-click="{&quot;spm&quot;:&quot;1001.2101.3001.7020&quot;,&quot;dest&quot;:&quot;https://so.csdn.net/so/search?q=%E6%A0%B8%E9%85%B8%E6%A3%80%E6%B5%8B&amp;spm=1001.2101.3001.7020&quot;,&quot;extra&quot;:&quot;{\&quot;searchword\&quot;:\&quot;核酸检测\&quot;}&quot;}" data-tit="核酸检测" data-pretit="核酸检测">核酸检测</a>筛查。</p> <p>每名采样员的效率不同，采样效率为N人/小时。</p> <p>由于外界变化，采样员的效率会以M人/小时为粒度发生变化，M为采样效率浮动粒度，M=N*10%，输入保证N*10%的结果为整数。</p> <p>采样员效率浮动规则：采样员需要一名志愿者协助组织才能发挥正常效率，在此基础上，每增加一名志愿者，效率提升1M，最多提升3M；如果没有志愿者协助组织，效率下降2M。</p> <p>怎么安排速度最快？求<strong>总最快检测效率</strong>（总检查效率为各采样人员效率值相加）。</p> <p></p> <h2 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0"><a name="t1"></a>输入描述</h2> <p>第一行：第一个值，采样员人数，取值范围[1, 100]；第二个值，志愿者人数，取值范围[1, 500]；<br> 第二行：各采样员基准效率值（单位人/小时），取值范围[60, 600]，保证序列中每项值计算10%为整数。</p> <p></p> <h2 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0"><a name="t2"></a>输出描述</h2> <p>第一行：总最快检测效率（单位人/小时）</p> <p></p> <h2 id="%E7%94%A8%E4%BE%8B"><a name="t3"></a>用例</h2> <div class="table-box"> <table border="1" cellpadding="1" cellspacing="1" style="width:500px;"> <tbody> <tr> <td style="width:86px;">输入</td> <td style="width:412px;">2 2<br> 200 200</td> </tr> <tr> <td style="width:86px;">输出</td> <td style="width:412px;">400</td> </tr> <tr> <td style="width:86px;">说明</td> <td style="width:412px;">输入需要保证采样员基准效率值序列的每个值*10%为整数。</td> </tr> </tbody> </table> </div> <p></p> <h2 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90"><a name="t4"></a>题目解析</h2> <p>用例意思是：</p> <p>有两个采样员，两个志愿者。</p> <p>两个采样员的正常效率都是200，但是要给每个采样员配一个志愿者才能发挥正常效率。</p> <p>现在刚好采样员和志愿者是一比一，因此可以发挥出总效率是：200 + 200 = 400。</p> <p></p> <p>如果，我们给一个采样员配两个志愿者，那么该采样员发挥的效率是：200 + 200 * 10% = 220。</p> <p>但是另一名采样员就没有志愿者了，因此发挥不了正常效率，200 - 200 * 20% = 160，此时总效率是220 + 160 = 380。</p> <p>因此，总最快效率是400。</p> <p></p> <p>需要注意的是，用例中采样员的正常效率只是凑巧相同，很有可能出现一个采样员的正常效率极高，一个采样员的正常效率极低的情况。</p> <p></p> <p>我的解题思路如下：</p> <p>首先分两种情况：</p> <p>1、志愿者数量少于采样员</p> <p>2、志愿者数量不少于采样员</p> <p></p> <p>对于情况1，我们应该将不多的志愿者优先分配给高效率的采样员，默认一比一分配。</p> <p>接下来，我们应该考虑，剥夺低效率的采样员的志愿者&nbsp; 给 高效率的采样员，只要 高效率采样员增加的10%的效率&nbsp; &nbsp;可以大于&nbsp; 低效率采样员减少的20%的效率。</p> <p>其中还要考虑，高效率的采样员最多可以追加3个志愿者，即最多增加30%的效率。如果最高效率的采样员已经提升30%效率，则第二高效率的采样员称为最高优先级，继续上面剥夺逻辑。</p> <p></p> <p>对于情况2，我们应该先按一比一的方式，给每个采样员分配一个志愿者。</p> <p>然后，如果还多出志愿者的话，则优先分配给高效率的采样员，同样需要注意每个采样员最追加3个志愿者。</p> <p>当多出的志愿者分配完后，我们需要考虑剥夺低效率的采样员的志愿者&nbsp; 给 高效率的采样员，只要 高效率采样员增加的10%的效率&nbsp; &nbsp;可以大于&nbsp; 低效率采样员减少的20%的效率。逻辑同情况1。</p> <p></p> <p>根据ant_shi网友的指正，上面解析对于志愿者超出采样员数量四倍时的情况考虑不够全面：</p> <blockquote> <p>另外，对于情况2而言，如果采样员：志愿者 的比例，超过了1：4，那么超出4倍采样员范围的志愿者将没有效率提升作用，因此有效志愿者数量最多是四倍的采样员数量。</p> </blockquote> <p></p> <h2><a name="t5"></a>贪心思维解法</h2> <h3 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81"><a name="t6"></a>JavaScript算法源码</h3> <pre data-index="0" class="set-code-hide" name="code"><code class="language-javascript hljs"><ol class="hljs-ln hundred" style="width:991px"><li><div class="hljs-ln-numbers"><div class="hljs-ln-line hljs-ln-n" data-line-number="1"></div></div><div class="hljs-ln-code"><div class="hljs-ln-line"><span class="hljs-comment">/* JavaScript Node ACM模式 控制台输入获取 */</span></div></div></li><li><div class="hljs-ln-numbers"><div class="hljs-ln-line hljs-ln-n" data-line-number="2"></div></div><div class="hljs-ln-code"><div class="hljs-ln-line"><span class="hljs-keyword">const</span> readline = <span class="hljs-built_in">require</span>(<span class="hljs-string">"readline"</span>);</div></div></li><li><div class="hljs-ln-numbers"><div class="hljs-ln-line hljs-ln-n" data-line-number="3"></div></div><div class="hljs-ln-code"><div class="hljs-ln-line"> </div></div></li><li><div class="hljs-ln-numbers"><div class="hljs-ln-line hljs-ln-n" data-line-number="4"></div></div><div class="hljs-ln-code"><div class="hljs-ln-line"><span class="hljs-keyword">const</span> rl = readline.<span class="hljs-title function_">createInterface</span>({</div></div></li><li><div class="hljs-ln-numbers"><div class="hljs-ln-line hljs-ln-n" data-line-number="5"></div></div><div class="hljs-ln-code"><div class="hljs-ln-line"> <span class="hljs-attr">input</span>: process.<span class="hljs