自动搬运

查看原文

来自洛谷，原作者为

	Maxmilite **

搬运于2025-08-24 21:18:07，当前版本为作者最后更新于2025-03-19 22:31:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

[语言月赛 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;
}