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