Мова Вестероса#12425
Автор задачі: | Матвій Грицина |
Підготував: | Матвій Грицина |
Розбір: | Матвій Грицина |
Ідея
Після довільного перемішування ми все одно хочемо отримати паліндром, тому порядок елементів у початковому масиві не важливий — важливо лише як ми їх розіб'ємо на пари.Ключове спостереження для цієї задачі полягає в тому, що нам завжди вигідно парувати сусідні по колу букви.Виходячи з цього розглянемо два випадки.
— парне
Відсортуємо масив за неспаданням.З спостереження видно що у нас є два способи розбити елементи на пари які можуть давати оптимальний результат.
({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) — мінімальну кількість операцій,щоб зробити букви та однаковими. Оскільки алфавіт циклічний то dist(x,y) = min(m,m-|x-y|). Користуючись цією формулою порахуємо кожен з варіантів та виберемо мінімальний
— непарне
Спочатку порахуємо два масиви та .\text{pref}[i] = \text{pref}[i-2]+dist({a}[i],{a}[i-1]),для 2\le i \le n.Іншими словами — вартісь розбиття на пари префіску масива довжини і ми залишашаємо один перший елемент якщо — непарне. Аналогічно \text{suff}[i] = \text{suff}[i+2]+dist({a}[i],{a}[i+1]).Тепер переберемо елемент який в фінальному масиві буде стояти посередині і порахуємо для нього відповідь. Якщо — непарне то вартість розбиття на пари першим спосібом дорівнює \text{pref}[i-1]+\text{suff}[i+1], а другим \text{pref}[i-2]+ \text{suff}[i+2]+dist(a[1],a[n])+dist(a[i-1],a[i+1]). Якщо ж — парне то вартість розбиття на пари першим спосібом — \text{pref}[i-2]+\text{suff}[i+2]+dist({a}[i-1],{a}[i+1]),а другим \text{pref}[i-1]+\text{suff}[i+1]+dist({a}[1],{a}[n]). Крім того варто окремо обробити випадок коли i=1 і i=n.
Загальна асимптотика — O(nlogn) через сортування.
#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();
}