Vesterosun Dili#12425
Məsələnin müəllifi: | Matvii Hrytsyna |
Hazırlayan: | Matvii Hrytsyna |
Həll: | Matvii Hrytsyna |
İdeya
İxtiyari qarışdırmadan sonra da biz hələ də palindrom almaq istəyirik, buna görə ilkin massivdə elementlərin sırası vacib deyil — vacib olan yalnız onları cütlərə necə bölməyimizdir. Bu məsələ üçün əsas müşahidə odur ki, çevrə üzərində yanaşı hərfləri cütləşdirmək həmişə daha sərfəlidir. Buna əsasən, iki halı nəzərdən keçirək.
— cüt
Massivi azalmayan sırada çeşidləyin. Müşahidədən görə bilərik ki, optimal nəticə verə bilən elementləri cütlərə bölməyin iki yolu var.
({a}[1],{a}[2]),({a}[3],{a}[4]),...({a}[n-1n
({a}[2],{a}[3]),({a}[4],{a}[5]),...({a}[1],{a}[n
dist(x,y) ilə və hərflərini bərabər etmək üçün lazım olan minimum əməliyyat sayını işarə edək. Əlifba dövri olduğuna görə, dist(x,y) = min(m,m-|x-y|). Bu düsturdan istifadə edərək, iki variantın hər biri üçün qiyməti hesablayın və minimumu seçin.
— tək
Əvvəlcə və adlı iki massiv hesablayın. \text{pref}[i] = \text{pref}[i-2]+dist({a}[i],{a}[i-1]), 2\le i \le n üçün. Başqa sözlə, uzunluğu olan massivinin prefiksini cütlərə bölməyin qiymətidir, əgər təkdirsə, birinci elementi kənarda saxlamaqla. Eyni qaydada, \text{suff}[i] = \text{suff}[i+2]+dist({a}[i],{a}[i+1]). İndi yekun massivdə ortada olacaq elementi götürüb onun üçün cavabı hesablayın. Əgər təkdirsə, onda birinci üsulla cütlərə bölmənin qiyməti \text{pref}[i-1]+\text{suff}[i+1], ikinci üsulla isə \text{pref}[i-2]+ \text{suff}[i+2]+dist(a[1],a[n])+dist(a[i-1],a[i+1]) olur. Əgər cütdürsə, onda birinci üsulla cütlərə bölmənin qiyməti \text{pref}[i-2]+\text{suff}[i+2]+dist({a}[i-1],{a}[i+1]), ikinci üsulla isə \text{pref}[i-1]+\text{suff}[i+1]+dist({a}[1],{a}[n]) olur. Bundan əlavə, i=1 və i=n halları ayrıca işlənməlidir.
Ümumi mürəkkəblik çeşidləmə səbəbindən O(nlogn)-dir.
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e17;
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n);
for (auto &ai : a) cin >> ai;
if (n == 1) {
cout << 0 << '\n';
return;
}
sort(begin(a), end(a));
auto dist = [m](int x, int y) -> int {
return (int)min(abs(x - y), m - abs(x - y));
};
auto calc = [&](int l, int r) -> long long {
long long res1 = 0, res2 = 0;
for (int i = l; i <= r; i += 2) res1 += dist(a[i], a[i + 1]);
for (int i = l + 1; i < r; i += 2) res2 += dist(a[i], a[i + 1]);
res2 += dist(a[l], a[r]);
return min(res1, res2);
};
if (n % 2 == 0) {
long long res1 = 0, res2 = 0;
for (int i = 0; i < n; i++) {
if (i % 2 == 0 && i + 1 < n)
res1 += dist(a[i], a[i + 1]);
else if (i % 2 == 1 && i + 1 < n)
res2 += dist(a[i], a[i + 1]);
}
res2 += dist(a[n - 1], a[0]);
cout << min(res1, res2) << '\n';
} else {
long long ans = min(calc(0, n - 2), calc(1, n - 1));
vector<long long> pref(n + 1, 0), suff(n + 1, 0);
for (int i = 1; i < n; i++) {
if (i - 2 >= 0) pref[i] = pref[i - 2];
pref[i] += dist(a[i], a[i - 1]);
}
for (int i = n - 2; i >= 0; i--) {
suff[i] = suff[i + 2];
suff[i] += dist(a[i], a[i + 1]);
}
for (int i = 1; i < n - 1; i++) {
long long option_1 = 0, option_2 = 0;
if (i % 2 == 0) {
if (i > 0) option_1 = pref[i - 1];
option_1 += suff[i + 1];
if (i - 2 >= 0) option_2 += pref[i - 2];
option_2 += suff[i + 2];
option_2 += dist(a[i - 1], a[i + 1]);
option_2 += dist(a[0], a[n - 1]);
} else {
if (i > 2) option_1 += pref[i - 2];
option_1 += suff[i + 2];
option_1 += dist(a[i - 1], a[i + 1]);
option_2 = pref[i - 1];
option_2 += suff[i + 1];
option_2 += dist(a[0], a[n - 1]);
}
ans = min(ans, min(option_1, option_2));
}
cout << ans << '\n';
}
}
int main() {
int tt = 1;
cin >> tt;
while (tt--) solve();
}