Average and Median
unknown
plain_text
2 years ago
1.3 kB
8
Indexable
#include <bits/stdc++.h> using namespace std; const int INF = 1010000000; int main(){ cout << fixed << setprecision(20); int N; cin >> N; vector<int> A(N); for (int i = 0; i < N; i++){ cin >> A[i]; } double tv1 = 0, fv1 = INF; for (int i = 0; i < 50; i++){ double mid = (tv1 + fv1) / 2; vector<double> B(N); for (int j = 0; j < N; j++){ B[j] = A[j] - mid; } vector<vector<double>> dp(N + 1, vector<double>(2, -INF)); dp[0][1] = 0; for (int j = 0; j < N; j++){ dp[j + 1][0] = dp[j][1]; dp[j + 1][1] = max(dp[j][0], dp[j][1]) + B[j]; } if (dp[N][0] > 0 || dp[N][1] > 0){ tv1 = mid; } else { fv1 = mid; } } cout << tv1 << endl; int tv2 = 0, fv2 = INF; while (fv2 - tv2 > 1){ int mid = (tv2 + fv2) / 2; vector<vector<int>> dp(N + 1, vector<int>(2, -INF)); dp[0][1] = 0; for (int i = 0; i < N; i++){ dp[i + 1][0] = dp[i][1]; dp[i + 1][1] = max(dp[i][0], dp[i][1]); if (A[i] >= mid){ dp[i + 1][1]++; } else { dp[i + 1][1]--; } } if (dp[N][0] > 0 || dp[N][1] > 0){ tv2 = mid; } else { fv2 = mid; } } cout << tv2 << endl; }
Editor is loading...