Codeforces Round #323 (Div. 2) B. Robot's Task

简介:
B. Robot's Task
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Robot Doc is located in the hall, with n computers stand in a line, numbered from left to right from 1 to n. Each computer containsexactly one piece of information, each of which Doc wants to get eventually. The computers are equipped with a security system, so to crack the i-th of them, the robot needs to collect at least ai any pieces of information from the other computers. Doc can hack the computer only if he is right next to it.

The robot is assembled using modern technologies and can move along the line of computers in either of the two possible directions, but the change of direction requires a large amount of resources from Doc. Tell the minimum number of changes of direction, which the robot will have to make to collect all n parts of information if initially it is next to computer with number 1.

It is guaranteed that there exists at least one sequence of the robot's actions, which leads to the collection of all information. Initially Doc doesn't have any pieces of information.

Input

The first line contains number n (1 ≤ n ≤ 1000). The second line contains n non-negative integers a1, a2, ..., an (0 ≤ ai < n), separated by a space. It is guaranteed that there exists a way for robot to collect all pieces of the information.

Output

Print a single number — the minimum number of changes in direction that the robot will have to make in order to collect all n parts of information.

Sample test(s)
input
3
0 2 0
output
1
input
5
4 2 3 0 1
output
3
input
7
0 3 1 0 5 2 6
output
2
Note

In the first sample you can assemble all the pieces of information in the optimal manner by assembling first the piece of information in the first computer, then in the third one, then change direction and move to the second one, and then, having 2 pieces of information, collect the last piece.

In the second sample to collect all the pieces of information in the optimal manner, Doc can go to the fourth computer and get the piece of information, then go to the fifth computer with one piece and get another one, then go to the second computer in the same manner, then to the third one and finally, to the first one. Changes of direction will take place before moving from the fifth to the second computer, then from the second to the third computer, then from the third to the first computer.

In the third sample the optimal order of collecting parts from computers can look like that: 1->3->4->6->2->5->7.


解题思路:

用一个sum值记录一下他所已知的电脑信息的数量,然后一直判断,从前往后,从后往前

一直判断知道sum = = m,用两个标记值分别标记从前往后是否转向和从后往前是否转向,

然后输出结果,(转向的次数)

上代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;

#define MM(a) memset(a,0,sizeof(a))
#define MM1(a) memset(a, false, sizeof(a))
typedef long long LL;
typedef unsigned long long ULL;
const int maxn = 1e3+5;
const int mod = 1000000007;
const double eps = 1e-7;
const double pi = 3.1415926;

int arr[maxn];
bool flag[maxn];
int main()
{
    int m, k;
    while(cin>>m)
    {
        for(int i=0; i<m; i++)
            cin>>arr[i];
        int sum = 0, ret = 0;
        MM1(flag);
        ///memset(flag, false, sizeof(false));
        bool ok = false, yes=false;
        while(sum < m)
        {
            ///注意需要在这里判断,
            if(ok)
                ret++;
            ///在初始化一次
            ok = false;
            for(int i=0; i<m; i++)
            {
                ///cout<<9;
                if(arr[i]<=sum && !flag[i])
                {
                    k = i;
                    ok = true;
                    sum++;
                    flag[i] = true;
                }
            }
            for(int j=k-1; j>=0; j--)
            {
                if(arr[j]<=sum && !flag[j])
                {
                    yes = true;
                    sum++;
                    flag[j] = true;
                }
            }
            if(yes)
                ret++;
            ///初始化为false
            yes = false;
        }
        cout<<ret<<endl;
    }
    return 0;
}


目录
相关文章
Codeforces Round #192 (Div. 2) (330B) B.Road Construction
要将N个城市全部相连,刚开始以为是最小生成树的问题,其实就是一道简单的题目。 要求两个城市之间不超过两条道路,那么所有的城市应该是连在一个点上的,至于这个点就很好找了,只要找到一个没有和其他点有道路限制的即可。
40 0
|
机器学习/深度学习 算法 C++
|
C++
Codeforces Round #423 (Div. 2, rated, based on VK Cup Finals)爆零记
昨晚一个瓜皮说今晚有cf,听说是晚间场,我瞅了一眼,娃,VK Cup,上分的好机会,看着比赛时间就有点心酸了,0:35,当时一直在纠结要不要打的问题,当时想着应该不难吧,要不打一下吧,要不还是看看题先,如果容易就打,难的话就不打了好的吧!于是就这样愉快的决定了。
1116 0