Xiaoyuan raised a cute black dog, but couldn’t think of any special name at the moment, so he simply called it “CuteBlack Dog,” or CBD for short. CBD is very smart and can recognize Arabic numerals, which made Xiaoyuan love it even more.
Under Xiaoyuan’s careful care, CBD gradually gained weight. Seeing this as a potential problem, Xiaoyuan designed a game for CBD to play and exercise at the same time.
The game Xiaoyuan designed works like this: He prepares N paper cards, each sequentially numbered from 1 to N, and arranges them in a random order from left to right on the ground. He then lets CBD run from the leftmost card to the rightmost card, and then back from the rightmost to the leftmost card, continuously going back and forth. The rule is that whenever CBD encounters the card with the smallest number among the remaining cards, CBD must take that card; otherwise, it cannot be taken.
For example, suppose there are 5 cards initially arranged from left to right as 1, 4, 2, 5, 3. The first time CBD runs from the left end to the right, it will take cards 1, 2, and 3 along the way. When CBD returns to the left, it will take card 4. Finally, on the next trip to the right, it will take card 5.
Xiao Yuan wants to ask you to help calculate the minimum number of times CBD needs to change direction in order to pick up all the cards, given the initial arrangement of the cards.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The input consists of two lines:
1. The first line contains a positive integer N, which indicates the number of cards. 2. The second line contains N positive integers separated by spaces, representing the values written on the cards from left to right. It is guaranteed that each number from 1 to N appears exactly once. | The output should consist of a single integer representing the number of times CBD needs to change direction (reverse course) in order to pick up all the cards. |
| 2 1 2 | 0 |
| 5 1 4 2 5 3 | 2 |
| 4 4 3 2 1 | 1 |
| 1 1 | 0 |
Thought Process
Store the data using a Pair, where the first field represents the number at the current position, and the second field represents the position of that number. Store this data in an array and sort it. After sorting, iterate through the array from start to end, keeping track of whether you are currently moving right or left. If the position of the current number is in the opposite direction of the current movement, increment the answer by 1 and change direction.
Sample Code－ZeroJudge B684: Dog Game
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
pair<int, int> num[1000005] = {};
for (int i = 0; i<N; i++) {
int tmp;
cin >> tmp;
num[i] = make_pair(tmp, i);
}
sort(num, num+N);
string sign = "Big";
int position = 0, ans = 0;
for (int i = 0; i<N; i++) {
if (sign == "Big") {
if (num[i].second >= position) position = num[i].second;
else {
ans++;
sign = "Small";
position = num[i].second;
}
}
else {
if (num[i].second < position) position = num[i].second;
else {
ans++;
sign = "Big";
position = num[i].second;
}
}
}
cout << ans << "\n";
}
//ZeroJudge B684
//Dr. SeanXD