Featured image of post 2022计蒜之道初赛(第一场)

2022计蒜之道初赛(第一场)

比赛简介

  • 题数: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;
}

总结

要用草稿纸

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