HDU - 5122 K.Bro Sorting(贪心)

题目大意：给你N个数字，要求你将这N个数字进行排序，有一种排序操作，挑选一个数，往右移动，直到碰到大于该数的数
问最少要操作几次

解题思路：从右往左扫，只有最高位都到位置了，才能移动最低位，不然中途就会被卡掉
用pos表明扫到那个位置了，用Max代表该位置应该要放什么数
讨论一下
1.如果val[pos] < Max，表示本来该位置应该是Max的，可是该数却比Max小，这就要将所有[val[pos] + 1, Max] 的所有数进行移动了，接着更新Max ＝ val[pos ] - 1，表示下一个位置就要放Max了

2.如果val[pos] > Max,这就不用管了，因为我们前面已经计算在内了，所以直接跳过

3.如果val[pos] == Max，表示符合，Max–

#include <cstdio>
#include <cstring>
const int N = 1000010;

int val[N];
int n, cas = 1;
void init() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &val[i]);
}

void solve() {
    int pos = n, Max = n, ans = 0;
    while (pos) {
        if (val[pos] < Max ) {
            ans += Max - val[pos];
            Max = val[pos] - 1;
        }
        if (val[pos] == Max) Max--;
        pos--;
    }
    printf("Case #%d: %d\n", cas++, ans);
}

int main() {
    int test;
    scanf("%d", &test);
    while (test--) {
        init();
        solve();
    }
    return 0;
}