Fork me on GitHub

程序设计竞赛:魔法师排队

发表于 | 分类于 | | 次阅读
有n个魔法师在排队买魔法面包，每个魔法师都有自己的魔力值，用一个正整数表示。 魔法师都不喜欢排队，如果任意时刻某个魔法师发现前面的魔法师的魔力值比自己小，那么这个魔法师就会用法术把前面的人传送到异空间。 请输出有多少个魔法师会被传送到异空间。

Problem B. 魔法师排队

时间限制 2000 ms
内存限制 64 MB

题目描述

有n个魔法师在排队买魔法面包，每个魔法师都有自己的魔力值，用一个正整数表示。 魔法师都不喜欢排队，如果任意时刻某个魔法师发现前面的魔法师的魔力值比自己小，那么这个魔法师就会用法术把前面的人传送到异空间。 请输出有多少个魔法师会被传送到异空间。

输入数据

第一行为一个正整数n，代表魔法师的人数。 接下来一行位n个正整数，第i个正整数ai代表队伍中第i个魔法师的魔力值。（第1个魔法师在队头，第n个魔法师在队尾）
1 <= n <= 1000000
1 <= ai <= 100000000

输出数据

被传送到异空间的魔法师个数

样例输入

1
2
5
4 5 1 3 2

样例输出

1
2

题解

一开始的想法是：找从第一个魔法师到最后一个魔法师中的拥有最大魔力值的魔法师max_index，那么位于它之前的魔法师都将会被传送走，此具有最大魔力值的魔法师会留下来；接着寻找从max_index + 1到最后一个魔法师之间的拥有最大魔力值的魔法师，进行同样的操作，依次循环下去，直到剩下最后一个魔法师为止（最后一个魔法师肯定会留下来）；然而结果却超时了。于是换了种思维方式，既然是位于魔法师前面且比其魔力值小的魔法师会被传送走，那么最后一个魔法师肯定会留下来；直接定义一个存储最大魔力值的变量max_num，初始化为最后一个魔法师的魔力值，从后向前倒序遍历，如果当前魔法师的魔力值比max_num小，那么就把他传送走；否则，更新最大魔力值。

TLE代码

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

using namespace std;

const int maxN = int(1e6 + 10);
int n, a[maxN], l, r, max_index, cont;
int i;

int main() {
    cin >> n;
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    l = 0; r = n;
    while(l < r) {
        vector<int> v(a + l, a + r);
        auto max_value = max_element(v.begin(), v.end());
        max_index = distance(begin(v), max_value);
        cont += max_index;
        l = l + max_index + 1;
    }
    cout << cont << endl;
    return 0;
}

AC代码

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

using namespace std;

const int maxN = int(1e6 + 10);
int n, a[maxN], max_num, cont;
int i;

int main() {
    cin >> n;
    for (i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    max_num = a[n];
    for (i = n - 1; i > 0; i--) {
        if (a[i] < max_num) {
            cont++;
        } else {
            max_num = a[i];
        }
    }
    cout << cont << endl;
    return 0;
}
0%