Untitled

 avatar
unknown
plain_text
3 years ago
2.4 kB
3
Indexable
#include <iostream>
#include <vector>
using namespace std;

typedef long double ld;

int main() {
	cout.precision(20);
	int n;
	cin >> n;
	vector<int> arr(n);
	vector<int> pref_min(n), pref_max(n), suff_min(n), suff_max(n);
	for (int& i : arr) cin >> i;
	for (int i = 0; i < n; i++) {
		if (i == 0) {
			pref_min[i] = arr[i];
			pref_max[i] = arr[i];
		}
		else {
			pref_min[i] = min(pref_min[i - 1], arr[i]);
			pref_max[i] = max(pref_max[i - 1], arr[i]);
		}
	}
	for (int i = n - 1; i >= 0; i--) {
		if (i == n - 1) {
			suff_min[i] = arr[i];
			suff_max[i] = arr[i];
		}
		else {
			suff_min[i] = min(arr[i], suff_min[i + 1]);
			suff_max[i] = max(arr[i], suff_max[i + 1]);
		}
	}

	vector<pair<ld, ld>> answer(n + 1, { 1e18, 0 });
	for (int k = 1; k <= n; k++) {
		if (k == n) {
			answer[k] = { 0, 1 };
		}
		else {
			ld pmin = pref_min[n - k - 1];
			ld pmax = pref_max[n - k - 1];
			ld smin = suff_min[n - k];
			ld smax = suff_max[n - k];
			
			// first case pmax and pmin
			ld left_border = max(ld(0), 1.0 - pmax / smax);
			ld right_border = 1.0 - pmin / smin;

			if (left_border <= right_border) {
				if (pmax - pmin <= answer[k].first) {
					answer[k].first = pmax - pmin;
					answer[k].second = right_border;
				}
			}

			// second case pmax and smin
			left_border = max(1.0 - pmin / smin, 1.0 - pmax / smax);
			left_border = max(ld(0), left_border);
			
			if (left_border <= 1) {
				if (pmax - smin * (1 - left_border) <= answer[k].first) {
					answer[k].first = pmax - smin * (1 - left_border);
					answer[k].second = left_border;
				}
			}

			// third case smax and pmin
			right_border = min(1 - pmax / smax, 1 - pmin / smin);
			if (right_border >= 0) {
				if (smax * (1.0 - right_border) - pmin <= answer[k].first) {
					answer[k].first = smax * (1.0 - right_border) - pmin;
					answer[k].second = right_border;
				}
			}

			// fourth case smax and smin
			right_border = 1 - pmax / smax;
			left_border = max(ld(0), 1 - pmin / smin);
			if (left_border <= right_border) {
				if (smax * (1 - right_border) - smin * (1 - right_border) <= answer[k].first) {
					answer[k].first = smax * (1 - right_border) - smin * (1 - right_border);
					answer[k].second = right_border;
				}
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		cout << answer[n - i + 1].second << ' ';
	}
	cout << '\n';
}
Editor is loading...