题目描述在一所拉丁美洲的高中克林贡语非常受欢迎许多学生开始自学。学校决定开设正式的克林贡语课程但学生们的语言基础不同因此提供了基础与高级两个级别。学校有多个班级每个学生恰好属于一个班级。由于行政和课程冲突不同班级的学生不能参加同一克林贡语课程。同时为了公平基础与高级课程必须覆盖所有班级并且各班级之间的难度应相同。因此每个班级将被分成两组一组学习基础课程另一组学习高级课程。某个组可能没有学生。为了分配级别所有学生参加了一次克林贡语测试分数为000到100010001000之间的整数。学校决定所有分数大于或等于某个阈值TTT的学生进入高级组分数小于TTT的学生进入基础组。学校希望选一个TTT使得所有班级中基础与高级人数之差的绝对值之和最小。定义累计差值为∑i1N∣basici−advancedi∣ \sum_{i1}^{N} |basic_i - advanced_i|i1∑N∣basici−advancedi∣其中basicibasic_ibasici是第iii个班级中分数T TT的人数advancediadvanced_iadvancedi是分数≥T\ge T≥T的人数。输入格式输入包含多个测试用例。每个测试用例的第一行包含一个整数NNN1≤N≤1041 \le N \le 10^41≤N≤104表示班级的数量。接下来有2×N2 \times N2×N行每个班级由两行描述第一行是一个整数KiK_iKi1≤Ki≤1041 \le K_i \le 10^41≤Ki≤104表示该班学生数第二行包含KiK_iKi个整数0≤score≤10000 \le score \le 10000≤score≤1000表示每个学生的分数。所有测试用例的学生总数不超过10510^5105。输入以一行单独的0结束。输出格式对于每个测试用例输出一行一个整数表示最优阈值TTT下累计差值的最小值。样例输入2 2 1 2 2 3 4 2 2 1 4 2 2 3 3 4 1 10 100 1000 3 5 55 555 5 4 16 64 256 1000 1 4 500 500 500 500 0输出2 0 2 4题目分析本题的目标是在所有可能的整数阈值TTT中最小化所有班级内部基础/高级人数差的绝对值之和。分数范围很小0∼10000 \sim 10000∼1000因此TTT只需考虑000到100110011001之间的整数即可T0T0T0时所有学生均为高级T1001T1001T1001时所有学生均为基础。暴力枚举TTT并重新统计每个班级的人数差时间复杂度为O(1001×N×K)O(1001 \times N \times K)O(1001×N×K)显然不可接受。但注意到对于每个班级我们可以预处理出关于阈值TTT的前缀计数pref[t]\textit{pref}[t]pref[t]表示该班级中分数小于ttt的学生人数t∈[0,1001]t \in [0, 1001]t∈[0,1001]。这样给定任意TTT该班级的基础人数就是pref[T]\textit{pref}[T]pref[T]总人数为pref[1001]\textit{pref}[1001]pref[1001]差值为∣2×pref[T]−pref[1001]∣|2 \times \textit{pref}[T] - \textit{pref}[1001]|∣2×pref[T]−pref[1001]∣。于是每个班级对任意TTT的贡献可以O(1)O(1)O(1)得到整体枚举TTT的复杂度降为O(1001×N)O(1001 \times N)O(1001×N)在给定数据范围内完全可行。解题思路步骤概述对每个班级读取学生人数KKK和分数列表。统计分数出现次数cnt[s]\textit{cnt}[s]cnt[s]0≤s≤10000 \le s \le 10000≤s≤1000。计算前缀数组pref[0…1001]\textit{pref}[0 \dots 1001]pref[0…1001]其中pref[0]0\textit{pref}[0] 0pref[0]0pref[t]∑s0t−1cnt[s]\textit{pref}[t] \sum_{s0}^{t-1} \textit{cnt}[s]pref[t]∑s0t−1cnt[s]即分数小于ttt的人数。注意pref[1001]\textit{pref}[1001]pref[1001]即为该班总人数。存储每个班级的pref\textit{pref}pref数组。枚举T0,1,…,1001T 0, 1, \dots, 1001T0,1,…,1001累加所有班级的∣2×pref[T]−pref[1001]∣|2 \times \textit{pref}[T] - \textit{pref}[1001]|∣2×pref[T]−pref[1001]∣记录最小值。输出最小值。正确性说明前缀数组pref[T]\textit{pref}[T]pref[T]精确表示了分数T TT的人数符合基本级别的定义。由于分数只有100110011001种TTT取遍0∼10010 \sim 10010∼1001即可覆盖所有可能的分割点包括全部高级和全部基础。枚举所有TTT并取最小必然得到全局最优解。复杂度分析时间每个班级统计分数O(K)O(K)O(K)计算前缀O(1001)O(1001)O(1001)枚举TTT时每个班级O(1)O(1)O(1)总计O(∑K1001×N)O(\sum K 1001 \times N)O(∑K1001×N)。其中∑K≤105\sum K \le 10^5∑K≤105N≤104N \le 10^4N≤104故总时间在10710^7107量级可以接受。空间存储每个班级的pref\textit{pref}pref数组共N×1002N \times 1002N×1002个整数最大约104×1002≈10710^4 \times 1002 \approx 10^7104×1002≈107也可接受若内存紧张也可边枚举边计算但本题空间足够。代码实现// Klingon Levels// UVa ID: 12196// Verdict: Accepted// Submission Date: 2026-06-20// UVa Run Time: 0.150s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intN;while(cinNN!0){vectorvectorintprefs;// 每个班级的前缀计数数组prefs.reserve(N);for(inti0;iN;i){intK;cinK;vectorintcnt(1001,0);// 分数 0..1000for(intj0;jK;j){intscore;cinscore;cnt[score];}vectorintpref(1002,0);// pref[t] 分数 t 的人数for(ints0;s1000;s)pref[s1]pref[s]cnt[s];prefs.push_back(move(pref));}intbestINT_MAX;for(intT0;T1001;T){intsum0;for(constautopref:prefs){intbasicpref[T];// 分数 T 的人数inttotalpref[1001];// 班级总人数intdiffabs(2*basic-total);sumdiff;}if(sumbest)bestsum;}coutbest\n;}return0;}总结本题的关键在于利用分数范围小的特点通过预处理每个班级的前缀计数将阈值枚举的复杂度降低到可接受范围。这种“以空间换时间”的思路在数据范围固定且较小时非常有效。同时注意TTT的取值必须覆盖所有可能的分界点包括边界情况全部基础或全部高级。代码实现简洁清晰易于扩展至类似的统计问题。 UVa 12196 Klingon Levels
题目描述在一所拉丁美洲的高中克林贡语非常受欢迎许多学生开始自学。学校决定开设正式的克林贡语课程但学生们的语言基础不同因此提供了基础与高级两个级别。学校有多个班级每个学生恰好属于一个班级。由于行政和课程冲突不同班级的学生不能参加同一克林贡语课程。同时为了公平基础与高级课程必须覆盖所有班级并且各班级之间的难度应相同。因此每个班级将被分成两组一组学习基础课程另一组学习高级课程。某个组可能没有学生。为了分配级别所有学生参加了一次克林贡语测试分数为000到100010001000之间的整数。学校决定所有分数大于或等于某个阈值TTT的学生进入高级组分数小于TTT的学生进入基础组。学校希望选一个TTT使得所有班级中基础与高级人数之差的绝对值之和最小。定义累计差值为∑i1N∣basici−advancedi∣ \sum_{i1}^{N} |basic_i - advanced_i|i1∑N∣basici−advancedi∣其中basicibasic_ibasici是第iii个班级中分数T TT的人数advancediadvanced_iadvancedi是分数≥T\ge T≥T的人数。输入格式输入包含多个测试用例。每个测试用例的第一行包含一个整数NNN1≤N≤1041 \le N \le 10^41≤N≤104表示班级的数量。接下来有2×N2 \times N2×N行每个班级由两行描述第一行是一个整数KiK_iKi1≤Ki≤1041 \le K_i \le 10^41≤Ki≤104表示该班学生数第二行包含KiK_iKi个整数0≤score≤10000 \le score \le 10000≤score≤1000表示每个学生的分数。所有测试用例的学生总数不超过10510^5105。输入以一行单独的0结束。输出格式对于每个测试用例输出一行一个整数表示最优阈值TTT下累计差值的最小值。样例输入2 2 1 2 2 3 4 2 2 1 4 2 2 3 3 4 1 10 100 1000 3 5 55 555 5 4 16 64 256 1000 1 4 500 500 500 500 0输出2 0 2 4题目分析本题的目标是在所有可能的整数阈值TTT中最小化所有班级内部基础/高级人数差的绝对值之和。分数范围很小0∼10000 \sim 10000∼1000因此TTT只需考虑000到100110011001之间的整数即可T0T0T0时所有学生均为高级T1001T1001T1001时所有学生均为基础。暴力枚举TTT并重新统计每个班级的人数差时间复杂度为O(1001×N×K)O(1001 \times N \times K)O(1001×N×K)显然不可接受。但注意到对于每个班级我们可以预处理出关于阈值TTT的前缀计数pref[t]\textit{pref}[t]pref[t]表示该班级中分数小于ttt的学生人数t∈[0,1001]t \in [0, 1001]t∈[0,1001]。这样给定任意TTT该班级的基础人数就是pref[T]\textit{pref}[T]pref[T]总人数为pref[1001]\textit{pref}[1001]pref[1001]差值为∣2×pref[T]−pref[1001]∣|2 \times \textit{pref}[T] - \textit{pref}[1001]|∣2×pref[T]−pref[1001]∣。于是每个班级对任意TTT的贡献可以O(1)O(1)O(1)得到整体枚举TTT的复杂度降为O(1001×N)O(1001 \times N)O(1001×N)在给定数据范围内完全可行。解题思路步骤概述对每个班级读取学生人数KKK和分数列表。统计分数出现次数cnt[s]\textit{cnt}[s]cnt[s]0≤s≤10000 \le s \le 10000≤s≤1000。计算前缀数组pref[0…1001]\textit{pref}[0 \dots 1001]pref[0…1001]其中pref[0]0\textit{pref}[0] 0pref[0]0pref[t]∑s0t−1cnt[s]\textit{pref}[t] \sum_{s0}^{t-1} \textit{cnt}[s]pref[t]∑s0t−1cnt[s]即分数小于ttt的人数。注意pref[1001]\textit{pref}[1001]pref[1001]即为该班总人数。存储每个班级的pref\textit{pref}pref数组。枚举T0,1,…,1001T 0, 1, \dots, 1001T0,1,…,1001累加所有班级的∣2×pref[T]−pref[1001]∣|2 \times \textit{pref}[T] - \textit{pref}[1001]|∣2×pref[T]−pref[1001]∣记录最小值。输出最小值。正确性说明前缀数组pref[T]\textit{pref}[T]pref[T]精确表示了分数T TT的人数符合基本级别的定义。由于分数只有100110011001种TTT取遍0∼10010 \sim 10010∼1001即可覆盖所有可能的分割点包括全部高级和全部基础。枚举所有TTT并取最小必然得到全局最优解。复杂度分析时间每个班级统计分数O(K)O(K)O(K)计算前缀O(1001)O(1001)O(1001)枚举TTT时每个班级O(1)O(1)O(1)总计O(∑K1001×N)O(\sum K 1001 \times N)O(∑K1001×N)。其中∑K≤105\sum K \le 10^5∑K≤105N≤104N \le 10^4N≤104故总时间在10710^7107量级可以接受。空间存储每个班级的pref\textit{pref}pref数组共N×1002N \times 1002N×1002个整数最大约104×1002≈10710^4 \times 1002 \approx 10^7104×1002≈107也可接受若内存紧张也可边枚举边计算但本题空间足够。代码实现// Klingon Levels// UVa ID: 12196// Verdict: Accepted// Submission Date: 2026-06-20// UVa Run Time: 0.150s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intN;while(cinNN!0){vectorvectorintprefs;// 每个班级的前缀计数数组prefs.reserve(N);for(inti0;iN;i){intK;cinK;vectorintcnt(1001,0);// 分数 0..1000for(intj0;jK;j){intscore;cinscore;cnt[score];}vectorintpref(1002,0);// pref[t] 分数 t 的人数for(ints0;s1000;s)pref[s1]pref[s]cnt[s];prefs.push_back(move(pref));}intbestINT_MAX;for(intT0;T1001;T){intsum0;for(constautopref:prefs){intbasicpref[T];// 分数 T 的人数inttotalpref[1001];// 班级总人数intdiffabs(2*basic-total);sumdiff;}if(sumbest)bestsum;}coutbest\n;}return0;}总结本题的关键在于利用分数范围小的特点通过预处理每个班级的前缀计数将阈值枚举的复杂度降低到可接受范围。这种“以空间换时间”的思路在数据范围固定且较小时非常有效。同时注意TTT的取值必须覆盖所有可能的分界点包括边界情况全部基础或全部高级。代码实现简洁清晰易于扩展至类似的统计问题。