题解：标准分数计算

题目理解

这道题目要求我们根据广东省高考标准分计算方法，将原始分数转换为标准分数。转换过程分为以下几个步骤：

1. 对所有学生的原始分数进行排序
2. 对于每个查询分数，计算低于该分数的学生比例$x$
3. 使用正态分布的逆累积分布函数$\Phi^{-1}(x)$计算中间标准分
4. 对中间标准分进行截断处理得到最终标准分

算法思路

1. 输入处理：读取多组测试数据，每组包含学生分数和查询
2. 排序处理：对学生分数进行排序以便计算百分位
3. 正态分布计算：
   • 使用梯形法数值积分计算$\Phi(x)$
   • 使用二分法计算$\Phi^{-1}(p)$
4. 标准分转换：根据公式将百分位转换为标准分
5. 结果输出：处理多组测试用例之间的空行

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <sstream>
#include <limits>
#include <array>

using namespace std;

// 定义计算精度和圆周率常量
const double EPS = 1e-10;       // 浮点数比较精度阈值
const double PI = 3.14159265358979323846;  // 圆周率π

// 预计算标准正态分布CDF表参数
constexpr int TABLE_SIZE = 801;  // 表大小(-4.0到4.0，步长0.01)
constexpr double TABLE_MIN = -4.0;  // 表最小值
constexpr double TABLE_MAX = 4.0;   // 表最大值
constexpr double TABLE_STEP = 0.01; // 步长
array<double, TABLE_SIZE> phi_table; // 存储预计算值的数组

/**
 * 初始化标准正态分布CDF预计算表
 * 使用泰勒级数展开近似计算Φ(x)值
 */
void init_phi_table() {
    for (int i = 0; i < TABLE_SIZE; ++i) {
        double x = TABLE_MIN + i * TABLE_STEP;  // 当前x值
        double sum = 0.5;  // Φ(0)的基础值
        double term = x;    // 泰勒级数当前项
        double x_sq = x * x;  // x的平方
        double numerator = x;  // 分子
        double denominator = 1.0;  // 分母
        int k = 1;  // 迭代计数器
        
        // 使用泰勒级数近似计算积分
        while (k < 100) {
            sum += term;  // 累加当前项
            numerator *= x_sq;  // 更新分子
            denominator *= 2 * k + 1;  // 更新分母
            term = numerator / (denominator * (2 * k + 1));  // 计算下一项
            if (abs(term) < 1e-15) break;  // 项足够小则终止
            k++;
        }
        // 存储计算结果: 0.5 + 积分值
        phi_table[i] = 0.5 + sum * exp(-0.5 * x_sq) / sqrt(2 * PI);
    }
}

/**
 * 使用预计算表快速获取Φ(x)值
 * @param x 输入值
 * @return 标准正态分布在x处的累积概率
 */
double fast_phi(double x) {
    // 处理超出表范围的极端值
    if (x <= TABLE_MIN) return 0.0;
    if (x >= TABLE_MAX) return 1.0;
    
    // 计算x在表中的位置
    double idx = (x - TABLE_MIN) / TABLE_STEP;
    int lower = static_cast<int>(idx);  // 下限索引
    double frac = idx - lower;         // 小数部分
    
    // 边界检查
    if (lower + 1 >= TABLE_SIZE) return phi_table[TABLE_SIZE - 1];
    
    // 线性插值返回结果
    return phi_table[lower] * (1 - frac) + phi_table[lower + 1] * frac;
}

/**
 * 计算标准正态分布累积分布函数的逆函数Φ⁻¹(p)
 * @param p 概率值(0,1)
 * @param epsilon 精度阈值
 * @return 对应的x值
 */
double fast_inverse_phi(double p, double epsilon = 1e-7) {
    // 处理边界情况
    if (p <= 0.0) return -numeric_limits<double>::infinity();
    if (p >= 1.0) return numeric_limits<double>::infinity();
    
    // 有理函数近似系数
    static const double a[] = {-3.969683028665376e+01, 2.209460984245205e+02,
                              -2.759285104469687e+02, 1.383577518672690e+02,
                              -3.066479806614716e+01, 2.506628277459239e+00};
    static const double b[] = {-5.447609879822406e+01, 1.615858368580409e+02,
                              -1.556989798598866e+02, 6.680131188771972e+01,
                              -1.328068155288572e+01};
    static const double c[] = {-7.784894002430293e-03, -3.223964580411365e-01,
                              -2.400758277161838e+00, -2.549732539343734e+00,
                              4.374664141464968e+00, 2.938163982698783e+00};
    static const double d[] = {7.784695709041462e-03, 3.224671290700398e-01,
                              2.445134137142996e+00, 3.754408661907416e+00};
    
    double q = min(p, 1 - p);  // 对称处理
    double t, x;
    
    if (q > 0.02425) {
        // 中心区域有理逼近
        t = q - 0.5;
        double num = ((((a[0]*t + a[1])*t + a[2])*t + a[3])*t + a[4])*t + a[5];
        double den = ((((b[0]*t + b[1])*t + b[2])*t + b[3])*t + b[4])*t + 1.0;
        x = t * num / den;
    } else {
        // 尾部区域有理逼近
        t = sqrt(-2 * log(q));
        x = ((((c[0]*t + c[1])*t + c[2])*t + c[3])*t + c[4])*t + c[5];
        double den = (((d[0]*t + d[1])*t + d[2])*t + d[3])*t + 1.0;
        x = x / den;
    }
    
    // 调整符号
    if (p < 0.5) x = -x;
    
    // 牛顿迭代法精修结果
    for (int i = 0; i < 2; ++i) {
        double err = fast_phi(x) - p;
        if (abs(err) < epsilon) break;
        double dx = err * sqrt(2 * PI) * exp(0.5 * x * x);
        x -= dx;
    }
    
    return x;
}

/**
 * 计算给定原始分数的标准分
 * @param x 原始分数
 * @param sorted_points 已排序的分数列表
 * @return 标准分(100-900)
 */
int compute_standard_point(int x, const vector<int>& sorted_points) {
    int n = sorted_points.size();
    if (n == 0) return 0;  // 空列表处理
    
    // 使用二分查找确定x的位置
    auto left = lower_bound(sorted_points.begin(), sorted_points.end(), x);
    auto right = upper_bound(sorted_points.begin(), sorted_points.end(), x);
    
    // 计算百分位
    double percentage = (left - sorted_points.begin()) / (double)n;
    
    double sp_prime;  // 中间标准分
    if (percentage == 0.0) {
        sp_prime = -numeric_limits<double>::infinity();  // 最低分
    } else if (percentage == 1.0) {
        sp_prime = numeric_limits<double>::infinity();   // 最高分
    } else {
        // 计算标准分: 500 + 100*Φ⁻¹(percentage)
        sp_prime = 500 + 100 * fast_inverse_phi(percentage);
    }
    
    // 限制标准分范围在100-900之间
    if (sp_prime <= 100) {
        return 100;
    } else if (sp_prime > 900) {
        return 900;
    } else {
        return (int)round(sp_prime);  // 四舍五入
    }
}

int main() {
    // 优化IO性能
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 初始化预计算表
    init_phi_table();
    
    // 读取所有输入行
    string line;
    vector<string> input_lines;
    while (getline(cin, line)) {
        input_lines.push_back(line);
    }
    
    size_t ptr = 0;  // 当前处理行指针
    bool first_case = true;  // 首个测试用例标志
    
    // 处理每个测试用例
    while (true) {
        // 跳过空行
        while (ptr < input_lines.size() && input_lines[ptr].empty()) {
            ptr++;
        }
        if (ptr >= input_lines.size()) {
            break;  // 输入结束
        }
        
        // 读取学生人数N
        int N = stoi(input_lines[ptr]);
        ptr++;
        if (N == 0) {
            break;  // N=0表示输入结束
        }
        
        // 读取所有学生分数
        vector<int> points;
        for (int i = 0; i < N; ++i) {
            points.push_back(stoi(input_lines[ptr]));
            ptr++;
        }
        
        // 读取查询数量M
        int M = stoi(input_lines[ptr]);
        ptr++;
        vector<int> queries;
        for (int i = 0; i < M; ++i) {
            queries.push_back(stoi(input_lines[ptr]));
            ptr++;
        }
        
        // 排序分数用于百分位计算
        vector<int> sorted_points = points;
        sort(sorted_points.begin(), sorted_points.end());
        
        // 预计算查询结果(避免重复计算)
        map<int, int> score_to_standard;
        for (int q : queries) {
            if (score_to_standard.find(q) == score_to_standard.end()) {
                score_to_standard[q] = compute_standard_point(q, sorted_points);
            }
        }
        
        // 测试用例间输出空行(首个除外)
        if (!first_case) {
            cout << '\n';
        }
        first_case = false;
        
        // 输出查询结果
        for (int q : queries) {
            cout << score_to_standard[q] << '\n';
        }
    }
    
    return 0;
}

复杂度分析

1. 排序：$O(N \log N)$，使用快速排序
2. 查询处理：$O(M \log N)$，使用二分查找
3. 正态分布计算：每次计算$\Phi(x)$需要$O(n)$时间，$n$是积分步数
4. 逆函数计算：每次需要$O(k)$次迭代，$k$取决于精度要求