內容
給定一長度為 n 的整數陣列 arr (index從0開始)，每次操作可以選擇任意一個i位於[0,n) 使得arr[i]變為任意的正整數。
求最少需要幾次操作可以使得arr變為非嚴格遞增的序列。
輸入說明
多筆測資
每筆測資有兩行
第一行是一個整數n代表陣列的長度(1<=n<=10^5)
第二行包含n個整數，以空格隔開，代表陣列對應的值(1<=arr[i]<=n)
輸出說明
輸出最少的操作數
範例輸入
#1
5 5 4 3 2 1 6 4 1 5 2 6 2
範例輸出
#1
4 3
測資資訊：
記憶體限制：
512
MB
公開 測資點#0 (33%): 0.5s , <1M
公開 測資點#1 (33%): 0.5s , <10M
公開 測資點#2 (34%): 0.7s , <10M
公開 測資點#0 (33%): 0.5s , <1M
公開 測資點#1 (33%): 0.5s , <10M
公開 測資點#2 (34%): 0.7s , <10M
提示 ：
第一筆測資將arr[0],arr[1],arr[3],arr[4]都換成3，使arr變成[3,3,3,3,3]，最少需要4次操作
第二筆測資將arr[0]換成1,arr[2]換成2,arr[5]換成8，使arr變成[1,1,2,2,6,8]，最少需要3次操作
---
是這題 https://leetcode.com/problems/minimum-operations-to-make-the-array-k-increasing/ 的簡化版。
測資有問題可以留言或私信作者。
2022/2/4 更新測資，卡掉O(n^2)的解法。
標籤:
出處:
[管理者：
s1082942@g.n
...
(sellie)
]