Advertisement
Mirbek

E - Average and Median (Atcoder)

Jan 28th, 2022
710
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 1e5 + 3;
  6.  
  7. int n;
  8. int a[N];
  9.  
  10. bool check_average(double x) {
  11.     vector <double> dp(n + 1);
  12.     dp[1] = a[1] - x;
  13.     for (int i = 2; i <= n; i++) {
  14.         double b = (double)a[i] - x;
  15.         dp[i] = max(dp[i - 1], dp[i - 2]) + b;
  16.     }
  17.     return max(dp[n], dp[n - 1]) >= 0;
  18. }
  19.  
  20. double find_average() {
  21.     double l = 0, r = 1e9;
  22.     for (int step = 0; step < 100; step++) {
  23.         double md = (l + r) / 2;
  24.         if (check_average(md))
  25.             l = md;
  26.         else
  27.             r = md;
  28.     }
  29.     return l;
  30. }
  31.  
  32. bool check_median(int x) {
  33.     int cnt = 0;
  34.     for (int i = 1; i <= n; i++) {
  35.         if (a[i] >= x) cnt++;
  36.     }
  37.     vector <int> dp(n + 1);
  38.     int zeros = 0;
  39.     for (int i = 1; i <= n; i++) {
  40.         if (a[i] < x) {
  41.             zeros++;
  42.         } else {
  43.             cnt -= zeros / 2;
  44.             zeros = 0;
  45.         }
  46.     }
  47.     cnt -= zeros / 2;
  48.     return cnt > 0;
  49. }
  50.  
  51. int find_median() {
  52.     int l = 1, r = 1e9;
  53.     while (l <= r) {
  54.         int md = (l + r) >> 1;
  55.         if (check_median(md))
  56.             l = md + 1;
  57.         else
  58.             r = md - 1;
  59.     }
  60.     return r;
  61. }
  62.  
  63. int main(){
  64.     cin >> n;
  65.  
  66.     for (int i = 1; i <= n; i++) {
  67.         cin >> a[i];
  68.     }
  69.  
  70.     cout << fixed << setprecision(10) << find_average() << endl;
  71.     cout << find_median() << endl;
  72. }
  73.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement