凸包——G - Highest Ratio

G - Highest Ratio

来源：AtCoder Beginner Contest 341-G

题目描述：

给定长度为 $N$ 的序列 $A=(A_1,A_2,\dots ,A_N)$。

对于每个 $k=1,2,\dots ,N$，解决以下问题：

选择整数 $r$，使得序列 $A$ 的第 $k$ 到第 $r$ 项的平均值最大化，并满足 $k\le r\le N$。

这里，序列 $A$ 的第 $k$ 到第 $r$ 项的平均值定义为：

$\frac{1}{r-k+1}{\sum }_{i=k}^r{A}_i$

约束条件：

• $1\le N\le 2\times 10^5$
• $1\le A_i\le 10^6$
• 所有输入值都是整数。

Output:

输出格式：

• 打印 $N$ 行。
• 第 $i$ 行（$1\le i\le N$）应包含当 $k=i$ 时问题的答案。
• 您的输出将被视为正确，如果对于每一行，打印值与真实值之间的绝对或相对误差最多为 $10^{-6}$。

Sample

输入：

5
1 1 4 5 3

输出：

2.80000000
3.33333333
4.50000000
5.00000000
3.00000000

思路：

记 $Si$ 为前 i 个元素的前缀和，在平面上放N个点$(i,Si)$，第 x 个点到第 y 个点连线的斜率即为区间$(x+1,y)$的平均值（平均值 = $(Sy-Sx)/(y-x)$ = 斜率），在这个图上求凸包即可

在求凸包的循环中，如果栈顶的点不属于凸包，则弹出栈顶元素，该点的ans即为该点与弹出后的栈顶点的斜率值。
求完凸包后，凸包上的相邻两点的斜率即为ans

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+10;
int T;
vector<int> stk;

// 定义点的结构体
struct Point{
  double x, y;
  // 重载减法运算符，用于计算向量差
  Point operator-(Point& p){
    Point t;
    t.x = x - p.x;
    t.y = y - p.y;
    return t;
  }
  // 计算向量叉积
  double cross(Point p) {
    return x * p.y - p.x * y;
  }
};

// 比较函数，用于排序点
bool cmp(Point& p1, Point& p2) {
  if (p1.x != p2.x) return p1.x < p2.x;
  return p1.y < p2.y;
}

Point point[N];  // 保存无序的点
int convex[N];  // 保存组成凸包的点的下标
int n;  // 无序点的个数
int sum[N];  // 前缀和数组
double ans[N];  // 保存每个点的最大斜率
bool st[N];  // 标记点是否在凸包中（未在代码中使用）

// 计算两点间的斜率
double kk(Point& a, Point& b) {
  return (b.y - a.y) * 1.00 / (b.x - a.x);
}

// 构建凸包
void GetConvexHull() {
  int total = 0;
  convex[total++] = n;  // 将最后一个点（索引为 n）加入凸包
  ans[n] = 1.00 * (sum[n] - sum[n - 1]);  // 计算最后一个点的斜率
  for (int i = n - 1; i >= 0; i--) {
    while (total > 1 && (point[convex[total - 1]] - point[convex[total - 2]]).cross(point[i] - point[convex[total - 1]]) <= 0) {
      ans[convex[total - 1]] = kk(point[convex[total - 1]], point[convex[total - 2]]);  // 计算斜率
      total--;  // 弹出栈顶点
    }
    convex[total++] = i;  // 将当前点加入凸包
  }
  for (int i = total - 1; i >= 1; i--) {
    ans[convex[i]] = kk(point[convex[i]], point[convex[i - 1]]);  // 计算斜率
  }
  return;
}

// 解决问题的主函数
void solve() {
  cin >> n;  // 读取点的个数
  int x;
  sum[0] = 0;
  point[0] = {0, 0};
  for (int i = 1; i <= n; i++) {
    cin >> x;
    sum[i] = sum[i - 1] + x;  // 计算前缀和
    point[i] = {i, sum[i]};  // 初始化点
  }
  GetConvexHull();  // 构建凸包
  for (int i = 0; i < n; i++) {
    printf("%.8lf\n", ans[i]);  // 输出每个点的最大斜率
  }
}

signed main() {
  solve();  // 调用解决问题的主函数
  return 0;
}