CodeForces-402B 题解

发表于2023-07-14更新于2023-07-14

题目传送门

一道枚举题……

数据范围非常小，考虑暴力枚举。枚举第一棵树的高度，如果按照这样排列需要的操作次数是最小的，就选用这棵树作为新的第一棵树的高度，然后求出剩下的树的高度。

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
#include <bits/stdc++.h>
#define ll long long
#define INF 1e9
using namespace std;
int n, k, maxn = -INF, maxl = -INF, top, q; // top 是新的第一个高度
int a[1005], b[1005];
signed main() {
    ios :: sync_with_stdio(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        maxn = max(maxn, a[i]); // 只需要枚举到最大值
    }
    for (int i = 1; i <= maxn; i++) {
        int cnt = i, sum = 0; // sum 是统计以 i 这个高度为开头有多少棵树不用进行操作
        if (i == a[1]) sum++; 
        for (int j = 2; j <= n; j++) {
            cnt += k;
            if (cnt == a[j]) sum++;
        }
        if (sum > maxl) { // 最多有多少棵树不操作
            maxl = sum;
            top = i;
        }
    }
    b[1] = top;
    int x = top + k;
    for (int i = 2; i <= n; i++) {
        b[i] = x;
        x += k;
    }
    for (int i = 1; i <= n; i++) {
        if (a[i] != b[i]) q++;
    }
    cout << q << "\n";
    for (int i = 1; i <= n; i++) {
        if (a[i] < b[i]) cout << "+ " << i << " " << b[i] - a[i] << "\n";    
        if (a[i] > b[i]) cout << "- " << i << " " << a[i] - b[i] << "\n";
    }
    return 0;
}