AtCoder Beginner Contest (ABC) 236-E-Average and Median
题目大意：给出一个数列a[]，可以删掉数列中任意多的元素，问在分别在原数列基础上删掉任意多的元素，且不删掉任意两个相邻元素的情况下，所剩数列的最大平均值和中位数分别是多大。
这道题一看就是二分答案。但是二分的判断函数是什么？
注意到，如果知道答案的话，可以通过递推来求得原数列中各个前缀的很多性质。比如在判断平均值合法性的函数中，可以通过递推得知每个前缀所能取得的最大平均值，从而得到整个数列所能取得的最大平均值；但是在我的设想中，这个转移方程非常复杂，影响状态转移的因素有元素的位置、是否删除以及与待验证答案的大小关系都有关结果就是写了个长度近百行的转移方程 竟然还过了两组样例。
题解中也确实是用递推来验证答案的可行性，但使用了较为简便的方法。
首先是验证一个数与最大可能平均值的大小关系。对于数列a，要验证它的平均值与常数k的大小关系，如果∑i=1n(ai−k)>0，那么数列a的平均值肯定是大于k的，反之亦然。状态dp[n][2]表示删除/不删除第n个数所能取到的这个值的前缀和的最大值，就可以通过递推得到整个数列的平均值与k的关系了。
然后是验证一个数与最大可能中位数的大小关系。对于数列a，要验证它的中位数与常数k的大小关系，其实就是要看数列中大于k的数的数量与小于k的数的数量是否相等。如果相等，那么k就是中位数。将数列中所有数值小于k的数视为-1，所有大于k的数视为1，就可以快速知道数列中大于k的数的数量与小于k的数的数量是否相等了。构造类似上面所说的平均数的状态，也可以快速验证一个数与最大可能中位数的大小关系了。
然而，如果数列中大于k的数的数量与小于k的数的数量不相等，也不能说明中位数的数值不是k，因为可能存在多个数值与k相等的数。最开始，我统计了每个状态下取的所有与k相等的数的数量，并且也一直往后传递，这导致我这个状态转移的代码也写了大几十行不幸的是最后也没过样例。其实只要将等于k的视作大于k的处理，并且保证在最后全部的1和-1相加大于0就可以了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
double dp[100005][2];
int f[100005][2], a[100005], n;
bool c1(double x)
{
dp[1][1] = a[1] - x;
dp[1][0] = 0;
for (int i = 2; i <= n; i++)
{
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0]) + (a[i] - x);
dp[i][0] = max(dp[i - 1][1], dp[i][1]);
}
return max(dp[n][0], dp[n][1]) >= 0;
}
bool c2(int x)
{
f[1][1] = (a[1] >= x) - (a[1] < x);
f[1][0] = 0;
for (int i = 2; i <= n; i++)
{
f[i][1] = max(f[i - 1][1], f[i - 1][0]) - (a[i] < x) + (a[i] >= x);
f[i][0] = max(f[i - 1][1], f[i][1]);
}
return max(f[n][0], f[n][1]) > 0;
}
int main()
{
int l, r, md, i;
scanf("%d", &n);
for (i = 1; i <= n; i++)
scanf("%d", &a[i]);
double ll = 1, rr = 1e9 + 1, mdd;
while (rr - ll > 1e-6)
{
mdd = (rr - ll) / 2 + ll;
if (c1(mdd))
ll = mdd;
else
rr = mdd;
}
printf("%f\n", ll);
l = 0;
r = 1e9 + 1;
while (r - l > 1)
{
md = ((r - l) >> 1) + l;
if (c2(md))
l = md;
else
r = md;
}
printf("%d\n", l);
return 0;
}
|