思路
直接将输出的答案分为两个分考虑。
(1)
考虑二分 + DP。
设当前二分出的平均数为 \(x\)，如果合法，那么有（其中 \(p\) 为选出数下标的集合）：
\[ \frac{a_{p_1} + a_{p_2} + \dots + a_{p_k}}{k} \geq x \]即：
\[ \frac{(a_{p_1} - x) + (a_{p_2} - x) + \dots + (a_{p_k} - x)}{k} \geq 0 \]所以：
\[ (a_{p_1} - x) + (a_{p_2} - x) + \dots + (a_{p_k} - x) \geq 0 \]不妨令 \(A_i = a_i - x\)，那么 \(dp_i\) 表示在 \(A\) 的前 \(i\) 个数中选，并且必须选 \(A_i\) 的最大子序列和（在满足题意的情况下）。
那么，得出状态转移方程：
\[ dp_{i} = \max(dp_{i - 1},dp_{i - 2}) + A_i \]最后，如果 \(\max(dp_n,dp_{n - 1}) \geq 0\) 说明当前的 \(x\) 合法。
(2)
同理，二分 + DP。
设当前二分出的中位数为 \(x\)。
- 如果 \(a_i < x\)，令 \(B_i = -1\)。
- 否则，令 \(B_i = 1\)。
那么 \(dp_i\) 表示在 \(B\) 的前 \(i\) 个数中选，并且必须选 \(A_i\) 的最大子序列和（在满足题意的情况下）。
如果 \(\max(dp_n,dp_{n - 1}) > 0\) 说明当前的 \(x\) 合法。
Code
#include <bits/stdc++.h>
#define re register
using namespace std;
const int N = 1e5 + 10;
const double eps = 1e-6;
int n;
double arr[N],A[N],dp1[N];
int B[N],dp2[N];
inline int read(){
int r = 0,w = 1;
char c = getchar();
while (c < '0' || c > '9'){
if (c == '-') w = -1;
c = getchar();
}
while (c >= '0' && c <= '9'){
r = (r << 3) + (r << 1) + (c ^ 48);
c = getchar();
}
return r * w;
}
inline bool check1(double x){
for (re int i = 1;i <= n;i++) dp1[i] = max(dp1[i - 2],dp1[i - 1]) + A[i];
return max(dp1[n],dp1[n - 1]) >= 0;
}
inline bool check2(double x){
for (re int i = 1;i <= n;i++) dp2[i] = max(dp2[i - 2],dp2[i - 1]) + B[i];
return max(dp2[n],dp2[n - 1]) > 0;
}
int main(){
n = read();
for (re int i = 1;i <= n;i++) scanf("%lf",&arr[i]);
double l = 0,r = 1e9;
while (r - l > eps){
double mid = (l + r) / 2;
for (re int i = 1;i <= n;i++) A[i] = arr[i] - mid;
if (check1(mid)) l = mid;
else r = mid;
}
printf("%.4lf\n",l);
int ll = 0,rr = 1e9;
while (ll < rr){
int mid = ll + rr + 1 >> 1;
for (re int i = 1;i <= n;i++){
if (arr[i] >= mid) B[i] = 1;
else B[i] = -1;
}
if (check2(mid)) ll = mid;
else rr = mid - 1;
}
printf("%d",ll);
return 0;
}