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;
}