CCF-CSP真题《202203-3—计算资源调度器》思路+python题解

深藏阁楼爱情的钟 2023-09-28 09:09 8阅读 0赞

> 想查看其他题的真题及题解的同学可以前往查看：[CCF-CSP真题附题解大全][CCF-CSP]

<table> 
 <tbody> 
  <tr> 
   <td>试题编号：</td> 
   <td>202203-3</td> 
  </tr> 
  <tr> 
   <td>试题名称：</td> 
   <td>计算资源调度器</td> 
  </tr> 
  <tr> 
   <td>时间限制：</td> 
   <td>1.0s</td> 
  </tr> 
  <tr> 
   <td>内存限制：</td> 
   <td>512.0MB</td> 
  </tr> 
  <tr> 
   <td>问题描述：</td> 
   <td> <h3>题目背景</h3> <p>西西艾弗岛上兴建了一批数据中心，建设了云计算资源平台。小 C 是主管西西艾弗云开发的工程师。西西艾弗云中有大量的计算节点，每个计算节点都有唯一编号。<br> 西西艾弗云分为多个可用区，每个计算节点位于一个特定的可用区。一个可用区中可以有多个计算节点。</p> <p>西西艾弗云中运行的计算任务分为不同的应用，每个计算任务都有一个应用与之对应，一个应用中可能包括多个计算任务。<br> 每个计算任务由一个特定的计算节点执行，下文中计算任务“运行在某可用区上”意即“运行在某可用区的计算节点上”。<br> 不同的计算任务对运行的计算节点的要求不尽相同。有的计算任务需要在指定可用区上运行，有的计算任务要和其它应用的计算任务在同一个可用区上运行，<br> 还有的希望不要和某个应用的计算任务在同一个计算节点上运行。<br> 对于一个计算任务，执行它的计算节点一旦选定便不再更改；在选定计算节点后，该任务对计算节点的要求就不再被考虑，<br> 即使新安排的计算任务使得此前已有的计算任务的要求被违反，也是合法的。</p> <p>下图示意性地说明了可用区、计算节点、计算任务之间的关系，同时也说明了应用和计算任务的对应关系。<img alt="" height="783" src="https://img-blog.csdnimg.cn/ea792f5ed2144ffea949bb2c084c969d.png" width="1134"></p> <p></p> <p>一开始，小 C 使用了电子表格程序来统计计算任务的分配情况。随着云上的计算节点和计算任务的不断增多，小 C 被这些奇怪的要求搞得焦头烂额，有的时候还弄错了安排，让客户很不满意。<br> 小 C 找到你，希望你能为他提供一个程序，能够输入要运行的计算任务和对节点的要求，结合西西艾弗云的现有计算节点信息，计算出计算任务应该被安排在哪个计算节点上。</p> <h3>问题描述</h3> <p>计算任务对计算节点的要求十分复杂而且又不好描述，你对小 C 表示写程序这件事很为难。于是，小 C 进行了调研，<br> 将这些需求进行了归纳整理，形成了下面这三种标准需求。在提出需求时，必须从这三种标准需求中选取若干种，每种需求只能有一条。选取多种需求意味着要同时满足这些需求。</p> 
    <ul> 
     <li> <p>计算节点亲和性</p> <p>计算任务必须在<strong>指定可用区</strong>上运行。</p> </li> 
     <li> <p>计算任务亲和性</p> <p>计算任务必须和<strong>指定应用</strong>的计算任务在同一可用区上运行。</p> <p>该要求对计算任务可以运行的可用区添加了限制。不考虑该任务本身，一个可用区若运行有指定应用的任务，则满足要求。</p> </li> 
     <li> <p>计算任务反亲和性</p> <p>计算任务不能和<strong>指定应用</strong>的计算任务在同一个计算节点上运行。</p> <p>该要求对计算任务可以运行的计算节点添加了限制。不考虑该任务本身，一个计算节点若运行有指定应用的任务，则不满足要求。</p> <p>当要执行的计算任务多起来，计算任务反亲和性的要求可能很难满足。因此在添加计算任务反亲和性要求时，还要指定这个要求是“必须满足”还是“尽量满足”。</p> </li> 
    </ul><p>小 C 要求你按照如下方法来分配计算节点：按照计算任务的启动顺序，根据要求，依次为每个计算任务选择计算节点。一旦选择了一个计算节点，就固定下来不再变动，<br> 并且在此后的选择中，不再考虑这个计算任务的要求。对每个计算任务，选择计算节点的方法是：</p> 
    <ol> 
     <li> <p>过滤阶段</p> <p>在这个阶段，先根据计算任务的要求，过滤出所有满足要求的计算节点。如果不存在这样的计算节点，并且指定了计算任务反亲和性要求，并且计算任务反亲和性要求是尽量满足的，<br> 那么去掉计算任务反亲和性要求，再过滤一次。如果还不存在，就认为该计算任务的要求无法满足，该计算任务无法分配。</p> </li> 
     <li> <p>排序阶段</p> <p>在这个阶段，将过滤后的计算节点按照这个方法排序：</p> 
      <ol> 
       <li>选择此时运行计算任务数量最少的计算节点；</li> 
       <li>选择编号最小的计算节点。</li> 
      </ol></li> 
    </ol><h3>输入格式</h3> <p>输入的第一行包含两个由空格分隔的正整数&nbsp;n&nbsp;和&nbsp;m，分别表示计算节点的数目和可用区的数目。计算节点从&nbsp;1&nbsp;到&nbsp;n&nbsp;编号，可用区从&nbsp;1&nbsp;到&nbsp;m&nbsp;编号；</p> <p>输入的第二行包含&nbsp;n&nbsp;个由空格分隔的正整数&nbsp;l1,l2,…li,…,ln，表示编号为&nbsp;i&nbsp;的计算节点位于编号为&nbsp;li&nbsp;的可用区。其中，0&lt;li≤m；</p> <p>输入的第三行包含一个正整数&nbsp;g，表示计算任务的组数；</p> <p>接下来的&nbsp;g&nbsp;行，每行包含六个由空格分隔的整数&nbsp;fi、ai、nai、pai、paai、paari，表示依次启动的一组计算任务的信息，其中：</p> 
    <ul> 
     <li>fi：表示要接连启动&nbsp;fi&nbsp;个所属应用和要求相同的计算任务，其中&nbsp;fi&gt;0；</li> 
     <li>ai：表示这&nbsp;fi&nbsp;个计算任务所属应用的编号，其中&nbsp;0&lt;ai≤Amax（Amax&nbsp;代表最大应用编号）；</li> 
     <li>nai：表示计算节点亲和性要求，其中&nbsp;0≤nai≤m。当&nbsp;nai=0&nbsp;时，表示没有计算节点亲和性要求；否则表示要运行在编号为&nbsp;nai&nbsp;的可用区内的计算节点上；</li> 
     <li>pai：表示计算任务亲和性要求，其中&nbsp;0≤pai≤Amax。当&nbsp;pai=0&nbsp;时，表示没有计算任务亲和性要求；否则表示必须和编号为&nbsp;pai&nbsp;的应用的计算任务在同一个可用区运行；</li> 
     <li>paai：表示计算任务反亲和性要求，其中&nbsp;0≤paai≤Amax。当&nbsp;paai=0&nbsp;时，表示没有计算任务反亲和性要求；否则表示不能和编号为&nbsp;paai&nbsp;的应用的计算任务在同一个计算节点上运行；</li> 
     <li>paari：表示计算任务亲和性要求是必须满足还是尽量满足，当&nbsp;paai=0&nbsp;时，paari&nbsp;也一定为 0；否则&nbsp;paari=1&nbsp;表示“必须满足”，paari=0&nbsp;表示“尽量满足”。</li> 
    </ul><p>计算任务按组输入实际上是一种简化的记法，启动一组&nbsp;(fi,ai,nai,pai,paai,paari)&nbsp;和连续启动&nbsp;fi&nbsp;组&nbsp;(1,ai,nai,pai,paai,paari)&nbsp;并无不同。</p> <h3>输出格式</h3> <p>输出&nbsp;g&nbsp;行，每行有&nbsp;fi&nbsp;个整数，由空格分隔，分别表示每个计算任务被分配的计算节点的情况。若该计算任务没有被分配，则输出 0；否则输出被分配的计算节点的编号。</p> <h3>样例输入</h3> <p>10 4<br> 1 1 1 1 1 2 2 2 2 2<br> 6<br> 2 1 4 1 2 1<br> 6 1 1 0 1 1<br> 1 2 2 0 0 0<br> 6 1 2 0 2 1<br> 5 2 2 0 1 0<br> 11 3 0 1 3 0</p> <h3>样例输出</h3> <p>0 0<br> 1 2 3 4 5 0<br> 6<br> 7 8 9 10 7 8<br> 6 6 6 6 6<br> 1 2 3 4 5 9 10 7 8 6 1</p> <h3>样例解释</h3> <p>本输入中声明了十个计算节点，前五个位于可用区 1，后五个位于可用区 2。可用区 3 和 4 不包含任何计算节点。</p> <p>对于第一组计算任务，由于它们声明了计算节点亲和性要求，但要求的可用区编号是 4，该可用区不包含计算节点，因此都不能满足。</p> <p>对于第二组计算任务，要在可用区 1 中启动 6 份应用 1 的任务，并且要求了计算任务反亲和性。因此，前五份任务分别被安排在前五个节点上。对于第六份任务，由于它必须运行于可用区 1，所以能够安排的范围仅限于前五个节点。但是它还指定了强制的计算任务反亲和性，前五个节点上已经启动了属于应用 1 的计算任务，因此没有能够运行它的节点。</p> <p>对于第三组计算任务，要在可用区 2 中启动 1 份应用 2 的任务，直接将其分配给节点 6。</p> <p>对于第四组计算任务，要在可用区 2 中启动 6 份应用 1 的任务，并且要求了计算任务反亲和性，不能和应用 2 的计算任务分配在同一个节点上。因此，节点 6 不能用于分配，这六份任务只能分配在节点 7～10 上。按照题意，选取运行任务数最少的和编号最小的，因此依次分配 7、8、9、10、7、8。</p> <p>对于第五组计算任务，要在可用区 2 中启动 5 份应用 2 的任务，并且要求了尽量满足的计算任务反亲和性，不能和应用 1 的计算任务分配在同一个节点上。此时，可用区 2 中的节点 6 上没有应用 1 的计算任务，因此这 5 份计算任务都会被分配到这个节点上。</p> <p>对于第六组计算任务，要启动 11 份应用 3 的任务，并且要求了尽量满足的计算任务反亲和性，不能和应用 3 的其它计算任务分配在同一个节点上，同时要求和应用 1 的计算任务位于同一个可用区。应用 1 位于两个可用区，因此全部 10 个节点都可以用于分配。对于前 10 份任务，按照题意，依次选取运行的任务数最少且编号最小的节点进行分配。对于第 11 份任务，由于所有的节点上都运行有应用 3 的任务，因此没有节点符合它的反亲和性要求。又因为反亲和性要求是尽量满足的，因此可以忽略这一要求，将它安排在节点 1 上。</p> <h3>子任务</h3> <p>本题包含&nbsp;20&nbsp;个测试用例，每个&nbsp;5&nbsp;分。</p> <p>全部测试数据保证&nbsp;0&lt;m≤n≤1000，0&lt;g≤∑i=1gfi≤2000。</p> <p>部分测试点的特殊性质详见下表，比如测试点&nbsp;1、2&nbsp;中最大应用编号仅为&nbsp;10&nbsp;且不包含任何需求。</p> 
    <table> 
     <thead> 
      <tr> 
       <th>测试点</th> 
       <th>最大应用编号</th> 
       <th>计算节点亲和性</th> 
       <th>计算任务亲和性</th> 
       <th>计算任务反亲和性</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>1, 2</td> 
       <td>Amax=10</td> 
       <td>无要求（nai=0）</td> 
       <td>无要求（pai=0）</td> 
       <td>无要求（paai=0）</td> 
      </tr> 
      <tr> 
       <td>3, 4</td> 
       <td>Amax=109</td> 
       <td>无要求（nai=0）</td> 
       <td>无要求（pai=0）</td> 
       <td>无要求（paai=0）</td> 
      </tr> 
      <tr> 
       <td>5, 6, 7</td> 
       <td>Amax=10</td> 
       <td>nai≥0</td> 
       <td>无要求（pai=0）</td> 
       <td>无要求（paai=0）</td> 
      </tr> 
      <tr> 
       <td>8, 9, 10</td> 
       <td>Amax=109</td> 
       <td>nai≥0</td> 
       <td>无要求（pai=0）</td> 
       <td>无要求（paai=0）</td> 
      </tr> 
      <tr> 
       <td>11, 12, 13</td> 
       <td>Amax=10</td> 
       <td>nai≥0</td> 
       <td>无要求（pai=0）</td> 
       <td>paai≥0</td> 
      </tr> 
      <tr> 
       <td>14, 15, 16</td> 
       <td>Amax=109</td> 
       <td>nai≥0</td> 
       <td>无要求（pai=0）</td> 
       <td>paai≥0</td> 
      </tr> 
      <tr> 
       <td>17, 18</td> 
       <td>Amax=10</td> 
       <td>nai≥0</td> 
       <td>pai≥0</td> 
       <td>paai≥0</td> 
      </tr> 
      <tr> 
       <td>19, 20</td> 
       <td>Amax=109</td> 
       <td>nai≥0</td> 
       <td>pai≥0</td> 
       <td>paai≥0"]</td> 
      </tr> 
     </tbody> 
    </table></td> 
  </tr> 
 </tbody> 
</table>

**真题来源：**[计算资源调度器][Link 1]

> 感兴趣的同学可以进去进行练习提交

**解题建议：**

> 注意题目测试点的要求，从最简单的两个测试点开始解，先拿20分到手再说！

**20分题解：**

n, m = map(int,input().split())
    nums = list(map(int,input().split()))
    temp = [i+1 for i in range(n)]
    point = {}
    for id, value in enumerate(nums):
        if value not in point:
            point[value] = [id+1]
        else:
            point[value].append(id+1)
    g = int(input())
    datas = [[i for i in map(int, input().split())] for j in range(g)]
    output = [[] for j in range(g)]
    time = 0
    for data in datas:
        for i in range(data[0]):
            output[time].append(0) 
            output[time][i] = temp.pop(0)
            temp.append(output[time][i])
        time += 1
    for i in range(g):
        print(*output[i])

**运行结果：**

![89cd93babfbd455882519034eaa0f463.png][]

--------------------

**50分题解：**

--------------------

**80分题解：**

--------------------

**100分题解：**

[CCF-CSP]: https://blog.csdn.net/weixin_53919192/article/details/124893395?spm=1001.2014.3001.5502
[Link 1]: http://118.190.20.162/view.page?gpid=T141
[89cd93babfbd455882519034eaa0f463.png]: https://img-blog.csdnimg.cn/89cd93babfbd455882519034eaa0f463.png