HDU - 5122 K.Bro Sorting(贪心)

时间:2022-10-06 07:42:16

题目大意:给你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;
}