給定一個循環數組?a1,a2,…,ana1?,a2?,…,an?。
你可以對?aa?至多執行?n?1n?1?次以下操作：
- 設?mm?為?aa?的當前大小，你可以選擇任何兩個相鄰的元素，其中前一個不大于后一個（特別地，amam??和?a1a1??是相鄰的，amam??是前一個），并刪除其中的一個。換句話說，選擇一個整數?ii?(1≤i≤m1≤i≤m) 使得?ai≤a(imodm)+1ai?≤a(imodm)+1??成立，然后從?aa?中刪除?aiai??或?a(imodm)+1a(imodm)+1??之一。
你的目標是找到使得?aa?中所有元素相等所需的最小操作次數。
輸入
每個測試包含多個測試用例。第一行包含測試用例的數量?tt?(1≤t≤5001≤t≤500)。接下來是測試用例的描述。
每個測試用例的第一行包含一個整數?nn?(1≤n≤1001≤n≤100) — 數組?aa?的長度。
每個測試用例的第二行包含?nn?個整數?a1,a2,…,ana1?,a2?,…,an??(1≤ai≤n1≤ai?≤n) — 數組?aa?的元素。
輸出
對于每個測試用例，輸出一行包含一個整數：使得?aa?中所有元素相等所需的最小操作次數。
示例
| Inputcopy | Outputcopy |
|---|---|
7 1 1 3 1 2 3 3 1 2 2 5 5 4 3 2 1 6 1 1 2 2 3 3 8 8 7 6 3 8 7 6 3 6 1 1 4 5 1 4 | 0 2 1 4 4 6 3 |
注意
在第一個測試用例中，aa?中只有一個元素，因此我們無法進行任何操作。
在第二個測試用例中，我們可以執行以下操作使得?aa?中所有元素相等：
- 選擇?i=2i=2，刪除?a3a3?，然后?aa?將變為?[1,2][1,2]。
- 選擇?i=1i=1，刪除?a1a1?，然后?aa?將變為?[2][2]。
可以證明，我們無法使用少于?22?次操作使得?aa?中所有元素相等，因此答案是?22。
//找規律，總數減去最多相等數的個數
#include<bits/stdc++.h>
using namespace std;
map<int,int>mapp;
int main(){int t;cin>>t;while(t--){mapp.clear();int n,maxn=-1;cin>>n;int h=n;while(h--){int k;cin>>k;mapp[k]++;maxn=max(mapp[k],maxn);}cout<<n-maxn<<endl;}
} ?
