题解：线性函数极值问题

解题思路

本题需要求解线性函数$F(q_1, q_2, ..., q_n)$在给定约束条件下的最小值和最大值。函数定义为：

其中$\sum_{i=1}^n \mu_i = 1$且$0 < \mu_i \leq 1$。已知$F(p_1, p_2, ..., p_n) = C$，需要在给定$q_i$的情况下找到$F(q_1, q_2, ..., q_n)$的极值。

关键思路是将问题转化为几何问题，通过计算点集的凸包来高效确定极值。

算法分析

1. 几何转换：

   • 将每个$(p_i, q_i)$看作二维平面上的点
   • 极值问题转化为在凸包上寻找与$x=C$的交点的最大和最小$y$值

2. 复杂度分析：

   • 凸包构建：$O(n \log n)$
   • 极值查询：$O(n)$
   • 总复杂度：$O(n \log n)$ （对于$n \leq 50000$可接受）

3. 特殊情况处理：

   • 当$n=1$时直接输出唯一解
   • 处理共线点和重复点的情况

C++代码实现（带详细注释）

#include <iostream>
#include <iomanip>  // 用于控制输出格式
#include <vector>   // 使用vector存储点集
#include <algorithm> // 使用sort等算法
#include <cmath>    // 使用数学函数

const double INF = 1e50;  // 定义一个很大的数表示无穷大

// 定义点的结构体
struct Point {
    int x, y;  // x坐标表示p_i，y坐标表示q_i
};

// 计算向量叉积
double cross(const Point& o, const Point& a, const Point& b) {
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

// 计算两点间的欧几里得距离
double dist(const Point& A, const Point& B) {
    return std::hypot(A.x - B.x, A.y - B.y);
}

// 自定义排序比较函数
bool cmp(const Point& A, const Point& B, const Point& minp) {
    double k = cross(minp, A, B);
    if (k < 0) return false;  // 如果叉积为负，说明B在A的顺时针方向
    if (k > 0) return true;   // 如果叉积为正，说明A在B的顺时针方向
    return dist(minp, A) < dist(minp, B);  // 共线时按距离排序
}

// Graham扫描算法求凸包
std::vector<Point> GrahamScan(const std::vector<Point>& points) {
    int n = points.size();
    std::vector<Point> p = points;
    std::vector<Point> stk;  // 用于存储凸包上的点

    // 找到y坐标最小的点（如果y相同则取x较小的点）
    for (int i = 1; i < n; ++i) {
        if (p[i].y < p[0].y || (p[i].y == p[0].y && p[i].x < p[0].x)) {
            std::swap(p[i], p[0]);
        }
    }

    Point minp = p[0];  // 基准点
    p.push_back(p[0]);  // 在末尾添加基准点以便形成闭合环
    
    // 按极角排序
    std::sort(p.begin() + 1, p.end() - 1, [minp](const Point& A, const Point& B) {
        return cmp(A, B, minp);
    });

    // 构建凸包
    stk.push_back(p[0]);
    stk.push_back(p[1]);

    for (int i = 2; i < n; ++i) {
        // 当新点在当前凸包边的右侧时，弹出栈顶的点
        while (stk.size() >= 2 && cross(stk[stk.size() - 2], stk[stk.size() - 1], p[i]) <= 0) {
            stk.pop_back();
        }
        stk.push_back(p[i]);
    }

    return stk;
}

// 更新最大和最小y坐标
void update(const Point& a, const Point& b, int c, double& mmin, double& mmax) {
    Point pa = a, pb = b;
    // 确保pa在pb的左侧
    if (pa.x > pb.x) {
        std::swap(pa, pb);
    }
    
    // 检查x=c是否在pa和pb之间
    if (pa.x <= c && pb.x >= c) {
        // 如果两点x坐标相同
        if (pa.x == c && pb.x == c) {
            mmax = std::max(mmax, static_cast<double>(std::max(pa.y, pb.y)));
            mmin = std::min(mmin, static_cast<double>(std::min(pa.y, pb.y)));
        } else {
            // 线性插值计算y值
            double k = static_cast<double>(c - pa.x) / (pb.x - pa.x) * (pb.y - pa.y) + pa.y;
            mmax = std::max(mmax, k);
            mmin = std::min(mmin, k);
        }
    }
}

int main() {
    int n, c;
    while (std::cin >> n >> c) {  // 读取点数和目标值C
        std::vector<Point> points(n);
        
        // 读取p_i值
        for (int i = 0; i < n; ++i) {
            std::cin >> points[i].x;
        }
        
        // 读取q_i值
        for (int i = 0; i < n; ++i) {
            std::cin >> points[i].y;
        }

        // 特殊情况处理：当n=1时直接输出
        if (n == 1) {
            std::cout << std::fixed << std::setprecision(3) 
                      << static_cast<double>(points[0].y) << " "
                      << static_cast<double>(points[0].y) << std::endl;
            continue;
        }

        // 计算凸包
        std::vector<Point> stk = GrahamScan(points);
        stk.push_back(stk[0]);  // 形成闭合环

        double mmin = INF, mmax = -INF;  // 初始化最小值和最大值
        
        // 遍历凸包的每条边，更新极值
        for (size_t i = 1; i < stk.size(); ++i) {
            update(stk[i - 1], stk[i], c, mmin, mmax);
        }

        // 输出结果，保留3位小数
        std::cout << std::fixed << std::setprecision(3) 
                  << mmin << " " << mmax << std::endl;
    }

    return 0;
}

复杂度分析

1. 时间复杂度：

   • 凸包构建：$O(n \log n)$（主要来自排序操作）
   • 极值查询：$O(n)$（遍历凸包边）
   • 总时间复杂度：$O(n \log n)$

2. 空间复杂度：

   • 存储点集：$O(n)$
   • 凸包存储：$O(n)$
   • 总空间复杂度：$O(n)$