算法练习专栏——Acwing周赛练习——第146场周赛

A：讲课速度（枚举）

某班有 n 个学生，学习能力分别为 a1,a2,…,an。

为了保证全班学生都能跟得上讲课，该班的讲课速度恰好等于班级内学习能力最低的学生的学习能力。

请你计算并输出，该班的讲课速度。

输入格式

第一行包含整数 n。

第二行包含 n 个整数 a1,a2,…,an。

输出格式

一个整数，表示该班的讲课速度。

数据范围

前 3 个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤100，1≤ai≤1001。

输入样例：

1
2
3
4 5 6

输出样例：

1
4

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
const int INF = 110;
int n;

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n;
    int k = INF;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        k = min(k, x);
    }
    
    cout << k;
    return 0;
}

B：截断数组（贪心）

给定一个长度为 n 的整数数组 a1,a2,…,an。

如果一个整数数组恰好包含相同数量的奇数元素和偶数元素，就称该数组为一个平衡数组。

给定的数组 a 恰好就是一个平衡数组。

现在，我们可以将该数组从中间截断，从而得到若干个非空子数组。

关于截断操作：

  • 每次操作都需要一定成本，具体来说，将数组从 ai 和 ai+1 之间截断，所需成本为 |ai−ai+1|。
  • 所有进行的截断操作的总成本不得超过 B。
  • 所有截断得到的子数组都必须也是平衡数组。

请你计算，在满足所有要求的前提下，最多可以进行多少次截断操作。

输入格式

第一行包含两个整数 n,B,。

第二行包含 n 个整数 a1,a2,…,an。

输出格式

一个整数，表示在满足所有要求的前提下，可以进行的截断操作的最多次数。

数据范围

前 4个测试点满足 2≤n≤6。
所有测试点满足 2≤n≤100，1≤B≤100，1≤ai≤100。

输入样例1：

1
2
6 4
1 2 5 10 15 20

输出样例1：

1
1

输入样例2：

1
2
4 10
1 3 2 4

输出样例2：

1
0

输入样例3：

1
2
6 100
1 2 3 4 5 6

输出样例3：

1
2

代码

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
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;
const int N = 110;
int a[N], b[N], c[N], h[N];
int n, m;

int main()

{
    ios::sync_with_stdio(false),cin.tie(0), cout.tie(0);
    cin >> n >> m;
    int k = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        h[i] = x;
        if (x % 2) {
            a[i] = a[i - 1] + 1;
            b[i] = b[i - 1];
        }
        else {
            b[i] = b[i - 1] + 1;
            a[i] = a[i - 1];
        }
        
    }
    for (int i = 2; i < n; i += 2) {
        if (a[i] == b[i] && a[n] - a[i] == b[n] - b[i]) {
            c[k++] = abs(h[i] - h[i + 1]);
        }
    }
    
    sort(c, c + k);
    
    int res = 0, kk = 0;
    for (int i = 0; i < k; i++) {
        res += c[i];
        if (res <= m) kk++;
    }
    
    cout << kk;
    return 0;
}

C：双端队列（贪心+分类讨论）

给定一个长度为 n 的双端队列 a1,a2,…,an。

作为双端队列，我们既可以从队列的左端弹出元素，也可以从队列的右端弹出元素。

我们希望弹出尽可能多的元素，并要求所有弹出元素按照弹出顺序进行排列，刚好可以构成一个严格递增的序列。

请你计算，最多可以弹出多少个元素。

输入格式

第一行包含整数 n。

第二行包含 n 个整数 a1,a2,…,an。

输出格式

输出一个整数 k，表示最大弹出元素数量。

数据范围

前 66测试点满足 1≤n≤10。
所有测试点满足 1≤n≤2×10^5^，1≤ai≤2×10^5^。

输入样例1：

1
2
5
1 2 4 3 2

输出样例1：

1
4

输入样例2：

1
2
7
1 3 5 6 5 4 2

输出样例2：

1
6

输入样例3：

1
2
3
2 2 2

输出样例3：

1
1

输入样例4：

1
2
4
1 2 4 3

输出样例4：

1
4

代码一

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
using namespace std;
const int N = 2e5 + 10;
typedef long long LL;
int a[N];
int n, ma, k;

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n;
    int l = 0, r = n - 1;
    for (int i = 0; i < n; i++) cin >> a[i];
    while (l <= r) {
        if (a[l] < a[r]) {
            if (a[l] > ma) {
                ma = a[l];
                l++;
                k++;
            } else if (a[r] > ma) {
                ma = a[r];
                r--;
                k++;
            } else {
                break;
            }
        } else if (a[r] < a[l]){
            if (a[r] > ma) {
                ma = a[r];
                r--;
                k++;
            } else if (a[l] > ma) {
                ma = a[l];
                l++;
                k++;
            } else {
                break;
            }
        } else {
            if (a[l] > ma){
                int cntl = 1, cntr = 1;
                for (int i = l + 1; i <= r; i++){
                    if (a[i] > a[i - 1]) {
                        cntl++;
                    } else {
                        break;
                    }
                }
                for (int i = r - 1; i >= l; i--) {
                    if (a[i] > a[i + 1]) {
                        cntr++;
                    } else {
                        break;
                    }
                }
                k += max(cntl, cntr);
                break;
            } else {
                break;
            }
            if (a[l] <= ma) {
                break;
            } else {
                ma = a[l];
                k++;
            }
            if (l == r) break;
            if (a[l + 1] > a[r - 1]) {
                if (a[r - 1] > ma) {
                    r--;    
                } else if (a[l + 1] > ma) {
                    l++;
                } else {
                    l++;
                }
            } else if (a[l + 1] < a[r - 1]){
                if (a[l + 1] > ma) {
                    l++;
                } else if (a[r - 1] > ma) {
                    r--;
                } else {
                    l++;
                }
            } else {
                l++;
            }
        }
    }
    cout << k;
    return 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
using namespace std;
const int N = 2e6 + 10;
typedef long long LL;
LL a[N];
LL n, ma, k;

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n;
    LL l = 0, r = n - 1;
    for (int i = 0; i < n; i++) cin >> a[i];
    while (l <= r) {
        if (a[l] < a[r]) {
            if (a[l] > ma) {
                ma = a[l];
                l++;
                k++;
            } else if (a[r] > ma) {
                ma = a[r];
                r--;
                k++;
            } else {
                break;
            }
        } else if (a[r] < a[l]){
            if (a[r] > ma) {
                ma = a[r];
                r--;
                k++;
            } else if (a[l] > ma) {
                ma = a[l];
                l++;
                k++;
            } else {
                break;
            }
        } else {
            if (a[l] > ma){
                int cntl = 1, cntr = 1;
                for (int i = l + 1; i <= r; i++){
                    if (a[i] > a[i - 1]) {
                        cntl++;
                    } else {
                        break;
                    }
                }
                for (int i = r - 1; i >= l; i--) {
                    if (a[i] > a[i + 1]) {
                        cntr++;
                    } else {
                        break;
                    }
                }
                k += max(cntl, cntr);
                break;
            } else {
                break;
            }

        }
    }
    cout << k;
    return 0;
}