[贪心] HDU 5500 Reorder the Books

题意

给定一个从1到n的乱序序列，每次取一个数到最前面，问最少多少次能使序列变为增序。

思路

先找到数n的位置，在n之前找n-1，若没找到n-1，则n-1需要操作，所有小于n-1的数均需要操作；若找到了n-1，再接着往前依次找n-2，n-3，。。。假如数k找不到了，那就是至少需要k次操作。

代码

// https://blog.csdn.net/ymrfzr/article/details/49048249 #include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <map> #include <queue> #include <set> #include <string> #include <vector> using namespace std; typedef long long ll; const int maxn = 20 + 10; int n; int book[ maxn ]; int main () { int T; scanf ( "%d", &T ); while ( T-- ) { scanf ( "%d", &n ); for ( int i = 0; i < n; ++i ) scanf ( "%d", &book[ i ] ); int key = n; for ( int i = n - 1; i >= 0; --i ) if ( key == book[ i ] ) --key; printf ( "%d\n", key ); } return 0; }