• E. Beautiful Array
  • 原题链接
  • 题目
  • 思路
  • 代码

E. Beautiful Array

原题链接

题目

思路

代码

// https://codeforces.com/contest/1986/problem/E
#include <bits/stdc++.h>
#define caseT \
    int T;    \
    cin >> T; \
    while (T--)
using namespace std;
using ll = long long;
void solve() {
    ll n, k, ans = 0, num2 = 0;
    cin >> n >> k;
    vector<ll> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];
    sort(nums.begin(), nums.end());
    map<ll, vector<ll>> H;
    for (ll num : nums) H[num % k].push_back(num);
    for (auto &[key, p] : H) {
        if (p.size() & 1 && ++num2 >= 2) {
            cout << "-1" << endl;
            return;
        }
        int len = p.size();
        vector<vector<ll>> dp(len, vector<ll>(2));
        dp[0][0] = INT_MAX;
        if (len > 1) dp[1] = {(p[1] - p[0]) / k, INT_MAX};
        for (int i = 2; i < len; i++) {
            ll t = (p[i] - p[i - 1]) / k;
            if (i & 1) {
                dp[i][0] = min(dp[i - 2][0], dp[i - 1][1]) + t;
            } else {
                dp[i][1] = dp[i - 1][0];
                dp[i][0] = min(dp[i - 2][0], dp[i - 2][1]) + t;
            }
        }
        ans += (len & 1) ? min(dp[len - 1][1], dp[len - 1][0]) : dp[len - 1][0];
    }
    cout << ans << endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    caseT solve();
    return 0;
}