h162 - 最少的操作數

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算將給定的整數陣列轉換為非嚴格遞增序列所需的最少操作次數。操作定義為將陣列中的任意元素替換為任意正整數。

解題思路

本題可以使用貪心策略結合二分搜尋來解決。核心思想是維護一個非嚴格遞增的子序列，遍歷輸入陣列，對於每個元素，如果它可以擴展當前子序列（即大於等於子序列的最後一個元素），則直接將其添加到子序列中。否則，使用二分搜尋找到子序列中第一個大於該元素的位置，並用該元素替換該位置的元素。最終，需要操作的次數等於原始陣列的長度減去子序列的長度。

程式碼中 DP 陣列用於儲存非嚴格遞增的子序列。it 變數追蹤子序列的長度。對於每個輸入元素 a[i]，如果 a[i] 大於或等於 DP[it-1]，則直接將 a[i] 添加到子序列的末尾，it 加一。否則，使用 lower_bound 找到 DP 陣列中第一個大於或等於 a[i] 的元素的位置，並用 a[i] 替換該位置的元素。最後，n - it 就是最少的操作次數。

複雜度分析

• 時間複雜度: O(n log n)
• 空間複雜度: O(n)

程式碼

#include <iostream>
using namespace std;
int DP[100005],n,a[100005];
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	while(cin >> n){
		for(int i=0;i<n;++i){
			cin >> a[i];
			DP[i]=0;
		}
		int it=0;
		for(int i=0;i<n;++i){
			if(it==0||a[i]>=DP[it-1])
				DP[it++]=a[i];
			else
				DP[lower_bound(DP,DP+it,a[i])-DP]=a[i];
		}
		cout << n-it << "\n";
	}
}