Epic Transformation | Codeforces

Epic Transformation

from Codeforces Round #710 (Div. 3)

Time limit：2s

Memory limit：256MB

這個題目時有技巧的

先舉個例子

有四個數：2 3 1 1

我們會先配對2 3的話，會剩下1 1，但是如果配對2 1和3 1那麼久可以不剩

是以這個題我們應該先對最多的數進行配對。

ac代碼：

#include<iostream>
#include<algorithm>
using namespace std;
int t,n;
int x[200005];
void solve(){
    int maxn = 0;
    int i,j;
    for(i = 1;i <= n;){
        for(j = i + 1;j <= n;++j){
            if(x[j] != x[i]){
                maxn = max(maxn,j - i);i = j;break;
            }
        }
        if(j == n + 1){
            maxn = max(maxn,j - i);break;
        }
    }
    if(maxn * 2 <= n)
        cout<<n % 2<<"\n";
    else
        cout<<maxn - (n - maxn)<<"\n";
}
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        for(int i = 1;i <= n;++i)
            cin>>x[i];
        sort(x + 1,x + n + 1);
        solve();
    }
    return 0;
}