题目

Mice and Rice is the name of a programming contest in which each programmer must write a piece of code to control the movements of a mouse in a given map. The goal of each mouse is to eat as much rice as possible in order to become a FatMouse.

First the playing order is randomly decided for $N_{P}$ programmers. Then every $N_{G}$ programmers are grouped in a match. The fattest mouse in a group wins and enters the next turn. All the losers in this turn are ranked the same. Every $N_{G}$ winners are then grouped in the next match until a final winner is determined.

For the sake of simplicity, assume that the weight of each mouse is fixed once the programmer submits his/her code. Given the weights of all the mice and the initial playing order, you are supposed to output the ranks for the programmers.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive integers: $N_{P}$ and $N_{G}( \leq 1000)$ , the number of programmers and the maximum number of mice in a group, respectively. If there are less than $N_{G}$ mice at the end of the player’s list, then all the mice left will be put into the last group. The second line contains $N_{P}$ distinct non-negative numbers $W_{i}\left(i=0, \cdots, N_{P}-1\right)$ where each $W_{i}$ is the weight of the i-th mouse respectively. The third line gives the initial playing order which is a permutation of $0, \cdots, N_{P}-1$ (assume that the programmers are numbered from 0 to $N_{P}-1$ ). All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the final ranks in a line. The i-th number is the rank of the i-th programmer, and all the numbers must be separated by a space, with no extra space at the end of the line.

Sample Input:

1
2
3

11 3
25 18 0 46 37 3 19 22 57 56 10
6 0 8 7 10 5 9 1 4 2 3

Sample Output:

1	5 5 5 2 5 5 5 3 1 3 5

题解

思路

题目意思真的太抽象了
我来慢慢给你捋一捋
题目先给你老鼠总数，和每个小组有几只老鼠
接着呢，给你一串数，是每个老鼠的体重
自然，这些数的出现顺序是依照老鼠的id下标的
也就是说，给出来的一串数，下标是id，值是这个id的老鼠的体重，id从0开始计
接着呢，给出一长串数，这串数是出场顺序
注意咯！这给出的数，下标是id，值是出场顺序。
拿题目的例子来说的话就是，给定下面这些数

11 3
25 18 0 46 37 3 19 22 57 56 10
6 0 8 7 10 5 9 1 4 2 3
<!--hexoPostRenderEscape:<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line">+ 第0个老鼠体重是25,它在第6个出场。</span><br><span class="line"></span><br><span class="line">+ 第1个老鼠体重是18,它在第0个出场。</span><br><span class="line"></span><br><span class="line">+ 题目的意思是，按出场顺序，按分组个数对它们分组。</span><br><span class="line"></span><br><span class="line">+ 像这题的分组个数是3</span><br><span class="line"></span><br><span class="line">+ 那么第1号老鼠，第7号老鼠，第九号老鼠的出场顺序是&#96;[0,1,2]&#96;，它们就分为一组，以此类推。</span><br><span class="line"></span><br><span class="line">+ 到最后剩下两只老鼠不足3个，那么把它们分到一组（题目里说和最后一组合并，是大骗子）。</span><br><span class="line"></span><br><span class="line">+ 所以我们现在拥有四组老鼠。</span><br><span class="line"></span><br><span class="line">+ 在每一组老鼠里面，选出一个最大的。</span><br><span class="line"></span><br><span class="line">+ 即按照最后一行，每三个每三个分割，将值映射到体重，取最大的。</span><br><span class="line"></span><br><span class="line">+ 对这题来说，我们选出来的老鼠id是&#96;[8,7,9,3]&#96;。它们的出场顺序是&#96;[2,3,6,10]&#96;。它们的体重是&#96;[57,22,56,46]&#96;。</span><br><span class="line"></span><br><span class="line">+ 我们选出来了四个，那么剩下的七个老鼠的排名就是&#96;1+4 &#x3D; 5&#96;，被淘汰，这四个老鼠进入下一轮。</span><br><span class="line"></span><br><span class="line">+ 现在&#96;[8,7,9,3]&#96;四只老鼠的出场顺序是&#96;[0,1,2,3]&#96;</span><br><span class="line"></span><br><span class="line">+ 那么&#96;3&#96;号老鼠直接晋级，而&#96;[8,7,9]&#96;这三只老鼠里面最重的是&#96;8&#96;。</span><br><span class="line"></span><br><span class="line">+ 所以&#96;[7,9]&#96;的排名等于&#96;1+2 &#x3D; 3&#96;</span><br><span class="line"></span><br><span class="line">+ 继续对比&#96;[8,3]&#96;两位选手。</span><br><span class="line"></span><br><span class="line">+ 就这样重复进行并更新排名，直到只剩最后一人。</span><br><span class="line"></span><br><span class="line">## 数据结构</span><br><span class="line"></span><br><span class="line">+ num_pro,max_mice 是老鼠总数和分组的每组老鼠数</span><br><span class="line">+ weight是一个列表，表示老鼠们的体重</span><br><span class="line">  + 下标是id</span><br><span class="line">  + 值是体重</span><br><span class="line">+ init_order 是给出的最初的出场顺序列表</span><br><span class="line">  + **下标是出场顺序**</span><br><span class="line">  + **值是id**</span><br><span class="line">+ rank 是排名列表</span><br><span class="line">  + 下标是id</span><br><span class="line">  + 值是排名</span><br><span class="line">+ weight_last 记录上一轮的各个选手的出场顺序以及它们的体重</span><br><span class="line">  + **下标是出场顺序**</span><br><span class="line">  + **值是选手体重**</span><br><span class="line">+ weight_next 记录下一轮的各个选手的出场顺序以及它们的体重</span><br><span class="line">  - **下标是出场顺序**</span><br><span class="line">  - **值是选手体重**</span><br><span class="line"></span><br><span class="line">## 算法</span><br><span class="line"></span><br><span class="line">+ 先初始化weight,init_order,rank</span><br><span class="line">+ 然后初始化weight_last为当前的比赛顺序，也就是将第0个登场的选手的体重放在第0个这样排列。</span><br><span class="line">+ 初始化weight_next，它表示下一轮的擂台上的老鼠数，所以循环条件就是这个列表长度大于1。</span><br><span class="line">+ 初始化的时候只要是一个不为空的长度列表就行（因为在循环里面都要清空）</span><br><span class="line">+ 开始循环</span><br><span class="line">  + 先设置weight_next为空</span><br><span class="line">  + 对于上一轮也就是在weight_last的选手</span><br><span class="line">  + 按照它们的出场顺序遍历</span><br><span class="line">  + 找到遍历选手的所在组</span><br><span class="line">    + 可以根据选手的下标，整除以一组人数，再乘以一组人数，得到这一组的起始下标（也就是选手下标 - （选手下标%一组人数））</span><br><span class="line">    + 而这一组的结尾下标就是起始下标再加上一组人数</span><br><span class="line">    + 对于最后人数不足的组也按照这一标准</span><br><span class="line">    + 用weight_last和上面的起始结尾下标切片，就是所在组的信息</span><br><span class="line">  + 当它不是所在组内的最大值的时候</span><br><span class="line">    + 它需要更新排名，增加的人数就是这轮比赛会晋级的人数。</span><br><span class="line">    + 也就是这场擂台的人数除以一组人数，但是有余数的话要加一。即场上的所剩组数。</span><br><span class="line">  + 当这个选手的体重是所在组的最大值的时候</span><br><span class="line">    + 放到weight_next里面</span><br><span class="line">  + 最后把weight_last更新为weight_next，进入下一场比拼</span><br><span class="line">+ 直到weight_next只剩下一人，即冠军，输出即可。</span><br><span class="line"></span><br><span class="line">## 代码</span><br><span class="line"></span><br><span class="line">+ 由于使用Python能够AC，因此只放了Python的代码。</span><br><span class="line"></span><br><span class="line">&#96;&#96;&#96;python</span><br><span class="line"># 输入与数据结构初始化</span><br><span class="line">from math import ceil</span><br><span class="line">num_pro, max_mice &#x3D; list(map(int, input().split()))</span><br><span class="line">weight &#x3D; list(map(int, input().split()))</span><br><span class="line">init_order &#x3D; list(map(int, input().split()))</span><br><span class="line">rank &#x3D; [1 for _ in range(num_pro)]</span><br><span class="line">weight_last &#x3D; [weight[init_order[i]] for i in range(num_pro)]</span><br><span class="line"></span><br><span class="line"># 模拟擂台</span><br><span class="line">weight_next &#x3D; weight_last.copy()</span><br><span class="line">while len(weight_next) &gt; 1:</span><br><span class="line">    weight_next.clear()</span><br><span class="line">    for i in range(len(weight_last)):</span><br><span class="line">        if weight_last[i] !&#x3D; max(weight_last[(i &#x2F;&#x2F; max_mice) * max_mice:(i &#x2F;&#x2F; max_mice) * max_mice + max_mice]):</span><br><span class="line">            rank[weight.index(weight_last[i])] +&#x3D; (ceil(len(weight_last) &#x2F; max_mice))</span><br><span class="line">        else:</span><br><span class="line">            weight_next.append(weight_last[i])</span><br><span class="line">    weight_last &#x3D; weight_next.copy()</span><br><span class="line"></span><br><span class="line"># 输出</span><br><span class="line">print(&quot; &quot;.join(map(str,rank)))</span><br></pre></td></tr></table></figure>:hexoPostRenderEscape-->