#PU892. USACO 2019 January Contest, Bronze — Problem 2. Sleepy Cow Sorting

    ID: 1514 传统题 文件IO:sleepy 2000ms 256MiB 尝试: 0 已通过: 0 难度: 普及 上传者: 标签>USACO赛事:jan19来源:usaco.orgscoring:equal_test_cases贪心排序

USACO 2019 January Contest, Bronze — Problem 2. Sleepy Cow Sorting

USACO 2019 January Contest, Bronze — Problem 2. Sleepy Cow Sorting

题目描述

Farmer John is attempting to sort his NN cows (1≤N≤1001 \leq N \leq 100), conveniently numbered 1…N1 \dots N, before they head out to the pastures for breakfast. Currently, the cows are standing in a line in the order p1,p2,p3,…,pNp_1, p_2, p_3, \dots, p_N, and Farmer John is standing in front of cow p1p_1. He wants to reorder the cows so that they are in the order 1,2,3,…,N1, 2, 3, \dots, N, with cow 11 next to Farmer John. The cows are a bit sleepy today, so at any point in time the only cow who is paying attention to Farmer John's instructions is the cow directly facing Farmer John. In one time step, he can instruct this cow to move kk paces down the line, for any kk in the range 1…N−11 \ldots N-1. The kk cows whom she passes will amble forward, making room for her to insert herself in the line after them. For example, suppose that N=4N=4 and the cows start off in the following order: FJ: 4, 3, 2, 1 The only cow paying attention to FJ is cow 44. If he instructs her to move 22 paces down the line, the order will subsequently look like this: FJ: 3, 2, 4, 1 Now the only cow paying attention to FJ is cow 33, so in the second time step he may give cow 33 an instruction, and so forth until the cows are sorted. Farmer John is eager to complete the sorting, so he can go back to the farmhouse for his own breakfast. Help him find the minimum number of time steps required to sort the cows.

输入格式

The first line of input contains NN. The second line contains NN space-separated integers, p1,p2,p3,…,pNp_1, p_2, p_3, \dots, p_N, indicating the starting order of the cows.

输出格式

A single integer: the number of time steps before the NN cows are in sorted order, if Farmer John acts optimally.

数据范围

(见题面原文)

样例

样例 1

4
1 2 4 3
3
Problem credits: Dhruv Rohatgi