CCF-CSP真题《202112-2—序列查询新解》思路+python题解

蔚落 2023-09-29 15:34 10阅读 0赞

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

<table> 
 <tbody> 
  <tr> 
   <td>试题编号：</td> 
   <td>202112-2</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>上一题“序列查询”中说道：<br> A=[A0,A1,A2,⋯,An]&nbsp;是一个由&nbsp;n+1&nbsp;个&nbsp;[0,N)&nbsp;范围内整数组成的序列，满足&nbsp;0=A0&lt;A1&lt;A2&lt;⋯&lt;An&lt;N。基于序列&nbsp;A，对于&nbsp;[0,N)&nbsp;范围内任意的整数&nbsp;x，查询&nbsp;f(x)&nbsp;定义为：序列&nbsp;A&nbsp;中<strong>小于等于</strong>&nbsp;x&nbsp;的整数里<strong>最大</strong>的数的<strong>下标</strong>。</p> <p>对于给定的序列&nbsp;A&nbsp;和整数&nbsp;x，查询&nbsp;f(x)&nbsp;是一个很经典的问题，可以使用二分搜索在&nbsp;O(log⁡n)&nbsp;的时间复杂度内轻松解决。但在 IT 部门讨论如何实现这一功能时，小 P 同学提出了些新的想法。</p> <h3>题目描述</h3> <p>小 P 同学认为，如果事先知道了序列&nbsp;A&nbsp;中整数的分布情况，就能直接估计出其中小于等于&nbsp;x&nbsp;的最大整数的大致位置。接着从这一估计位置开始线性查找，锁定&nbsp;f(x)。如果估计得足够准确，线性查找的时间开销可能比二分查找算法更小。</p> <p>比如说，如果&nbsp;A1,A2,⋯,An&nbsp;均匀分布在&nbsp;(0,N)&nbsp;的区间，那么就可以估算出：<br> f(x)≈(n+1)⋅xN</p> <p>为了方便计算，小 P 首先定义了比例系数&nbsp;r=⌊Nn+1⌋，其中&nbsp;⌊&nbsp;⌋&nbsp;表示下取整，即&nbsp;r&nbsp;等于&nbsp;N&nbsp;除以&nbsp;n+1&nbsp;的商。进一步地，小 P 用&nbsp;g(x)=⌊xr⌋&nbsp;表示自己估算出的&nbsp;f(x)&nbsp;的大小，这里同样使用了下取整来保证&nbsp;g(x)&nbsp;是一个整数。</p> <p>显然，对于任意的询问&nbsp;x∈[0,N)，g(x)&nbsp;和&nbsp;f(x)&nbsp;越接近则说明小 P 的估计越准确，后续进行线性查找的时间开销也越小。因此，小 P 用两者差的绝对值&nbsp;|g(x)−f(x)|&nbsp;来表示处理询问&nbsp;x&nbsp;时的误差。</p> <p>为了整体评估小 P 同学提出的方法在序列&nbsp;A&nbsp;上的表现，试计算：<br> error(A)=∑i=0N−1|g(i)−f(i)|=|g(0)−f(0)|+⋯+|g(N−1)−f(N−1)|</p> <h3>输入格式</h3> <p>从标准输入读入数据。</p> <p>输入的第一行包含空格分隔的两个正整数&nbsp;n&nbsp;和&nbsp;N。</p> <p>输入的第二行包含&nbsp;n&nbsp;个用空格分隔的整数&nbsp;A1,A2,⋯,An。</p> <p>注意&nbsp;A0&nbsp;固定为&nbsp;0，因此输入数据中不包括&nbsp;A0。</p> <h3>输出格式</h3> <p>输出到标准输出。</p> <p>仅输出一个整数，表示&nbsp;error(A)&nbsp;的值。</p> <h3>样例1输入</h3> <p>3 10<br> 2 5 8</p> <h3>样例1输出</h3> <p>5</p> <h3>样例1解释</h3> <p>A=[0,2,5,8]</p> <p>r=⌊Nn+1⌋=⌊103+1⌋=2</p> 
    <table> 
     <thead> 
      <tr> 
       <th>i</th> 
       <th>0</th> 
       <th>1</th> 
       <th>2</th> 
       <th>3</th> 
       <th>4</th> 
       <th>5</th> 
       <th>6</th> 
       <th>7</th> 
       <th>8</th> 
       <th>9</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>f(i)</td> 
       <td>0</td> 
       <td>0</td> 
       <td>1</td> 
       <td>1</td> 
       <td>1</td> 
       <td>2</td> 
       <td>2</td> 
       <td>2</td> 
       <td>3</td> 
       <td>3</td> 
      </tr> 
      <tr> 
       <td>g(i)</td> 
       <td>0</td> 
       <td>0</td> 
       <td>1</td> 
       <td>1</td> 
       <td>2</td> 
       <td>2</td> 
       <td>3</td> 
       <td>3</td> 
       <td>4</td> 
       <td>4</td> 
      </tr> 
      <tr> 
       <td>|g(i)−f(i)|</td> 
       <td>0</td> 
       <td>0</td> 
       <td>0</td> 
       <td>0</td> 
       <td>1</td> 
       <td>0</td> 
       <td>1</td> 
       <td>1</td> 
       <td>1</td> 
       <td>1</td> 
      </tr> 
     </tbody> 
    </table><h3>样例2输入</h3> <p>9 10<br> 1 2 3 4 5 6 7 8 9</p> <h3>样例2输出</h3> <p>0</p> <h3>样例3输入</h3> <p>2 10<br> 1 3</p> <h3>样例3输出</h3> <p>6</p> <h3>样例3解释</h3> <p>A=[0,1,3]</p> <p>r=⌊Nn+1⌋=⌊102+1⌋=3</p> 
    <table> 
     <thead> 
      <tr> 
       <th>i</th> 
       <th>0</th> 
       <th>1</th> 
       <th>2</th> 
       <th>3</th> 
       <th>4</th> 
       <th>5</th> 
       <th>6</th> 
       <th>7</th> 
       <th>8</th> 
       <th>9</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>f(i)</td> 
       <td>0</td> 
       <td>1</td> 
       <td>1</td> 
       <td>2</td> 
       <td>2</td> 
       <td>2</td> 
       <td>2</td> 
       <td>2</td> 
       <td>2</td> 
       <td>2</td> 
      </tr> 
      <tr> 
       <td>g(i)</td> 
       <td>0</td> 
       <td>0</td> 
       <td>0</td> 
       <td>1</td> 
       <td>1</td> 
       <td>1</td> 
       <td>2</td> 
       <td>2</td> 
       <td>2</td> 
       <td>3</td> 
      </tr> 
      <tr> 
       <td>|g(i)−f(i)|</td> 
       <td>0</td> 
       <td>1</td> 
       <td>1</td> 
       <td>1</td> 
       <td>1</td> 
       <td>1</td> 
       <td>0</td> 
       <td>0</td> 
       <td>0</td> 
       <td>1</td> 
      </tr> 
     </tbody> 
    </table><h3>子任务</h3> <p>70%&nbsp;的测试数据满足&nbsp;1≤n≤200&nbsp;且&nbsp;n&lt;N≤1000；</p> <p>全部的测试数据满足&nbsp;1≤n≤105&nbsp;且&nbsp;n&lt;N≤109。</p> <h3>提示</h3> <p>需要注意，输入数据&nbsp;[A1⋯An]&nbsp;并不一定均匀分布在&nbsp;(0,N)&nbsp;区间，因此总误差&nbsp;error(A)&nbsp;可能很大</p> </td> 
  </tr> 
 </tbody> 
</table>

**真题来源：**[序列查询新解][Link 1]

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

**70分题解：**

**1）内存超限的代码：**

n, N = map(int, input().split())
    nums = [i for i in map(int, input().split())]
    r = N//(n+1)
    f = [0 for i in range(N+1)]
    for x in nums:
        f[x] = 1
    sum = 0
    for i in range(1,N): 
        if f[i]==1:
            f[i] = f[i-1]+1
        else:
            f[i] = f[i-1]
        sum += abs(i//r-f[i])
    print(sum)

**运行结果：**

![54684ef58ce1447ab333a067ff49d812.png][]

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

**2）****运行超时****的代码：**

n, N = map(int, input().split())
    nums = [i for i in map(int, input().split())]
    r = N//(n+1)
    f = 0
    sum = 0
    for i in range(1,N): 
        if i in nums:
            f += 1
        sum += abs(i//r-f)
    print(sum)

**运行结果：**

![e929e8a96fd74bdc82455f0dc4046b2f.png][]

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

**满分题解：**

[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=T137
[54684ef58ce1447ab333a067ff49d812.png]: https://img-blog.csdnimg.cn/54684ef58ce1447ab333a067ff49d812.png
[e929e8a96fd74bdc82455f0dc4046b2f.png]: https://img-blog.csdnimg.cn/e929e8a96fd74bdc82455f0dc4046b2f.png