T3

T3.

当数组中所有的元素都是大于1的，那么一定合法，我们可以把前 $n - 1$ 个数全变成1，多出来的部分加到最后一个 数上面。所以我们只需要考虑1的情况，我们可以令 $cnt1$ 代表1的个数， $cnt$ 代表非1的数和1的差值的和，我们只需要把 $cnt$ 分配给 $cnt1$ 个1即可。

例如

• 不合法的极端情况

  4
  1 1 1 3
  

  这个样例不合法，因为3最多拿出2出来给前面的1，所以至少有一个1和之前一样。

• 合法的情况

  4
  1 1 1 4
  

  这个样例是合法的，因为刚好可以从最后一个元素抽出3出来均匀分配给前面3个元素，使得数组中所有元素都不一样。

#include <bits/stdc++.h>
 #define int long long
using namespace std;
   
const int N = 200010;
int a[N], n, m, k;
 
void solve(){
    cin >> n;
    int cnt1 = 0, cnt = 0;
    for(int i = 1; i <= n; i ++ ){
        cin >> a[i];
        if(a[i] == 1) cnt1 ++;
        else cnt += a[i] - 1;
    }
    if(cnt >= cnt1) cout << "^_^\n";
    else cout << ":-(\n";
}
 
signed main(){
    int tt = 1;
    cin >> tt;
    while(tt -- ){
        solve();
    }
    return 0;
}