Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 1e5 + 3;
- int n;
- int a[N];
- bool check_average(double x) {
- vector <double> dp(n + 1);
- dp[1] = a[1] - x;
- for (int i = 2; i <= n; i++) {
- double b = (double)a[i] - x;
- dp[i] = max(dp[i - 1], dp[i - 2]) + b;
- }
- return max(dp[n], dp[n - 1]) >= 0;
- }
- double find_average() {
- double l = 0, r = 1e9;
- for (int step = 0; step < 100; step++) {
- double md = (l + r) / 2;
- if (check_average(md))
- l = md;
- else
- r = md;
- }
- return l;
- }
- bool check_median(int x) {
- int cnt = 0;
- for (int i = 1; i <= n; i++) {
- if (a[i] >= x) cnt++;
- }
- vector <int> dp(n + 1);
- int zeros = 0;
- for (int i = 1; i <= n; i++) {
- if (a[i] < x) {
- zeros++;
- } else {
- cnt -= zeros / 2;
- zeros = 0;
- }
- }
- cnt -= zeros / 2;
- return cnt > 0;
- }
- int find_median() {
- int l = 1, r = 1e9;
- while (l <= r) {
- int md = (l + r) >> 1;
- if (check_median(md))
- l = md + 1;
- else
- r = md - 1;
- }
- return r;
- }
- int main(){
- cin >> n;
- for (int i = 1; i <= n; i++) {
- cin >> a[i];
- }
- cout << fixed << setprecision(10) << find_average() << endl;
- cout << find_median() << endl;
- }
Advertisement
Advertisement
Advertisement
RAW Paste Data
Copied
Advertisement