「沉默魔女」莫妮卡．艾瓦雷特
因為非常的怕生，不敢在人前講話，所以練習無詠唱魔法
沒想到她成為了是世界上唯一一位能使用無詠唱魔法的魔術師，也是單槍匹馬擊退傳說黑龍的英雄
也是利迪爾王國魔法師的頂點「七賢者」之一
魔法有點像數學，不同的魔法式就有點像是數學式子一樣，只要把魔法式解開就能發出魔法，而詠唱就是幫助解開魔法的方式，理論上無詠唱是不可能的，但莫妮卡的思考效能極高，這也使他能夠不依賴詠唱，達成瞬時的魔法發動。
$samson$轉生到利迪爾王國後非常的崇拜沉默魔女，他也想要學習無詠唱魔法，但$samson$的腦袋沒有莫妮卡的那種能力，所以他決定依靠現代科技的力量，用程式處理魔法式，現在有一個魔法式如下。請你幫忙$samson$寫一個程式處理這個問題。
給你一長度為$n$的正整數數列$a_1,a_2,......,a_n$
你可以對她進行下面的操作
$\implies$選擇任意整數$x$，對於所有滿足$a_i = x$的$i$，使$a_i$成為$0$
請你找出最小操作次數使數列為遞增的數列(不是嚴格遞增，可以等於)
請仔細看提示，不同子題可能會有完全不同的解法
第一行為一正整數$t$，代表有$t$筆測資
每筆測資的第一行為一正整數$n$，代表數列長度為$n$
每筆測資的第二行為$n$個正整數，代表數列$a_1,a_2,.....a_n$，(題目保證滿足所有$i$，$1 \leq a_i \leq n$)
對每筆測資輸出最小操作次數(以換行結尾)
4 3 3 3 2 4 1 2 1 2 4 3 4 2 3 1 1
1 2 3 0
公開 測資點#0 (10%): 1.0s , <1M
公開 測資點#1 (10%): 1.0s , <1M
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 1.0s , <50M
公開 測資點#4 (10%): 1.0s , <50M
公開 測資點#5 (10%): 1.0s , <50M
公開 測資點#6 (10%): 1.0s , <50M
公開 測資點#7 (10%): 1.0s , <50M
公開 測資點#8 (10%): 1.0s , <50M
公開 測資點#9 (10%): 1.0s , <50M
以[3 3 2]為例，選擇x=3,變成[0,0,2],操作一次
以[1 2 1 2]為例，選擇x = 1和x = 2,變成[0 0 0 0],操作兩次
對於30%測資
$1 \leq t \leq 10^2$
$1 \leq n \leq 10^2$
不保證任意$i,j(i \neq j)$，$a_i \neq a_j$(也就是會數列中會有重複的數)
對於30%測資
$1 \leq t \leq 10^3$
$1 \leq n \leq 10^4$
保證任意$i,j(i \neq j)$，$a_i \neq a_j$(也就是會數列中不會有重複的數)
對於40%測資
$1 \leq t \leq 10^3$
$1 \leq n \leq 10^4$
不保證任意$i,j(i \neq j)$，$a_i \neq a_j$(也就是會數列中會有重複的數)
記得IO優化
5/1號 測資加強
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||