Atcoder-abc334_c 题解

发表于2023-12-29更新于2023-12-29

题目传送门

一道贪心题……

数量为 22 的袜子不用考虑，因为最好的情况就是相同颜色的配一对。

我们只需要考虑那 kk 种只有 11 个的袜子，如果 kk 为偶数，答案为相邻两数之差之和；如果 kk 为奇数，就枚举删掉一个数，让剩下的数按照 kk 为偶数的情况做，最后取一个最小值。这个过程可以使用前缀和维护。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>

const long long IMX = 1ll << 30;
const long long LMX = 1ll << 60;
const long long MOD = 998244353;

using ll = long long;
using i128 = __int128;
using ld = long double;
using f128 = __float128;

namespace xvl_ { 
    #define SP(n, x) std :: setprecision(n) << std :: fixed << x
    #define REP(i, l, r) for (auto i = (l); i <= (r); i++)
    #define PER(i, r, l) for (auto i = (r); i >= (l); i--)
    #define DEBUG(x) std :: cerr << #x << " = " << x << '\n'
    #define SZ(x) (x.size())
    #define fst first
    #define snd second
    template <typename T> T Max(T a, T b) { return a > b ? a : b; } template <typename T, typename... Args> T Max(T a, Args... args) { return a > Max(args...) ? a : Max(args...); }
    template <typename T> T Min(T a, T b) { return a < b ? a : b; } template <typename T, typename... Args> T Min(T a, Args... args) { return a < Min(args...) ? a : Min(args...); }
}
using namespace std;
using namespace xvl_;
ll n, k, ans;
ll a[200005], sum[200005], pre[200005];
int main() {
    // freopen("InName.in", "r", stdin);
    // freopen("OutName.out", "w", stdout);
    ios :: sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> k;
    REP(i, 1, k) {
        cin >> a[i];
        if (i & 1) sum[i] = sum[i - 1] - a[i];
        else sum[i] = sum[i - 1] + a[i];
    }
    PER(i, k, 1) {
        if (i & 1) pre[i] = pre[i + 1] - a[i];
        else pre[i] = pre[i + 1] + a[i];
    }
    if (k & 1) {
        ans = LMX;
        REP(i, 1, k) ans = Min(ans, sum[i - 1] - pre[i + 1]);
    }
    else {
        for (int i = 2; i <= n; i += 2) ans += a[i] - a[i - 1];
    }
    cout << ans;
    return 0;
}