a590. 桑義的完美陣列 - 彰化精誠中學

內容

桑義是個完美主義者，他現在正在研究如何將一個陣列變得完美。

一個長度為$n$的完美陣列$A$必須符合以下條件：對於所有$0\leq i, j\leq n-1; i\ne j$，$A[i]\geq2$且$\gcd(A[i],A[j])=1$。

為了將所有陣列都變得完美，桑義研究出了一台能量轉換機，支援以下兩種操作：

將陣列內的某個數字減1，機器提取出1份能量
機器消耗1份能量，將陣列內某數字加1 (至少要有1份能量才能執行此操作)

機器一開始都沒有能量。

即便有能量轉換機在手，桑義發現仍有一些陣列無法變得完美。對於這些陣列，桑義想知道至少要移除幾個元素後，才能讓該陣列能夠透過能量轉換機變得完美。

輸入說明

輸入第一行包含$N$。
接下來一行有$N$個數，第$i$個數$x_i$代表陣列的第$i$個元素。

$1\le N\le2\cdot10^5$
$2\le x_i\le 10^9$

Subtask:

20%: $N=2$
10%: $N=3$
70%: 無其他限制。

輸出說明

輸出一個數字$k$ $(0\leq k\leq N)$，代表至少需要移除$k$個元素，這個陣列才能透過能量轉換機的操作變得完美。

範例輸入 #1

4
2 3 2 4

範例輸出 #1

範例輸入 #2

3
5 5 5

範例輸出 #2

範例輸入 #3

3
2 98 2

範例輸出 #3

測資資訊：

記憶體限制： 128 MB
公開測資點#0 (10%): 0.8s , <1K
公開測資點#1 (10%): 0.8s , <1K
公開測資點#2 (10%): 0.8s , <1K
公開測資點#3 (10%): 0.8s , <1M
公開測資點#4 (10%): 0.8s , <1M
公開測資點#5 (10%): 0.8s , <1M
公開測資點#6 (10%): 0.8s , <10M
公開測資點#7 (10%): 0.8s , <10M
公開測資點#8 (10%): 0.8s , <10M
公開測資點#9 (10%): 0.8s , <10M

提示：

範例輸入1，可將$2$與$4$移除剩下$[2,3]$，剛好是一個完美陣列。

範例輸入2，不需要移除任何元素，即可透過以下操作轉換成完美陣列（最後剩下3份能量）：
$[5,5,5]\to[5,4,5]\to[4,4,5]\to[3,4,5]$

範例輸入3，不需要移除任何元素，即可透過以下操作轉換成完美陣列（最後剩下0份能量）：
$[2,98,2]\to[2,97,2]\to[2,97,3]$

標籤:

出處:

明達 [管理者：

pusapphire@g... (pusapphire)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」