# Untitled

unknown
plain_text
2 years ago
4.4 kB
1
Indexable
Never
```#include <iostream>
#include <vector>
using namespace std;

typedef long double ld;
typedef long long ll;

ll gcd(ll a, ll b) {
if (a == 0) return b;
return gcd(b % a, a);
}

struct Fraction {
ll a, b;

Fraction(ll a, ll b) {
this->a = a;
this->b = b;
}

Fraction operator-(Fraction other) {
ll x = a * other.b - other.a * b;
ll y = b * other.b;
ll g = gcd(abs(x), abs(y));
return { x / g, y / g };
}

bool operator<=(Fraction other) {
Fraction res = other - (*this);
return res.a >= 0;
}

bool operator<(Fraction other) const {
Fraction res = other - (*this);
return res.a > 0;
}
};

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<Fraction, ld>> answer(n + 1, { Fraction(1e18, 1), 0 });
for (int k = 1; k <= n; k++) {
if (k == n) {
answer[k] = { Fraction(0, 1), 1 };
}
else {
ll pmin = pref_min[n - k - 1];
ll pmax = pref_max[n - k - 1];
ll smin = suff_min[n - k];
ll smax = suff_max[n - k];

// first case pmax and pmin
Fraction left_border = max(Fraction(0, 1), Fraction(1, 1) - Fraction(pmax, smax));
Fraction right_border = Fraction(1, 1) - Fraction(pmin, smin);

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

// second case pmax and smin
left_border = max(Fraction(1, 1) - Fraction(pmin, smin), Fraction(1, 1) - Fraction(pmax, smax));
left_border = max(Fraction(0, 1), left_border);

if (left_border <= Fraction(1, 1)) {
left_border.a *= smin;
Fraction res = Fraction(pmax, 1) - left_border;
left_border.a /= smin;
}
}

// third case smax and pmin
right_border = min(Fraction(1, 1) - Fraction(pmax, smax), Fraction(1, 1) - Fraction(pmin, smin));
if (Fraction(0, 1) <= right_border) {
Fraction tmp = (Fraction(1, 1) - right_border);
tmp.a *= smax;
Fraction res = tmp - Fraction(pmin, 1);
}
}

// fourth case smax and smin
right_border = Fraction(1, 1) - Fraction(pmax, smax);
left_border = max(Fraction(0, 1), Fraction(1, 1) - Fraction(pmin, smin));
if (left_border <= right_border) {
Fraction tmp1 = Fraction(1, 1) - right_border;
tmp1.a *= smax;
Fraction tmp2 = Fraction(1, 1) - right_border;
tmp2.a *= smin;
Fraction res = tmp1 - tmp2;