Average and Median

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.3 kB
5
Indexable
Never
#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;
}