分享一种二分答案做法。
先特判 \(n=1\),\(n=2\),开始就有超过一半的人不高兴的情况。
然后二分 \(x\),计算新的和,新的平均值,如果有超过一半的人不高兴,就更新答案。
代码:
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<long long>a(n);
long long S=0;
long long a_max=0;
for(int i=0;i<n;++i){
cin>>a[i];
S+=a[i];
a_max=max(a_max,a[i]);
}
if(n==1||n==2){
cout<<-1<<endl;
continue;
}
long long unhappy_count=0;
double half_avg=1.0*S/(2*n);
for(int i=0;i<n;++i){
if(a[i]<half_avg){
unhappy_count++;
}
}
if(unhappy_count>n/2){
cout<<0<<endl;
continue;
}
long long left=0;
long long right=1e18;
long long result=-1;
while(left<=right){
long long mid=(left+right)/2;
long long new_S=S+mid;
double new_half_avg=1.0*new_S/(2*n);
long long new_unhappy_count=0;
for(int i=0;i<n;++i){
if(a[i]<new_half_avg){
new_unhappy_count++;
}
}
if(new_unhappy_count>n/2){
result=mid;
right=mid-1;
}else{
left=mid+1;
}
}
if(result==-1){
cout<<-1<<endl;
}else{
cout<<result<<endl;
}
}
return 0;
}
标签:Town,int,题解,mid,long,coutn,max,Hood
From: https://www.cnblogs.com/cly312/p/18444978