codeforces 323 div.2

本文从WordPress迁移而来, 查看全部WordPress迁移文章

B.题目，有n个电脑，放在一排，从左到右编号1~n，每个电脑有一个值ai，表示至少收集了ai个信息，才能打开这个电脑（没打开一个电脑收集1个信息）。

一开始走路的方向是从左到右的，可以随时换方向（从右到左走，或者再换回来），当向一个方向走的时候，不一定要相邻着走。

从左往右走的时候，可以从1号走到5号等等，前提是走到该电脑时要能打开该电脑。问打开所有电脑，最少改变方向多少次。注意一开始方向是从左到右的，如果第1步要从右到左走，也算更改方向。

容易想到的一个性质，如果往一个方向走了，一定走到底，再换方向，这样一定更优，所以整个走路的过程就是，从一头走到另一头，尽可能打开能打开的电脑，然后再从这头走到那头。枚举启动时的方向即可

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


using namespace std;

#define LL long long
#define INF 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define MAXN 1010

bool vis[MAXN];
int n, a[MAXN];

int solve(int st, int delta) {
    memset(vis, false, sizeof vis);
    int cnt = 0, ans = 0, sum = 0;
    while (cnt < n) {
        int idx = st;
        while (0 <= idx && idx < n) {
            if (vis[idx]) {
                idx += delta;
            }
            else {
                if (sum >= a[idx]) {
                    vis[idx] = true;
                    sum += 1;
                    idx += delta;
                    cnt += 1;
                    //printf("idx: %d\n", idx);
                }
                else {
                    idx += delta;
                }
            }
            //printf("[%d]\n", idx);
        }
        if (cnt >= n) {
            break;
        }
        ans += 1;
        if (idx < 0) {
            st = 0;
            delta = 1;
        }
        else {
            st = n - 1;
            delta = -1;
        }
    }
    return ans;
}

int main() {
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
        int ans1 = solve(0, 1);
        //int ans2 = 100;
        int ans2 = solve(n-1, -1);
        printf("%d\n", min(ans1, ans2+1));
    }
    return 0;
}