五、 标准题解代码 (C++14)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

struct Point {
    int id;
    ll val;
};

// 计算在该轴上每个点到其他所有点的距离之和
void calculate_dist(int N, vector<Point>& pts, vector<ll>& result_dist) {
    // 按坐标值排序
    sort(pts.begin(), pts.end(), [](Point a, Point b) {
        return a.val < b.val;
    });

    vector<ll> prefix_sum(N + 1, 0);
    for (int i = 0; i < N; ++i) {
        prefix_sum[i + 1] = prefix_sum[i] + pts[i].val;
    }

    for (int i = 0; i < N; ++i) {
        ll k = i + 1; // 当前是第k个点(1-based)
        ll left_dist = (k - 1) * pts[i].val - prefix_sum[i];
        ll right_dist = (prefix_sum[N] - prefix_sum[k]) - (N - k) * pts[i].val;
        // 将计算结果存回该点对应的原始编号位置
        result_dist[pts[i].id] += (left_dist + right_dist);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N;
    cin >> N;

    vector<Point> x_pts(N), y_pts(N);
    for (int i = 0; i < N; ++i) {
        ll x, y;
        cin >> x >> y;
        x_pts[i] = {i + 1, x};
        y_pts[i] = {i + 1, y};
    }

    // 存储每个编号学校的总距离和，初始化为0
    vector<ll> total_dist(N + 1, 0);

    // 分别处理 X 轴和 Y 轴
    calculate_dist(N, x_pts, total_dist);
    calculate_dist(N, y_pts, total_dist);

    ll min_sum = -1;
    int best_id = -1;

    for (int i = 1; i <= N; ++i) {
        if (min_sum == -1 || total_dist[i] < min_sum) {
            min_sum = total_dist[i];
            best_id = i;
        } else if (total_dist[i] == min_sum) {
            if (best_id == -1 || i < best_id) {
                best_id = i;
            }
        }
    }

    cout << best_id << " " << min_sum << endl;

    return 0;
}

这是一个完整的 C++ 数据生成器，用于生成题目“最佳校区选址”的测试数据。

它包含了一个基于 $O(N \log N)$ 算法（前缀和优化）的标准题解，能够秒出 $N=10^5$ 级别的数据。

数据生成器代码 (Generator.cpp)

请将以下代码保存为 generator.cpp，编译并运行。它会在当前目录下生成 1.in/1.out 到 10.in/10.out。

/**
 * 题目：最佳校区选址 (Optimal Campus Selection)
 * 功能：生成测试数据 1.in ~ 10.in 及对应的 1.out ~ 10.out
 * 覆盖：
 * 1. 样例数据
 * 2. 小规模随机
 * 3. 一维分布 (只有X变化)
 * 4. 一维分布 (只有Y变化)
 * 5. 密集重叠点 (重复坐标)
 * 6. 极限坐标值 (接近 +/- 10^9)
 * 7. 中等规模随机
 * 8. 大规模随机 (N=50000)
 * 9. 大规模稀疏 (N=100000, 坐标分散)
 * 10. 大规模密集 (N=100000, 坐标集中)
 */

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <random>
#include <ctime>
#include <string>

using namespace std;

typedef long long ll;

// 64位随机数生成器 (处理大坐标)
mt19937_64 rng(time(0));

// 生成指定范围的随机数 [min, max]
ll rand_val(ll min_v, ll max_v) {
    uniform_int_distribution<ll> dist(min_v, max_v);
    return dist(rng);
}

// --- 标准解法部分 (Solver) ---
struct Point {
    int id;
    ll val;
};

// 核心逻辑：计算一维轴上每个点到其他所有点的距离和
// 时间复杂度 O(N log N)
void calc_1d_dist(int N, vector<Point>& pts, vector<ll>& total_costs) {
    // 1. 排序
    sort(pts.begin(), pts.end(), [](const Point& a, const Point& b) {
        return a.val < b.val;
    });

    // 2. 计算前缀和
    vector<ll> pref(N + 1, 0);
    for(int i = 0; i < N; ++i) {
        pref[i + 1] = pref[i] + pts[i].val;
    }

    // 3. 计算每个点的贡献
    for(int i = 0; i < N; ++i) {
        ll val = pts[i].val;
        // 左边的点：下标 0 ~ i-1 (共 i 个)
        // 贡献 = i * val - sum(0~i-1)
        ll left_cost = (ll)i * val - pref[i];

        // 右边的点：下标 i+1 ~ N-1 (共 N-1-i 个)
        // 贡献 = sum(i+1~N-1) - (N-1-i) * val
        ll right_sum = pref[N] - pref[i + 1];
        ll right_cost = right_sum - (ll)(N - 1 - i) * val;

        // 累加到该点原始ID的cost中
        total_costs[pts[i].id] += (left_cost + right_cost);
    }
}

// 求解主函数
string solve(int N, const vector<pair<ll, ll>>& coords) {
    vector<Point> x_pts(N), y_pts(N);
    for(int i = 0; i < N; ++i) {
        x_pts[i] = {i + 1, coords[i].first}; // 1-based ID
        y_pts[i] = {i + 1, coords[i].second};
    }

    // 存储每个ID的总距离，下标 1~N
    vector<ll> costs(N + 1, 0);

    // 分别处理 X 和 Y 轴
    calc_1d_dist(N, x_pts, costs);
    calc_1d_dist(N, y_pts, costs);

    // 寻找最小值
    ll min_c = -1;
    int best_id = -1;

    for(int i = 1; i <= N; ++i) {
        if(best_id == -1 || costs[i] < min_c) {
            min_c = costs[i];
            best_id = i;
        }
    }

    return to_string(best_id) + " " + to_string(min_c);
}

// --- 数据生成部分 ---
void make_case(int id) {
    int N;
    vector<pair<ll, ll>> coords;

    // 根据测试点编号设计数据
    switch(id) {
        case 1: // 样例
            N = 3;
            coords = {{1, 1}, {2, 2}, {3, 3}};
            break;
            
        case 2: // 小数据随机
            N = 10;
            for(int i=0; i<N; ++i) 
                coords.push_back({rand_val(-100, 100), rand_val(-100, 100)});
            break;
            
        case 3: // 水平直线 (Y相同)
            N = 50;
            for(int i=0; i<N; ++i)
                coords.push_back({rand_val(-1000, 1000), 100});
            break;
            
        case 4: // 垂直直线 (X相同)
            N = 50;
            for(int i=0; i<N; ++i)
                coords.push_back({-50, rand_val(-1000, 1000)});
            break;
            
        case 5: // 密集重叠点 (大量坐标相同)
            N = 200;
            for(int i=0; i<N; ++i) {
                // 坐标只在 0, 1, 2, 3, 4 中选
                coords.push_back({rand_val(0, 4), rand_val(0, 4)});
            }
            break;
            
        case 6: // 极限坐标 (测试 long long 溢出风险)
            N = 100;
            for(int i=0; i<N; ++i) {
                // 接近 10^9
                ll limit = 1000000000LL;
                coords.push_back({rand_val(-limit, limit), rand_val(-limit, limit)});
            }
            break;
            
        case 7: // 中等规模随机
            N = 1000;
            for(int i=0; i<N; ++i)
                coords.push_back({rand_val(-10000, 10000), rand_val(-10000, 10000)});
            break;
            
        case 8: // 大规模随机
            N = 50000;
            for(int i=0; i<N; ++i)
                coords.push_back({rand_val(-100000, 100000), rand_val(-100000, 100000)});
            break;
            
        case 9: // 大规模稀疏 (最大N, 坐标范围大)
            N = 100000;
            for(int i=0; i<N; ++i) {
                ll limit = 1000000000LL;
                coords.push_back({rand_val(-limit, limit), rand_val(-limit, limit)});
            }
            break;
            
        case 10: // 大规模密集 (最大N, 坐标范围小)
            N = 100000;
            for(int i=0; i<N; ++i)
                coords.push_back({rand_val(-1000, 1000), rand_val(-1000, 1000)});
            break;
    }

    // 1. 写入 .in 文件
    string in_file = to_string(id) + ".in";
    ofstream fout_in(in_file);
    fout_in << N << "\n";
    for(auto p : coords) {
        fout_in << p.first << " " << p.second << "\n";
    }
    fout_in.close();

    // 2. 计算并写入 .out 文件
    string out_file = to_string(id) + ".out";
    ofstream fout_out(out_file);
    fout_out << solve(N, coords) << "\n";
    fout_out.close();

    cout << "Generated Case " << id << " (N=" << N << ") Done." << endl;
}

int main() {
    // 提速
    ios_base::sync_with_stdio(false);
    
    for(int i = 1; i <= 10; ++i) {
        make_case(i);
    }
    
    return 0;
}

测试点设计说明

• Case 1 (Sample)：验证基本逻辑。
• Case 3 & 4 (Line)：测试在一维退化情况下的表现（这也是本题解法正确性的基石）。
• Case 5 (Duplicates)：测试多个学校在同一位置时，能否正确累加距离，以及题目要求的“ID最小”逻辑。
• Case 6 & 9 (Large Coords)：坐标达到 $\pm 10^9$，如果不使用 long long 累加距离，必然溢出。
• Case 10 (Max N)：$N=100,000$，测试算法的时间复杂度是否为 $O(N \log N)$（必须在1秒内跑完）。