《算法周练5》C：序列最小化

贪心：
首先注意题目说这个数列肯定是1-n的一个全排列。
那么说明这个数列一开始的数都是1~n中的,并且最小的是1.
那么,很显然最后的结果肯定全部为1.
因为想要替换为全部都一样,且每次替换都是在变小,那么最后肯定是全部为1才能实现.
所以我们直接用1去替换更优.为什么呢？
因为如果用其他的数去替换,最终还是要被替换成1,这样还多了不必要的中间替换步数.所以可知用1替换更优.
那么就枚举一开始的那段区间,然后不断向左向右延伸,最后比较其中最小的即可.

int a[N];
int main()
{
    int n,k,pos,ans = INF;sdd(n,k);
    for(int i=1;i<=n;++i){sd(a[i]);if(a[i] == 1) pos = 1;}
    for(int i=max(1,pos-k+1);i<=pos;++i)//枚举第一个区间左端点L,注意可能<1.所以控制一下左边界
    {
        int L = i,r = i+k-1,ma = 1;
        while(1)//延伸到最右边,可以发现的是超出的时候说明可以将起点往里移一点而一步达成,所以本质上都是1步
        {
            if(r >= n) break;
            r = r+k-1;ma++;
        }
        while(1)//延伸到最左边
        {
            if(L <= 1) break;
            L = L-k+1;ma++;
        }
        ans = min(ans,ma);
    }
    pr(ans);
    system("pause");
    return 0;
}