← 返回题目列表

AtCoder · pakencamp_2024_day3_2_e

E. 过山车

中文机器翻译题面 查看原题

配点 : 100 点

問題文

游乐园“Pakenland”有 有N 点, 第i 个点的海拔是 H_i 。还有,在公园里 M 有过山车轨道,i 铁轨是一个点 U_i 和 V_i 双向连接。

您想要使用其中一些轨道来构建满足以下条件的过山车路径:

  • 通过点的顺序 v_0, v_1, \dots, v_n 可以表示为v_0 = v_n 成立。
  • 全部 有一条轨道直接连接 i (1 \leq i \leq n),v_{i-1} 和 v_i 。

还有,过山车 有趣 使用以下公式定义 。

\[ \frac{1}{n} \sum_{i=1}^{n} \max(0, H_{v_{i-1}} - H_{v_i}) \]

找到享受的最大价值。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq U_{i} \lt V_{i} \leq N (1 \leq i \leq M)
  • i \neq j 然后, (U_{i}, V_{i}) \neq (U_{j}, V_{j})
  • 输入全部为整数

入力

输入将以以下格式从标准输入提供。

N M  
H_1 H_2 \ldots H_N   
U_1 V_1  
U_2 V_2  
\vdots  
U_M V_M  

出力

打印答案。与真实值的绝对或相对误差为 10^{-9} 以下情况被确定为正确的。 按照


入力例 1

4 5 
1 2 3 4 
1 2 
1 3 
1 4 
2 3 
3 4 

出力例 1

1.5

例如, 4, 3, 2, 1, 4 顺序通过的过山车满足问题陈述中的条件。有趣的是 自

  • H_4 - H_3 = 1
  • H_3 - H_2 = 1
  • H_2 - H_1 = 1
  • H_1 - H_4 = -3

以来, 该值除以 (\max(0, 1) + \max(0, 1) + \max(0, 1) + \max(0, -3)) 的 4 ,即 0.75 。 采取
如果你建造了一条最大化享受的路线,它的价值将为 1.5 。 采取

入力例 2

4 2 
1 1 2 3 
1 2 
3 4 

出力例 2

0.5 

游乐园中可能存在一组不仅通过轨道连接的点。