题目描述：
$ N $ 张卡片，每张上面有个数 $ a_i $ ，选一些卡片，但是要求 $ i $ 和 $ i + 1 $ 至少选一张。
求：
- 选出卡片，能够得到的最大的平均值
- 选出卡片，能够得到的最大的中位数（中位数是 $ \lceil \frac{n}{2} \rceil $ ）
数据范围：
- $ 2 \le N \le 10^5 $
- $ 1\le A_i \le 10^9 $
题解：
考虑 $ dp(0, j) $ 表示取第 $ j $ 张， $ dp(1, j) $ 表示不取第 $ j $ 张。那么最大值为 $ \max(dp(0, n), dp(1, n)) $
考虑使用二分，然后使用 dp 进行 check。
最大平均值：
二分出 mid，将 $ a_i $ 都减去 mid，然后就是求最大值大于等于 $ 0 $ 。如果成立，那么 mid 作为平均值可行，否则不行。
最大中位数：
注意这个中位数有点邪乎，需要考虑取整。
二分出 mid，将大于等于 mid 的看做 $ 1 $ ，将小于 mid 的看做 $ -1 $ 。然后求最大值，最大值大于 $ 0 $ 的时候可行。（为什么大于 $ 0 $ ，上面是大于等于？就是因为这个取整，大于零可以保证全是 $ 1 $ 和 $ -1 $ 时是奇数，能够取到一个 $ 1 $ 的值。）
第一个二分可以使用浮点数二分（寻常法或固定二分次数，或者直接扩大 $ 1000 $ 倍，求整数二分）。
第二个二分必须使用整数二分。
（之前 dp 数组行列开反了，居然没报错，一直 wa，气死了）
代码：
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
| using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e1 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
ll a[maxn];
ll b[maxn];
ll dp[2][maxn];
ll check()
{
dp[0][0] = dp[1][0] = 0;
for (int i = 1; i <= n; i++)
{
dp[0][i] = max(dp[0][i - 1], dp[1][i - 1]) + b[i];
dp[1][i] = dp[0][i - 1];
}
return max(dp[0][n], dp[1][n]);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
ll r = -1;
ll l = INF_LL;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
r = max(r, a[i]);
l = min(l, a[i]);
}
ll r1 = r * 1000, l1 = l * 1000;
ll ans1 = -1;
while (l1 <= r1)
{
ll mid = (r1 + l1) >> 1;
for (int i = 1; i <= n; i++)
{
b[i] = a[i] * 1000 - mid;
}
if (check() >= 0)
{
ans1 = mid;
l1 = mid + 1;
}
else
{
r1 = mid - 1;
}
}
int ans2 = -1;
int l2 = l, r2 = r;
while (l2 <= r2)
{
int mid = l2 + ((r2 - l2) >> 1);
for (int i = 1; i <= n; i++)
{
b[i] = (a[i] >= mid ? 1 : -1);
}
if (check() > 0)
{
ans2 = mid;
l2 = mid + 1;
}
else
{
r2 = mid - 1;
}
}
printf("%.9f\n%d\n", ans1 * 1.0 / 1000, ans2);
return 0;
}
|