比赛简介

• 题数：4道
• 时间：3个小时
• 总分：400分
• 难度：2道J2，2道S2
• 晋级标准:前100名

开始考试

先来讲题。

A题签到题忽略…… CD题目前没能力解决，也忽略。

B：Mila的木棍

题面

$\text{Mila}$ 找到了 $n$ 根木棍，她将这 $n$ 根木棍排成一行形成一个序列 $a$，但是她发现此时的序列可能是不优美的。

假如木棍的长度从左到右形成一个不下降序列，那么 $\text{Mila}$ 认为这些木棍才是优美的。因此，$\text{Mila}$ 学习了一种可以削减木棍长度的魔法：对一个区间 $[l,r]$ 使用一次魔法，可以将这个区间内所有木棍的长度减 $1$。

不下降序列：对于所有 $1\leq j < i \leq n$，满足 $a[j] \leq a[i]$。例如序列 $3,3,4,5$ 就是不下降序列。

现在 $\text{Mila}$ 想要知道：至少需要使用多少次魔法才可以将这些木棍变得优美？

输入格式

第一行一个整数 $n$，表示木棍的数量。

第二行 $n$ 个以空格隔开的整数，表示这个序列，第 $i$ 根木棍的长度为 $a_i$。

输出格式

输出共一行一个整数，表示答案。

数据范围

对于 $20%$ 的数据，满足 $n,a_i\leq 10$。

对于 $40%$ 的数据，满足 $n\leq 10^3$。

对于另外 $20%$ 的数据，保证 $a$ 是一个不递增序列。

对于 $100%$ 的数据，满足 $1\leq n\leq 10^6,1\leq a_i\leq 10^9$。

样例输入

1
2

3
1 3 2

样例输出

1

1

满分解

对于一个$i$，如果$a_i \gt a_{i + 1}$，那么为了形成不下降序列，至少有$a_i - a_{i + 1}$次削减的区间的右端点需位于$i$。

所以操作数至少为$\sum_{i=1}^{n - 1} max(a_i - a_{i + 1}, 0)$。

 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

#include <iostream>

using namespace std;

typedef long long LL;


int main() {
    freopen("stick.in", "r", stdin);
    freopen("stick.out", "w", stdout);
    int n;
    cin >> n;

    LL prev, ans;
    cin >> prev;
    n -- ;
    while (n -- ) {
        int a;
        cin >> a;
        if (prev > a) {
            ans += prev - a;
        }
        prev = a;
    }

    cout << ans << endl;
    return 0;
}

总结

要用草稿纸

不用草稿纸基本只能做签到题，况且这场比赛难度确实不低。