Average and Median（500）dp，二分 AtCoder Beginner Contest 236

E - Average and Median /
Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 500 points

Problem Statement
We have N cards. The i-th card (1≤i≤N) has an integer A
i
​
written on it.

Takahashi will choose any number of cards from these. However, for each i (1≤i≤N−1), at least one of the i-th and (i+1)-th cards must be chosen.

Find the following values.

The maximum possible average of the integers written on the chosen cards
The maximum possible median of the integers written on the chosen cards
Here, the median of the n integers is defined to be the ⌈
2
n
​
⌉-th smallest of them, where ⌈x⌉ is the smallest integer not less than x.

Constraints
2≤N≤10
5

1≤A
i
​
≤10
9

All values in input are integers.
Input
Input is given from Standard Input in the following format:

N
A
1
​
… A
N
​

Output
Print two lines. The first and second lines should contain the maximum possible average and maximum possible median of the integers written on the chosen cards, respectively. For the average, your output will be considered correct when its relative or absolute error from the exact answer is at most 10
−3
.

Sample Input 1
Copy
6
2 1 2 1 1 10
Sample Output 1
Copy
4
2
Choosing the 2-nd, 4-th, and 6-th cards makes the average of the written integers
3
12
​
=4, which is the maximum possible.

Choosing the 1-st, 3-rd, 5-th, and 6-th cards makes the median of the written integers 2, which is the maximum possible.

Sample Input 2
Copy
7
3 1 4 1 5 9 2
Sample Output 2
Copy
5.250000000
4
For the average, your output may contain some degree of error: for example, the output 5.2491 is still considered correct. For the median, however, the exact value must be printed.

题意 ：

• 有n个数，从其中选若干个，规则是$\forall i(1\le i\le n-1)$，都满足i和i+1个中 至少 被选择一个；求所有满足的方案中，选出的数的，最大平均值 和 最大中位数（第$n/2$向上取整个小的）

思路 ：

• 最大化平均值或者中位数 最常见的方法是 “结果是否超过k”，然后通过二分查找找出答案
• “平均值超过k吗”：数列的平均值超过k，等价于 数列中每个数都减去k后，新的数列的元素和大于0，因此，定义一个新的数组$b_i=a_i-k$，然后判断是否b_i的最大和大于0
• 首先我们看看这里中位数的定义，相当于如果4个数，第二个数是中位数；如果5个数，第三个数是中位数
• “中位数超过k吗”：数列的中位数超过k，等价于 超过k的元素的个数 小于等于k；因此，定义$b_i=1/-1$，当a_i >= k时，b_i为1，然后判断是否b_i的最大和是正数
• 那么如果找出b_i的最大和呢？答案是通过dp；$f_i$表示，考虑前i个元素时，第i个元素被选择的情况下，b数组的最大和；$g_i$表示，考虑前i个元素时，第i个元素不被选择的情况下，b数组的最大和；甚至可以不使用dp的方法，枚举到第i个元素时，考虑第i-1个元素，选择第i-1个元素的结果为sel，不选择的结果为unsel，则选择第i个元素的结果为max(sel, unsel) + x，不选择的结果为unsel，选择为max(sel, unsel) + x，最后返回max(sel, unsel)

#include <iostream> #include <iomanip> using namespace std;const int N = 1e5 + 10; const double esp = 1e-6;int a[N];int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int n; cin >> n;for (int i = 1; i <= n && cin >> a[i]; i ++ );double l = 0.0, r = 1e9 + 1, mid;while (r - l > esp){mid = (l + r) / 2;double sel = 0.0, optimal = 0.0;for (int i = 1; i <= n; i ++ ){sel += a[i] - mid;optimal = max(sel, optimal);swap(sel, optimal);}if (sel > 0) l = mid;else r = mid;}cout << fixed << setprecision(5) << r << endl;int L = 0, R = 1e9 + 1, MID;while (L + 1 != R){MID = L + R >> 1;int cnt = 0, mx = 0;for (int i = 1; i <= n; i ++ ){if (a[i] > MID) cnt ++ ;else cnt -- ;mx = max(mx, cnt);swap(mx, cnt);}if (cnt > 0) L = MID;else R = MID;}cout << R << endl; }

总结

以上是生活随笔为你收集整理的Average and Median（500）dp，二分 AtCoder Beginner Contest 236的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。