干货分享|算法竞赛真题讲解2

本篇文章选取了各类赛事的真题进行讲解，具体的题目读者可以通过网络搜索找到原题。不同的赛事的题目难度和风格各有不同。

3.【The 2018 ICPC Asia Qingdao Regional Programming Contest (The 1st Universal Cup,Stage 9: Qingdao)】J. Books

题目大意

书店里有n本书。因为小D很有钱，故小D会按如下策略买书。

按顺序从第1本到第n本考虑这n本书：

对于正在考虑的这本书，如果小D有足够的钱（不低于书的价格），就会买这本书，并且小D拥有的钱会减少这本书的价格。

如果小D有的钱低于这本书的价格，就会跳过这本书。

你只知道这n本书的价格和小D最终买到的书的数量m，而你并不知道小D一开始拥有多少钱。

你想知道，在满足按照上述策略最终买到m本书的情况下，小D一开始最多有多少钱（一个非

负整数）。

解题思路

本题容易有一个错觉：钱越多，买到的书越多（或相等）。实际上这是不对的，因为小D需要

严格按照顺序买，并不会选择最优的方案。例如，书的价格分别为[1,5,2,2]时，5元可以买3本，而6元却只能买2本。

我们换个思路来解题，首先考虑特殊情况：

当n=m时，输出Richman。

所有价格为0的书一定可以拿。一旦遇到一本价格为0的书，相当于让m减小1。若m<0，则

说明无论多少钱，拿的书都会比m多，输出“Impossible”。

否则，小D一定是拿前m本书（此时已经将价格为0的书去除），后面剩余的书一本都不能

买。此时，可以再加上后面剩余部分的最小价格减去1。

参考代码

• #include <bits/stdc++.h>
  #define int long long
  using namespace std;
  const int N = 2e5 + 9, inf = 8e18; // 定义数组最大大小和无穷大的近似值
  int a[N], b[N], bn, n, m; // 声明全局变量
  void solve()
  {
  cin >> n >> m; // 读入 n（数组大小）和 m（目标值）
  for(int i = 1;i <= n; ++ i)cin >> a[i]; // 读入数组 a 中的 n 个元素
  if(n == m)
  {
  cout << "Richman" << '\n'; // 如果 n 等于 m，直接输出 "Richman" 并返回
  return;
  }
  // 此时必然有 m < n，因为程序运行到这里说明 n != m
  bn = 0; // 初始化有效元素计数器
  for(int i = 1;i <= n; ++ i)
  if(a[i] == 0)m --; // 如果当前元素为 0，减少 m 的值
  else b[++ bn] = a[i]; // 否则将该元素存入数组 b，并更新有效元素计数器
   // 到这里依然有 m < bn，因为零值元素会减少 m，b 数组的大小 bn 小于或等于 n
  if(m < 0)
  {
  cout << "Impossible" << '\n'; // 如果 m 已经小于 0，输出 "Impossible" 并返回
  return;
  }
  int ans = 0; // 初始化答案
  for(int i = 1;i <= m; ++ i)ans += b[i]; // 取前 m 个有效元素求和
  int mi = b[m + 1]; // 从第 m+1 个元素开始寻找最小值
  for(int i = m + 1;i <= bn; ++ i)mi = min(mi, b[i]);
  cout << ans + mi - 1 << '\n'; // 输出结果：总和加上找到的最小值减去 1
  }
  signed main()
  {printf("hello world!");
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int _;cin >> _; // 读入测试案例数
  while(_ --)solve(); // 循环处理每个测试案例
  return 0;
  }

4.【The 2022 ICPC Asia Nanjing Regional Contest】F. Inscryption

若ai=1，则获得一只攻击力为1的鼹鼠。

若ai=−1，则将两只鼹鼠合并为一只，且攻击力为两只鼹鼠攻击力的总和。

若ai=0，则需选择执行以上两种操作中的一种。

问：最终所有鼹鼠攻击力的平均值最大是多少？

解题思路

可以发现，操作1会使得平均值降低（或不变），操作−1可以使得平均值升高。

因此，对于操作0（ai = 0），我们需要尽量多执行操作−1，尽量少执行操作1（ai=1），但当

只有一只鼹鼠时，不得不执行操作1。

为此，可以利用“反悔贪心”的思想：在遇到操作0且条件允许时，优先执行操作1，同时记录操作1的次数。如果后续遇到操作−1（ai=-1）且发现无法执行时，可将之前的某次操作0反悔，改为执行操作-1，以保证操作的合法性并尽量提高平均值。

参考代码

• #include <bits/stdc++.h>
  #define int long long
  using namespace std;
  const int N = 1e6 + 9, inf = 2e18; // 常量 N 表示数组大小，inf 表示无穷大
  int a[N]; // 用于存储输入操作序列的数组
  // 计算最大公约数的函数，使用递归实现
  int gcd(int a, int b){return b == 0 ? a : gcd(b, a % b);}
  void solve()
  {
  int n; cin >> n; // 输入操作序列的长度
  for(int i = 1;i <= n; ++ i)cin >> a[i]; // 输入操作序列
  // 当前所有鼹鼠的总攻击力，当前鼹鼠的总数量
  int sum = 1, cnt = 1, c2 = 0; // 遇到操作0时，记录执行了多少次可以反悔操作-1
  for(int i = 1;i <= n; ++ i)
  {
  if(a[i] == 1) // 操作1：增加一只攻击力为 1 的鼹鼠
  {
  sum ++, cnt ++;
  }
  else if(a[i] == -1) // 操作-1：将两只鼹鼠合并为一只
  {
  if(cnt == 1 && c2)
  {
  // 如果当前只有 1 只鼹鼠，且存在可反悔的操作，则执行反悔
  sum ++, cnt += 2; // 将一次操作-1反悔为操作1，鼹鼠数量增加 2
  c2 --; // 可反悔操作的次数减少 1
  }
  if(cnt == 1) // 如果当前只有1只鼹鼠，无法进行操作-1，直接输出 -1
  {
  cout << -1 << '\n';
  return;
  }
  cnt --; // 执行操作-1，鼹鼠数量减少 1
  }else // 遇到操作0时，优先执行操作-1
  {
  if(cnt > 1)
  {
  cnt --, c2 ++; // 表示执行了一次操作-1，并记录下来（此操作是可反悔的）
   // 鼹鼠数量减少 1
  }
  else sum ++, cnt ++; // 如果只有1只鼹鼠，无法执行操作-1，则执行操作1
  }
  }
  // 计算最终平均攻击力的最简分数形式
  int g = gcd(sum, cnt); // 计算 sum 和 cnt 的最大公约数
  sum /= g, cnt /= g; // 分子化简，分母化简
  cout << sum << ' ' << cnt << '\n'; // 输出结果
  }
  signed main()
  {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 关闭同步，提高输入/输出效率
   // 取消 cin 和 cout 的绑定
  int _; cin >> _; // 输入测试用例的数量
  while(_ --)solve(); // 逐个处理每个测试用例
  return 0; // 程序正常结束
  }

本文摘自《算法竞赛入门笔记》，获出版社和作者授权发布。

购书链接：算法竞赛入门笔记——jd