P1223 排队接水 · 习题解析｜信息学奥赛算法练功房

0题目原文（本地存了一份）

深入：为什么这里抄了一份题面

原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库。

转录自洛谷 P1223，日期见页头。两边不一致时信原站。

题目描述

有 n 个人在一个水龙头前排队接水，假如每个人接水的时间为 Tᵢ，请编程找出这 n 个人排队的一种顺序，使得 n 个人的平均等待时间最小。

一个人的等待时间不包括他的接水时间。

如果两个人接水的时间相同，编号更小的人应当排在前面。

输入格式

第一行为一个整数 n。

第二行 n 个整数，第 i 个整数 Tᵢ 表示第 i 个人的接水时间 Tᵢ。

输出格式

输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。

数据规模与约定

1 ≤ n ≤ 1000，1 ≤ tᵢ ≤ 10⁶，不保证 tᵢ 不重复。

输入输出样例

输入

10
56 12 1 99 1000 234 33 55 99 812

输出

3 2 7 8 1 4 9 6 10 5
291.90

第一行是人数，第二行是每个人的接水时间。

学生版：一页看懂这道题

这道题考什么：第 19 章的第一道例题 —— 接水快的人排前面 （按接水时间从小到大排）。为什么这样最优，第 19 章已经证明过了。

算法三分钟就写完，难的全在算法之外。最容易错的四处：

第一行要输出的是编号，不是排好序的时间 ⇒ 排序时要把编号一起带上。
时间相同时编号小的在前 ⇒ 排 (时间, 编号) 这个 pair 最省事；如果自己写比较函数只比时间，std::sort 不保证相同的两个人谁在前。
总等待时间会超过 int（最坏约 5 × 10¹¹）⇒ 用 long long。
平均值要用小数除：(double)total / n，不是 (double)(total / n)。

能 AC 的：p1223.cpp（第 ⑤ 步）。

下面每一步里灰色的「深入」块是折叠的：那是这些结论怎么实测出来的，第一遍可以跳过。

1算法：接水快的排前面

排在第 1 位的人，他接水时后面 n - 1 个人都在等；排在第 2 位的，后面 n - 2 个人在等…… 所以越靠前的人，他的接水时间被越多的人一起等。让接水最快的人排最前面，总等待最小。

    总等待 = Σ (n-1-i) · t[排在第 i+1 位的人]      i = 0, 1, ..., n-1

深入：怎么确认「从小到大排」是对的

第 19 章正文用「交换论证」证明过（第 ⑤ 步），并用全排列暴力对拍过（第 ③ 步）。这里再验一次：n ≤ 8 时把全部 n! 种排队顺序枚举一遍取最小，和「排序后累加」逐组比 —— 320 组，不一致 0 组。（暴力程序就是 code/19-greedy-sorting/brute.cpp。）

2坑一：输出编号，以及时间相同的人谁在前

题面要的第一行是「排队顺序」，也就是人的编号。所以不能只排 t，要排 (时间, 编号) 这个 pair。

pair 顺手解决了「时间相同编号小的在前」

pair 的默认比较是「先比 first，一样再比 second」。把时间放 first、编号放 second，题面要的那条规则就自动满足了，一个字都不用多写。

很多人写的是结构体＋比较函数，而比较函数只比时间：

p1223Cmp.cpp错法一：比较器只比时间

// P1223 错法一：比较器**只比接水时间** —— 并列时编号顺序不保证
//
// ★★★ 这是这一页的主角，也是这道题最隐蔽的一个 bug：
//   题面白纸黑字写着「**如果两个人接水的时间相同，编号更小的人应当排在前面**」，
//   而 `std::sort` **不是稳定排序** —— 比较器说「这两个不分先后」时，
//   它把谁放前面是没有承诺的。
//
// ⚠ 而它的抓获率有**两个主语**，页面第 ④ 步各量了一条曲线：
//   ① **值域**：`t` 的取值范围决定了「有没有并列」。没有并列，这个 bug 根本不存在。
//   ② ★★★ **n**：libstdc++ 的 `std::sort` 对**小数组直接走插入排序**（阈值 16），
//      而插入排序恰好是稳定的 ⇒ **n ≤ 16 时这个 bug 是精确的 0**。
//      官方样例 n = 10（而且里面真有一对并列的 99）—— **正好放过**。
//
// ⇒ 这是本书「小数据本身就是覆盖能力」（第 6 章 P8218）那条经验的一个**干净反例**：
//   这个 bug 只在数据**大**的时候才现形。两条经验都对，主语不一样。
//
// 修法有三种，随便挑一种：① 排 `pair` 用默认比较（正解那样）；
//   ② 比较器写全 `x.t != y.t ? x.t < y.t : x.id < y.id`；③ 换 `stable_sort`。

#include <bits/stdc++.h>
using namespace std;

struct P { int t, id; };

int main() {
    int n;
    if (!(cin >> n)) return 0;

    vector<P> a(n);
    for (int i = 0; i < n; i++) { cin >> a[i].t; a[i].id = i + 1; }

    sort(a.begin(), a.end(), [](const P& x, const P& y) { return x.t < y.t; });   // ← 只比时间

    long long total = 0;
    for (int i = 0; i < n; i++) total += (long long)(n - 1 - i) * a[i].t;

    for (int i = 0; i < n; i++) printf("%d%c", a[i].id, i + 1 == n ? '\n' : ' ');
    printf("%.2f\n", (double)total / n);
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

两个人时间一样时，比较函数说「不分先后」，而 std::sort 不保证保持原来的顺序 （它不是「稳定排序」），编号大的可能被排到前面去。官方样例测不出来，交上去才错。

怎么改

要么排 pair；要么比较函数里加上「时间相同就比编号」；要么换成 stable_sort（稳定排序，相同的元素保持原来的先后）。

深入：这个错多久出现一次（以及那条 16 / 17 的线）

主语一：值域（n 固定 1000，只改 t 的上限）

`t` 的上限	5	100	10 000	10⁶（顶格）
输入里有并列的轮数	300	300	300	104
只比时间那版错的轮数	300	300	300	56

有并列还不够，并列的那两个人还得真的被 sort 换了位置才会错，所以 104 轮里只错了 56 轮。

主语二：n（值域固定为 5，保证每一轮都有并列）

`n`	4	8	16	17	20	32	100	1000
错的轮数（300 轮）	0	0	0	300	300	300	300	300

n ≤ 16 一次都不错，n = 17 起每次都错。原因在标准库里： libstdc++ 的 std::sort 对长度 ≤ 16 的数组直接用插入排序，而插入排序恰好是稳定的。

    n <= 16   编号仍然是 1 2 3 ... n     <- 插入排序，稳定
    n == 17   17 个位置全部错位           <- 换成快速排序的那一刻

⚠ 这是实现细节，换个编译器可能是别的数 —— 所以要量，不要背。这也说明：自己造小数据测这个 bug，n 太小反而测不出来。（P8218 那页的 bug 正好相反，只有小数据才抓得到 ⇒ 数据规模两头都要试。）

3坑二：总等待时间要用 long long

p1223Int.cpp错法二：总等待用 int

// P1223 错法二：总等待时间用 `int`
//
// 顶格 `n = 1000`、`t = 10⁶`：总等待最大 `10⁶ × 1000 × 999 / 2 ≈ 5.0 × 10¹¹`，
// 而 `int` 只到 2 147 483 647 —— 差了两百多倍。
//
// ★ 而这一条正是第 19 章正文第 ⑦ 步那个警告框说的事，那儿写着
//   「**对拍永远不会告诉你这件事** …… 这只能靠脑子」。
//   ⚠ **在这道题上那句话不成立**（页面第 ⑤ 步实测）：那句话的隐含前提是
//   「参照物是暴力」（第 11 章 P1908 已经把这个主语点出来了）——
//   而这道题的参照物**就是正解本身，只换了一个类型**，顶格随便跑。
//
// ⇒ 顶格档（n = 1000, t ≤ 10⁶）对拍，它**每一轮都被抓**。
//   ⚠ 官方样例（n = 10，总等待 2919）当然放过它。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;

    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++) { cin >> a[i].first; a[i].second = i + 1; }
    sort(a.begin(), a.end());

    int total = 0;                                   // ← 这里
    for (int i = 0; i < n; i++) total += (n - 1 - i) * a[i].first;

    for (int i = 0; i < n; i++) printf("%d%c", a[i].second, i + 1 == n ? '\n' : ' ');
    printf("%.2f\n", (double)total / n);
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

先算一下，别急着测。 最坏的情况是每个人都接 10⁶：

    总等待 = 10⁶ × n(n-1)/2
    n = 66   2 145 000 000  <  2^31 = 2 147 483 648   还装得下
    n = 67   2 211 000 000  >= 2^31                    装不下了
    n = 1000（顶格）  499 500 000 000                  超了 232 倍

int 最大只到约 2.1 × 10⁹，所以总等待必须用 long long。

记住这个动作

看到「很多个数乘起来 / 加起来」，先拿题面的最大值乘一遍，再决定用 int 还是 long long。这只要十秒钟，比任何测试都可靠。

深入：随机数据要到 n = 130 才全错，以及正文的一处订正

`n`	8	50	65	66	100	1000
`int` 版错的轮数（300 轮，`t ≤ 10⁶` 随机）	0	0	0	0	1	300

随机数据下它第一次出错在 n = 100，要到 n = 130 才 300 轮全错 —— 比算出来的 67 晚。原因是排序把大系数配给了小时间，随机数据的总等待只有「全部顶格」的三分之一：

    E[总等待] = Σ (n-1-i) · (i+1)/(n+1) · T = T · n(n-1)/6
    全部顶格   =                             T · n(n-1)/2

`n`	随机数据的平均总等待	全部顶格	比值
100	1 651 417 770	4 950 000 000	3.00
1000	166 360 035 296	499 500 000 000	3.00

⇒ 「数据范围顶格」（n = 1000 随机）和「真正的最坏」（每个 t 都是 10⁶）差 3 倍（第 4 章 P1731 那页也遇到过「顶格不等于最坏」）。

顺带订正第 19 章正文的一句话：第 ⑦ 步原来写「对拍永远不会告诉你溢出」。那只在参照物是 n! 全排列暴力、只能跑 n ≤ 8 时成立；查溢出其实拿同一份算法的 long long 版当参照物就够了，想开多大开多大 —— 这一页顶格对拍 int 版被抓 300 / 300。正文那句已经改了（第 11 章 P1908 那页是同一个道理）。

4坑三、坑四：最后一行的平均值

p1223Self.cpp错法三：把自己的接水时间也算进等待

// P1223 错法三：把「自己的接水时间」也算进等待
//
// 题面特意写了一句：「**一个人的等待时间不包括他的接水时间**。」
// 这句提醒按第 12 章那套分法是**命门**（不是情报、也不是噪声）：
//   照着「等待 = 轮到我之前的全部时间 + 我自己接水」写，系数就从 `n-1-i` 变成 `n-i`，
//   答案每一组都会多出 `sum(t) / n`。
//
// ★ 它错得非常显眼 —— **官方样例当场就挡住了**（532.00 vs 291.90）。
//   ⇒ 和上面两个错法凑成这一页的一条观察：
//     **官方样例挡住的都是「每一组都错」的，放过的都是「偶尔才错」的。**
//     这不是运气，几乎是必然：样例只有一组，它天生就是一个「一测就死」的过滤器。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;

    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++) { cin >> a[i].first; a[i].second = i + 1; }
    sort(a.begin(), a.end());

    long long total = 0;
    for (int i = 0; i < n; i++) total += (long long)(n - i) * a[i].first;   // ← n-i，多算了自己

    for (int i = 0; i < n; i++) printf("%d%c", a[i].second, i + 1 == n ? '\n' : ' ');
    printf("%.2f\n", (double)total / n);
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

题面特意写了「一个人的等待时间不包括他的接水时间」。把自己的接水时间也算进去，每个人的系数就从 n-1-i 变成 n-i，答案每一组都会偏大。

p1223Div.cpp错法四：平均值用整数除法

// P1223 错法四：平均值用**整数除法**
//
// `total / n` 先把小数截掉了，再交给 `%.2f` —— 打出来永远是 `xxx.00`。
// 官方样例：2919 / 10 = 291 ⇒ `291.00`，而答案是 `291.90`。**样例当场挡住。**
//
// ★ 留着它是为了凑齐这一页那张「样例挡不挡得住」的表：
//   四个错法里，样例挡住的两个都是「每一组都错」的，放过的两个都是「偶尔才错」的。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;

    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++) { cin >> a[i].first; a[i].second = i + 1; }
    sort(a.begin(), a.end());

    long long total = 0;
    for (int i = 0; i < n; i++) total += (long long)(n - 1 - i) * a[i].first;

    for (int i = 0; i < n; i++) printf("%d%c", a[i].second, i + 1 == n ? '\n' : ' ');
    printf("%.2f\n", (double)(total / n));      // ← 括号位置：整数除完才转 double
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

(double)(total / n) —— 括号位置错了：先做整数除法把小数截掉，再转成 double 已经晚了，打出来永远是 xxx.00。要写 (double)total / n。

四个错法在官方样例上：

错法	官方样例	挡住了吗
比较器只比时间	`291.90`	没挡住
总等待用 `int`	`291.90`	没挡住
多算自己的接水时间	`532.00`	挡住了
平均值整数除法	`291.00`	挡住了

样例只有一组，挡得住的是「每组数据都会错」的写法；「偶尔才错」的两个顺利通过。 ⇒ 样例过了，只说明没有犯最明显的错。 另外两个坑要靠读题和估算自己想到。

5正解

p1223.cpp★ 这一版就能 AC

// P1223 排队接水 —— ★ 这一版就能 AC
//
// ★★★ 这道题的算法，第 19 章正文已经**证完了**：
//   按接水时间从小到大排，交换论证两行推导（见 /ch/19-greedy-sorting/ 第 ⑤ 步）。
//   ⇒ 写这道题的算法部分只要三分钟：`sort` 一句，累加一句。
//
// 而它能不能 AC，全押在**三件和贪心毫无关系的事**上（页面第 ③ ④ ⑤ 步各量了一件）：
//   ① 要输出的是**编号**不是时间 —— 所以排的是 `(时间, 编号)` 这个 pair；
//   ② 题面那句「**接水时间相同，编号更小的排在前面**」是**命门**：
//      比较器只比时间的话，`std::sort` 不保证并列元素的相对顺序（它不是稳定排序）；
//      ⚠ 而这个 bug **在 n ≤ 16 时抓不到**（libstdc++ 小数组直接走插入排序），
//        官方样例 n = 10 —— 正好放过；
//   ③ 总等待时间要开 **long long**：顶格 `n = 1000`、`t = 10⁶` 时约 5 × 10¹¹。
//
// ★ 第 ② 条这里是**白拿**的：`pair` 的默认比较就是「先比 first，再比 second」，
//   而我们把编号放在 second —— 题面要的 tie-break 一个字都不用写。
//
// 输出：第一行是排队顺序（编号），第二行是平均等待时间，保留两位小数。
//   ⚠ 平均要用**浮点**除（`(double)total / n`），整数除法当场就错（样例挡得住这一个）。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;

    vector<pair<int, int>> a(n);             // (接水时间, 编号)
    for (int i = 0; i < n; i++) {
        cin >> a[i].first;
        a[i].second = i + 1;
    }
    sort(a.begin(), a.end());                // ★ 默认比较 = 先按时间，时间相同按编号

    long long total = 0;                     // ★ 顶格约 5e11，int 装不下
    for (int i = 0; i < n; i++)
        total += (long long)(n - 1 - i) * a[i].first;   // 排第 i+1 位的人，被后面 n-1-i 个人等

    for (int i = 0; i < n; i++)
        printf("%d%c", a[i].second, i + 1 == n ? '\n' : ' ');
    printf("%.2f\n", (double)total / n);
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

深入：度量程序和生成器（上面那些表格是用它们跑出来的）

p1223Count.cpp度量程序

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

// P1223 的度量程序 —— 这一页所有数字都出自这一份。
//
// `./p1223Count`      人看的版本
// `./p1223Count csv`  一行一项，给 scripts/check-viz.mjs 写断言用
//
// 六段：
//   ① ★ 升序真的最优吗：小 n 全排列穷举，和「排序后累加」逐组比；
//   ② ★★ `int` 的**精确分界**：全 t = 10⁶ 时，最小的会溢出的 n（算术题，不用测）；
//   ③ ★★★ `std::sort` 的**稳定性分界**：全部元素相等时，最小的会打乱编号顺序的 n
//      （libstdc++ 小数组走插入排序 —— 这是**实现细节**，所以要量不要背）；
//   ④ ★★★ 「只比时间」那个 bug 的 **n 曲线**（值域固定为 5，保证有并列 ⇒ 只剩 n 这一个变量）；
//   ⑤ ★★ 它的**值域曲线**（n 固定 1000）—— 抓获率的第一个主语是「有没有并列」；
//   ⑥ ★★ `int` 版的 n 曲线，以及**随机数据**下它开始出错的最小 n
//      （⚠ 和第 ② 段那条算出来的线**不是一回事**：一个是最坏，一个是随机）。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

static bool CSV = false;
static void row(const char* key, const vector<ll>& v) {
    if (!CSV) return;
    printf("%s", key);
    for (ll x : v) printf(",%lld", x);
    printf("\n");
}

struct P { int t, id; };

/** 正解：排 (时间, 编号)，返回排好的编号序列 + 总等待 */
static void solve(const vector<int>& t, vector<int>& order, ll& total) {
    int n = t.size();
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++) a[i] = {t[i], i + 1};
    sort(a.begin(), a.end());
    order.clear();
    total = 0;
    for (int i = 0; i < n; i++) {
        order.push_back(a[i].second);
        total += (ll)(n - 1 - i) * a[i].first;
    }
}

/** 错法一：比较器只比时间 */
static void solveCmp(const vector<int>& t, vector<int>& order) {
    int n = t.size();
    vector<P> a(n);
    for (int i = 0; i < n; i++) a[i] = {t[i], i + 1};
    sort(a.begin(), a.end(), [](const P& x, const P& y) { return x.t < y.t; });
    order.clear();
    for (int i = 0; i < n; i++) order.push_back(a[i].id);
}

/** 错法二：总等待用 int 累加（这里真的用 int 加一遍，好把溢出行为原样复现） */
static int solveInt(const vector<int>& t) {
    int n = t.size();
    vector<int> s = t;
    sort(s.begin(), s.end());
    int total = 0;
    for (int i = 0; i < n; i++) total += (n - 1 - i) * s[i];
    return total;
}

static vector<int> gen(mt19937& rng, int n, int hi) {
    vector<int> t(n);
    for (int i = 0; i < n; i++) t[i] = rng() % (unsigned)hi + 1;
    return t;
}
static bool hasDup(vector<int> t) {
    sort(t.begin(), t.end());
    return adjacent_find(t.begin(), t.end()) != t.end();
}

int main(int argc, char** argv) {
    CSV = argc > 1 && string(argv[1]) == "csv";

    /* ① 升序真的最优吗 —— 小 n 全排列穷举 */
    {
        mt19937 rng(20260829u);
        int groups = 0, bad = 0;
        for (int n = 1; n <= 8; n++) {
            for (int rep = 0; rep < 40; rep++, groups++) {
                vector<int> t = gen(rng, n, 20);
                vector<int> idx(n);
                iota(idx.begin(), idx.end(), 0);
                ll best = LLONG_MAX;
                do {
                    ll s = 0;
                    for (int i = 0; i < n; i++) s += (ll)(n - 1 - i) * t[idx[i]];
                    best = min(best, s);
                } while (next_permutation(idx.begin(), idx.end()));
                vector<int> ord; ll total;
                solve(t, ord, total);
                if (total != best) bad++;
            }
        }
        if (!CSV) printf("① 全排列穷举 %d 组（n <= 8）：排序贪心和最优解不一致 %d 组\n", groups, bad);
        row("opt", {groups, bad});
    }

    /* ② int 的精确分界：全 t = 10^6 时最小的溢出 n */
    {
        const ll T = 1000000;
        int lim = -1;
        for (int n = 1; n <= 1000; n++) {
            ll total = T * n * (n - 1) / 2;         // 全部相等时的总等待
            if (total > 2147483647LL) { lim = n; break; }
        }
        ll below = T * (ll)(lim - 1) * (lim - 2) / 2, at = T * (ll)lim * (lim - 1) / 2;
        ll top = T * 1000LL * 999LL / 2;
        if (!CSV) printf("② 全 t = 10^6：n = %d 总等待 %lld（< 2^31），n = %d 是 %lld（>= 2^31）；顶格 n = 1000 是 %lld\n",
                         lim - 1, below, lim, at, top);
        row("bound", {lim, below, at, top});
    }

    /* ③ std::sort 的稳定性分界：全部元素相等，最小的会打乱编号的 n */
    {
        int lim = -1;
        for (int n = 1; n <= 200 && lim < 0; n++) {
            vector<int> t(n, 7);
            vector<int> ord;
            solveCmp(t, ord);
            for (int i = 0; i < n; i++) if (ord[i] != i + 1) { lim = n; break; }
        }
        vector<int> t17(lim, 7), ord17;
        solveCmp(t17, ord17);
        int moved = 0;
        for (int i = 0; i < lim; i++) if (ord17[i] != i + 1) moved++;
        if (!CSV) printf("③ 全部相等：n <= %d 时 std::sort 保持编号升序，n = %d 起被打乱（那一档有 %d 个位置错位）\n",
                         lim - 1, lim, moved);
        row("stable", {lim, moved});
    }

    /* ④ 「只比时间」的 n 曲线（值域固定 5 ⇒ 必有并列） */
    {
        const int NS[] = {4, 8, 16, 17, 20, 32, 100, 1000};
        vector<ll> out;
        for (int n : NS) {
            mt19937 rng(n * 7919u + 11u);
            int bad = 0;
            for (int r = 0; r < 300; r++) {
                vector<int> t = gen(rng, n, 5);
                vector<int> a, b; ll total;
                solve(t, a, total);
                solveCmp(t, b);
                if (a != b) bad++;
            }
            out.push_back(bad);
            if (!CSV) printf("④ n = %4d（t <= 5）：只比时间那版错 %d / 300\n", n, bad);
        }
        row("cmpN", out);
    }

    /* ⑤ 它的值域曲线（n 固定 1000） */
    {
        const int HIS[] = {5, 100, 10000, 1000000};
        vector<ll> out;
        for (int hi : HIS) {
            mt19937 rng(hi * 2654435761u + 3u);
            int bad = 0, dup = 0;
            for (int r = 0; r < 300; r++) {
                vector<int> t = gen(rng, 1000, hi);
                if (hasDup(t)) dup++;
                vector<int> a, b; ll total;
                solve(t, a, total);
                solveCmp(t, b);
                if (a != b) bad++;
            }
            out.push_back(bad); out.push_back(dup);
            if (!CSV) printf("⑤ n = 1000，t <= %7d：只比时间那版错 %d / 300，其中含并列的输入 %d / 300\n", hi, bad, dup);
        }
        row("cmpHi", out);
    }

    /* ⑥ int 版的 n 曲线 + 随机数据下的实际分界 */
    {
        const int NS[] = {8, 50, 65, 66, 100, 1000};
        vector<ll> out;
        for (int n : NS) {
            mt19937 rng(n * 40503u + 7u);
            int bad = 0;
            for (int r = 0; r < 300; r++) {
                vector<int> t = gen(rng, n, 1000000);
                vector<int> ord; ll total;
                solve(t, ord, total);
                if ((ll)solveInt(t) != total) bad++;
            }
            out.push_back(bad);
            if (!CSV) printf("⑥ n = %4d（t <= 10^6）：int 版错 %d / 300\n", n, bad);
        }
        int firstAll = -1, firstAny = -1;
        for (int n = 2; n <= 300; n++) {
            mt19937 rng(n * 40503u + 7u);
            int bad = 0;
            for (int r = 0; r < 300; r++) {
                vector<int> t = gen(rng, n, 1000000);
                vector<int> ord; ll total;
                solve(t, ord, total);
                if ((ll)solveInt(t) != total) bad++;
            }
            if (bad > 0 && firstAny < 0) firstAny = n;
            if (bad == 300) { firstAll = n; break; }
        }
        if (!CSV) printf("⑥ 随机 t <= 10^6：int 版第一次出错在 n = %d，到 n = %d 起 300 轮全错\n", firstAny, firstAll);
        out.push_back(firstAny); out.push_back(firstAll);
        row("intN", out);
    }

    /* ⑦ ★★★ 为什么随机数据的溢出线比算出来的那条晚一倍：**排序本身把总等待压小了三倍**
       升序排好之后，大系数 `n-1-i` 配到的是**小**的那些 t。
       随机均匀的 t 排序后 `E[s_i] ≈ (i+1)/(n+1)·T`，代进去：
         E[总等待] = Σ (n-1-i)·(i+1)/(n+1)·T = T·n(n-1)/6
       而全部 t 都顶格时是 `T·n(n-1)/2` —— **正好 3 倍**。这一段实测那个 3。 */
    {
        const int NS2[] = {100, 1000};
        vector<ll> out;
        for (int n : NS2) {
            mt19937 rng(n * 99991u + 5u);
            long double sum = 0;
            for (int r = 0; r < 300; r++) {
                vector<int> t = gen(rng, n, 1000000);
                vector<int> ord; ll total;
                solve(t, ord, total);
                sum += (long double)total;
            }
            ll avg = (ll)(sum / 300 + 0.5L);
            ll worst = 1000000LL * n * (n - 1) / 2;
            ll ratio100 = (ll)((long double)worst / (long double)avg * 100 + 0.5L);
            out.push_back(avg); out.push_back(worst); out.push_back(ratio100);
            if (!CSV) printf("⑦ n = %4d：随机数据平均总等待 %lld，全部顶格 %lld，比值 %.2f\n",
                             n, avg, worst, ratio100 / 100.0);
        }
        row("ratio", out);
    }
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

p1223Gen.cpp数据生成器

// P1223 对拍生成器：`./p1223Gen <seed> [n] [t 的上限]`
//   默认 `n = 1000`、`t ≤ 10⁶` —— ★ **就是题面的顶格档**。
//
// ★ 默认值写成顶格是有意的（本书第 53 条经验：生成器的默认档位要写成最终档）。
//   这道题的两个隐蔽 bug 恰好各要一头：
//     · `int` 溢出要 **n 和 t 都大**（顶格必炸，页面第 ⑤ 步算得出精确分界 n = 66）；
//     · 排序不稳定要 **n > 16**（小数组走插入排序）**且值域小到有并列**。
//   ⇒ 顺手写的 `n ≤ 10`、`t ≤ 100` 那种生成器，**两个都是精确的 0**。
//
// 值域这个旋钮单独拎出来（页面第 ④ 步那张表就是拧它拧出来的）：
//   `t` 的上限越小，并列越多，「只比时间」那个 bug 越容易现形。

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1;
    int n = argc > 2 ? atoi(argv[2]) : 1000;
    int hi = argc > 3 ? atoi(argv[3]) : 1000000;
    n = max(1, min(1000, n));
    hi = max(1, min(1000000, hi));

    mt19937 rng(seed * 2654435761u + 12345u);
    printf("%d\n", n);
    for (int i = 0; i < n; i++)
        printf("%u%c", (unsigned)(rng() % (unsigned)hi) + 1, i + 1 == n ? '\n' : ' ');
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

p1223Gen 不带参数就是题面顶格（n = 1000、t ≤ 10⁶）： int 溢出要 n 和 t 都大，排序不稳定要 n > 16 且值域小到有并列 —— 顺手写的 n ≤ 10、t ≤ 100 那种生成器，两个坑都测不出来。

「样例只挡得住每组都错的写法」这条规律，P1074、P2324、 P1032、P1516 那几页也都量过。

6一页纸


算法	按接水时间从小到大排（第 19 章已证明），`sort` 一句
能 AC 的	`p1223.cpp`；四个错法都只差一行
坑一	输出的是编号 ⇒ 排 `(时间, 编号)` 的 `pair`，「时间相同编号小的在前」自动满足
坑二	比较函数只比时间 ⇒ `std::sort` 不稳定，相同时间的人顺序会乱
坑三	总等待最坏约 5 × 10¹¹ ⇒ `long long`
坑四	等待不含自己的接水时间；平均值写 `(double)total / n`
样例	只挡住了「每组都错」的两个，另外两个要靠自己想到

洛谷 P1223 排队接水

0题目原文（本地存了一份）

输入

输出

1算法：接水快的排前面

2坑一：输出编号，以及时间相同的人谁在前

3坑二：总等待时间要用 long long

4坑三、坑四：最后一行的平均值

5正解

6一页纸