#Q. Average and Median

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l
    Type: RemoteJudge 2000ms 256MiB

Average and Median

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面翻译

nn 个数 a1…ana_{1}\dots a_n 排成一列。现在要选出一些数，满足 任意两个相邻的数中至少有一个数被选择。

请求出：

  • 所有选择方案中，被选中的数字平均值的最大值，误差在 10−310^{-3} 以内视为正确；
  • 所有选择方案中，被选中的数字中位数的的最大值。在这里，偶数 2k2k 个数的中位数视作第 kk 小的数。
  • 2≤n≤1052\leq n\leq 10^5
  • 1≤ai≤1091\leq a_i\leq 10^9

题目描述

N N 枚のカードがあり、i   (1 ≤ i ≤ N) i\ \,\ (1\ \leq\ i\ \leq\ N) 番目のカードには整数 Ai A_i が書かれています。

高橋君は、これらのカードから好きな枚数選びます。ただし、各 i   (1 ≤ i ≤ N − 1) i\ \,\ (1\ \leq\ i\ \leq\ N\ -\ 1) について、i i 番目のカードと i + 1 i\ +\ 1 番目のカードの少なくとも一方を選ぶ必要があります。

以下の値を求めてください。

  • 選んだカードに書かれた整数の平均値としてあり得る最大値
  • 選んだカードに書かれた整数の中央値としてあり得る最大値

ただし、n n 個の整数の中央値は、それらのうち小さい方から数えて ⌈ n2 ⌉ \lceil\ \frac{n}{2}\ \rceil 番目であるものとします。ここで、⌈ x ⌉ \lceil\ x\ \rceil は x x 以上の最小の整数を表します。

输入格式

入力は以下の形式で標準入力から与えられる。

N N A1 A_1 … \ldots AN A_N

输出格式

2 2 行出力せよ。1 1 行目には選んだカードに書かれた整数の平均値としてあり得る最大値を、2 2 行目には選んだカードに書かれた整数の中央値としてあり得る最大値を出力せよ。 平均値の出力については、正しい値との相対誤差または絶対誤差が 10−3 10^{-3} 以下であれば正答とみなされる。

样例 #1

样例输入 #1

6
2 1 2 1 1 10

样例输出 #1

4
2

样例 #2

样例输入 #2

7
3 1 4 1 5 9 2

样例输出 #2

5.250000000
4

提示

制約

  • 2 ≤ N ≤ 105 2\ \leq\ N\ \leq\ 10^5
  • 1 ≤ Ai ≤ 109 1\ \leq\ A_i\ \leq\ 10^{9}
  • 入力は全て整数である。

Sample Explanation 1

2 2 番目、4 4 番目、6 6 番目のカードを選ぶと、書かれた整数の平均は 123 = 4 \frac{12}{3}\ =\ 4 となり、これが最大です。 1 1 番目、3 3 番目、5 5 番目、6 6 番目のカードを選ぶと、書かれた整数の中央値は 2 2 となり、これが最大です。

Sample Explanation 2

平均値の出力については誤差が認められるので、例えば 5.2491 5.2491 と出力しても正答とみなされます。ただし、中央値は正確な値を出力しなければなりません。

北辰OI提高组第2周序列问题课后练习题👍

Not Attended
Status
Done
Rule
IOI
Problem
44
Start at
2024-1-7 16:00
End at
2024-2-18 8:00
Duration
1000 hour(s)
Host
Partic.
15
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. text

  4. 鲁公网安备 37079402001599号

  • 鲁ICP备2022025036号-1
  • Worker 0, 64ms
  • Powered by Hydro v4.9.27 Community