思路与算法

先求Average与前缀平方偏差S_i。令f[k][i]表示前i人恰好安排在前k教室中的最小评价指数。末班从j+1到i时，转移为G_kS_i+min(f[k-1][j]-G_kS_j)，窗口i-B≤j≤i-A。用单调队列维护窗口最小值；相同值保留更大的j，使末班人数更少。枚举班级数k，按评价指数、班级数、末班人数的顺序决胜。

正确性说明

任何合法方案的末班人数都在[A,B]，去掉末班后恰是前k-1教室的合法子问题，故递推完整。平方偏差前缀和使末班代价等于G_k(S_i-S_j)，与窗口式相同，G可负也不改变代数等式。单调队列只删去过期或被更晚且不劣候选支配的下标，不改变窗口最小值。相同转移值时更大j使末班更小；班级数按递增处理，同目标不覆盖前面的较小班级数，因此三级决胜正确。

复杂度

每一k扫描M个位置，候选各入队出队至多一次，初始化和读入O(M+N)，各行初始化O(M)，总O(MN)时间、O(M+N)空间。多组按各自MN求和。

易错点

保持输入学生顺序，使用前k教室，不能将G排序。Average先求总和再整除。G可为负，不能贪心少开教室；不可达状态不入队。平方和与评价指数用64位，无解输出-1 0 0。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int m, n, A, B;
        cin >> m >> n >> A >> B;
        vector<long long> x(m + 1), g(n + 1), s(m + 1);
        long long avg = 0;
        for (int i = 1; i <= m; i++) {
            cin >> x[i];
            avg += x[i];
        }
        avg /= m;
        for (int i = 1; i <= n; i++)
            cin >> g[i];
        for (int i = 1; i <= m; i++)
            s[i] = s[i - 1] + (x[i] - avg) * (x[i] - avg);
        const long long INF = 4000000000000000000LL;
        vector<long long> old(m + 1, INF), cur(m + 1);
        old[0] = 0;
        long long ans = INF;
        int classes = 0, last = 0;
        for (int k = 1; k <= min(n, m / A); k++) {
            fill(cur.begin(), cur.end(), INF);
            deque<int> q;
            auto value = [&](int j) {
                return old[j] - g[k] * s[j];
            };
            for (int i = 1; i <= m; i++) {
                int j = i - A;
                if (j >= 0 && old[j] != INF) {
                    while (!q.empty() && value(q.back()) >= value(j))
                        q.pop_back();
                    q.push_back(j);
                }
                while (!q.empty() && q.front() < i - B)
                    q.pop_front();
                if (!q.empty()) {
                    cur[i] = value(q.front()) + g[k] * s[i];
                    if (i == m && cur[i] < ans) {
                        ans = cur[i];
                        classes = k;
                        last = i - q.front();
                    }
                }
            }
            old.swap(cur);
        }
        if (ans == INF)
            cout << "-1 0 0\n";
        else
            cout << ans << ' ' << classes << ' ' << last << '\n';
    }
}