把每个 K 对应的剩余作业看成一个后缀，预处理后缀和与后缀最小值，就能在线性时间内求出删去最小值后的最大平均分。
OJ: luogu
题目 ID: P4086
难度:普及-
标签:后缀和最小值分数比较思维
日期: 2026-06-21 01:56
题意
给定一串作业分数 a[1..N]。
如果前 K 道题被吃掉，那么只剩下后缀 [K+1, N]。
老师会在这段剩余作业中删去一个最小分，然后对其他题目求平均分。
要求输出所有能让这个平均分最大的 K。
思路
先看最朴素的做法：
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 5;
int n;
int a[MAXN];
bool greater_fraction(long long num1, long long den1, long long num2, long long den2) {
return num1 * den2 > num2 * den1;
}
bool equal_fraction(long long num1, long long den1, long long num2, long long den2) {
return num1 * den2 == num2 * den1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
long long best_num = -1;
long long best_den = 1;
vector<int> answer;
for (int k = 1; k <= n - 2; k++) {
long long sum = 0;
int mn = 1000000000;
// 直接暴力统计剩余题目的总分与最小值。
for (int i = k + 1; i <= n; i++) {
sum += a[i];
mn = min(mn, a[i]);
}
long long current_num = sum - mn;
long long current_den = n - k - 1;
if (best_num == -1 || greater_fraction(current_num, current_den, best_num, best_den)) {
best_num = current_num;
best_den = current_den;
answer.clear();
answer.push_back(k);
} else if (equal_fraction(current_num, current_den, best_num, best_den)) {
answer.push_back(k);
}
}
for (int i = 0; i < (int)answer.size(); i++) {
cout << answer[i] << '\n';
}
return 0;
}brute.cpp 直接枚举每个 K，然后暴力扫描后缀 [K+1, N]：
- 求这段总和
- 求这段最小值
- 算删去最小值后的平均分
这个做法显然正确，但如果每个 K 都重新扫一遍后缀，复杂度会到
优化的关键在于：对每个 K，我们真正关心的只有后缀的两个信息：
- 后缀和
- 后缀最小值
这两个量都可以从右往左预处理。
设：
suffix_sum[i]表示后缀[i, N]的总和suffix_min[i]表示后缀[i, N]的最小值
如果剩余作业从 start 开始，也就是 start = K + 1，那么删去一个最小值后的平均分就是：
因为：
- 原后缀长度是
N - start + 1 - 去掉一个最小值后，剩余题数是
N - start
然后把所有 start = 2..N-1 枚举一遍，找出平均分最大的所有位置即可。
实现时不要用 double 直接比较平均分，使用交叉相乘比较两个分数更稳妥。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 5;
int n;
int a[MAXN];
int suffix_min[MAXN];
long long suffix_sum[MAXN];
// 返回 true 表示 num1 / den1 > num2 / den2
bool greater_fraction(long long num1, long long den1, long long num2, long long den2) {
return num1 * den2 > num2 * den1;
}
// 返回 true 表示 num1 / den1 == num2 / den2
bool equal_fraction(long long num1, long long den1, long long num2, long long den2) {
return num1 * den2 == num2 * den1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
suffix_sum[n] = a[n];
suffix_min[n] = a[n];
for (int i = n - 1; i >= 1; i--) {
suffix_sum[i] = suffix_sum[i + 1] + a[i];
suffix_min[i] = min(suffix_min[i + 1], a[i]);
}
long long best_num = -1;
long long best_den = 1;
vector<int> answer;
for (int start = 2; start <= n - 1; start++) {
// 吃掉前 start-1 题后，剩下的是 [start, n]
// 去掉这一段中的最小值，再对剩下的题求平均分。
long long current_num = suffix_sum[start] - suffix_min[start];
long long current_den = n - start;
if (best_num == -1 || greater_fraction(current_num, current_den, best_num, best_den)) {
best_num = current_num;
best_den = current_den;
answer.clear();
answer.push_back(start - 1);
} else if (equal_fraction(current_num, current_den, best_num, best_den)) {
answer.push_back(start - 1);
}
}
for (int i = 0; i < (int)answer.size(); i++) {
cout << answer[i] << '\n';
}
return 0;
}复杂度
预处理后缀和：
预处理后缀最小值：
枚举所有 K：
总时间复杂度：
空间复杂度：
总结
这题表面上是在枚举被吃掉多少题，实际上是在枚举“从哪里开始看后缀”。
一旦把每个方案统一表示成一个后缀，题目就只剩下两个后缀统计量：
- 后缀和
- 后缀最小值
这也是这道题最核心的建模转换。