B4250 [语言月赛 202503] 蛋挞制作工坊 题解

· · 题解

[语言月赛 202503] 蛋挞制作工坊 题解

Source & Knowledge

本题来源于 2025 年 3 月的语言月赛，主要考察较复杂题目的模拟与代码设计和冒泡排序的应用。

文字题解

题目要求按照不同材料的剩余量对小朋友排序，因此我们需要进行如下计算和排序：

计算每个小朋友能制作的蛋挞数量

由于制作蛋挞时，每种材料的用量不同，我们需要计算每个小朋友最多能做多少个蛋挞：

\text{count}_i = \min\left( \frac{c_{i,1}}{g_1}, \frac{c_{i,2}}{g_2}, \dots, \frac{c_{i,m}}{g_m} \right)

其中，\text{count}_i 是第 i 个小朋友能制作的蛋挞数量。

int count[55];
// 读入部分省略，可参考前七道题目的题解学习
for (int i = 1; i <= n; i++) {
    count[i] = 1000000000;
    // 10 的 9 次方，十亿，所有小朋友能制作蛋挞的最大数目
    for (int j = 1; j <= m; j++) {
        count[i] = min(count[i], c[i][j] / g[j]);
    }
}

计算每个小朋友的剩余材料量

计算公式：

\text{remain}_{i,j} = c_{i,j} - \text{count}_i \times g_j

这里，\text{remain}_{i,j} 表示第 i 个小朋友在使用 j 号材料制作蛋挞后剩余的材料量。

int remain[55][55];
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        remain[i][j] = c[i][j] - count[i] * g[j];
    }
}

按指定材料进行排序并输出

Alice 会按照指定的材料剩余量从小到大排序，如果剩余量相同，则按 Bob 的规则。因此我们有总的规则：

按照这种排序规则，我们做冒泡排序。

由于过程中涉及到的变量众多，冒泡排序又是非常需要交换的一种排序方式，因此在交换小朋友时，直接交换所有涉及的变量不是很优秀。这里，我们做一些简化运算。

我们对每种材料，使用一个 index 数组。index[i] 表示，在排序后，站在第 i 位的小朋友的编号应该是多少。

这样，我们在排序时，只需要关心 index 数组的交换即可。比较时，可以通过 remain[index[i]][...] 等的方式来读取数据。

int index[55];
for (int k = 1; k <= m; k++) { // 枚举 Alice 指定的
  for (int i = 1; i <= n; i++) index[i] = i;
  for (int i = 1; i <= n - 1; i++) { // 冒泡排序的两重循环
      for (int j = 1; j <= n - i; j++) {
          int a = index[j], b = index[j + 1];

          // 第一个规则
          if (remain[a][k] > remain[b][k]) {
              // 剩余指定材料不满足 a < b，应当交换
              swap(index[j], index[j + 1]);
          }

          // 第二个规则
          if (remain[a][k] != remain[b][k]) continue;
          if (count[a] < count[b]) {
              // 制作蛋挞数量不满足 a > b，应当交换
              swap(index[j], index[j + 1]);
          }

          // 第三个规则
          if (count[a] != count[b]) continue;
          if (a > b)) {
              // 编号不满足 a < b，应当交换
              swap(index[j], index[j + 1]);
          }
      }
  }

  for (int i = 1; i <= n; i++) {
      cout << index[i] << " ";
  }
  cout << endl;
}