中位数贪心+分组，CF 433C - Ryouko‘s Memory Note

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

---

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

433C - Ryouko's Memory Note

---

二、解题报告

1、思路分析

改变 x 只会影响所有值为 x 的下标 及其前后下标的贡献

我们考虑分组—— vals[x] = { 所有x出现位置前后不为x 的值 }

那么分组考虑

对于x，我们要把x调为何值最优呢？

vals[x]的中位数

那么我们分组考虑维护最小值

2、复杂度

时间复杂度： O(MlogM)空间复杂度：O(N + M)

3、代码详解

 ​

#include <bits/stdc++.h>
// #include <ranges>using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;constexpr int P = 998244353;
constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;void solve() {int n, m;std::cin >> n >> m;std::vector<int> a(m);std::vector<std::vector<int>> vals(n);i64 tot = 0;for (int i = 0; i < m; ++ i) {std::cin >> a[i];-- a[i];if (i && a[i] != a[i - 1]) {vals[a[i]].push_back(a[i - 1]);vals[a[i - 1]].push_back(a[i]);tot += abs(a[i] - a[i - 1]);}}i64 res = tot;for (int i = 0; i < n; ++ i) {if (vals[i].empty()) continue;std::ranges::sort(vals[i]);int m = vals[i][vals[i].size() / 2];i64 s = 0, t = 0;for (int x : vals[i])s += abs(x - m), t += abs(x - i);if (tot + s - t < res) res = tot + s - t;}std::cout << res;
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;// std::cin >> t;while (t--) {solve();}return 0;
}