首页 > 其他分享 >题解:CF2014C Robin Hood in Town

题解:CF2014C Robin Hood in Town

时间:2024-10-02 18:49:38浏览次数:7  
标签:Town int 题解 mid long coutn max Hood

分享一种二分答案做法。

先特判 \(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

相关文章

  • 题解:SP7973 ACPC10E - Sometimes, a penalty is good!
    比较简单的一道数学题。思路:计算小组赛的比赛总数。longlongstage1=G*T*(T-1)/2;每组有\(T\)个队伍,每个队伍都需要与其他\(T-1\)个队伍比赛,共有\(T\cdot(T-1)\)场比赛。共有\(G\)组,因此小组赛总比赛数为\(\frac{G\cdotT\cdot(T-1)}{2}\)。计算进入......
  • 题解:SP10242 ACPC11D - Dice on a Board
    思路递归生成所有的可能的筛子朝向,用DFS标记所有可达的位置,用dijkstra计算从起始位置到目标位置的最优路径,并确定在移动过程中能够获得的最大分数。generate函数generate用于生成所有可能的骰子朝向排列,\(mask\)作为参数,用于表示哪些数字已经被使用。使用二进制压缩。......
  • 题解:P9954 [USACO20OPEN] Cowntact Tracing B
    考虑暴力。枚举让每头牛都当一次“零号病人”和\(K\)的所有组合,模拟感染的过程,检查得出的病人是否和给出的一样即可。代码:#include<bits/stdc++.h>usingnamespacestd;boolinfectedd[101];intN,cowx[251],cowy[251];boolcheck(intpatient_zero,intK){ boolinfect......
  • 题解:SP9934 ALICE - Alice and Bob
    状态表示:使用两个变量来表示当前游戏的状态:\(a\)表示包含\(1\)个石子的堆的数量,\(b\)表示包含多于\(1\)个石子的堆的可操作次数。游戏策略:从包含多个石子的堆中取走一个石子,这会减少\(b\)。从包含\(1\)个石子的堆中取走一个石子,这会减少\(a\)。合......
  • 题解:P9939 [USACO21OPEN] Acowdemia III B
    考虑贪心。遍历每只奶牛:如果它最多与一头奶牛相邻,那么什么都不会发生。如果它与两头以上的奶牛相邻,那么它与两侧的两头奶牛相邻。将答案递增\(1\)。否则,如果正好有两头相邻的奶牛,我们就把它们配对。也就是说,将这对奶牛插入一组。代码:#include<bits/stdc++.h>usingname......
  • 题解:UVA1500 Alice and Bob
    状态表示:使用两个变量来表示当前游戏的状态:\(a\)表示包含\(1\)个石子的堆的数量,\(b\)表示包含多于\(1\)个石子的堆的可操作次数。游戏策略:从包含多个石子的堆中取走一个石子,这会减少\(b\)。从包含\(1\)个石子的堆中取走一个石子,这会减少\(a\)。合......
  • 题解:P9788 [ROIR 2020 Day2] 区域规划
    法1枚举\(a,b,c\),考虑到\(c\)的最小值为\(\max(1,\frac{(a\cdotb−n)}{b})\),所以直接剪枝即可通过。代码:#include<bits/stdc++.h>usingnamespacestd;intans,n,m;intmain(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m; for(i......
  • 题解:UVA124 Following Orders
    考虑深搜和拓扑排序。从入度为零的节点开始,逐步添加到当前的排列结果中,并在每一步递减相邻节点的入度。如果某个节点的入度变为零,就递归地将其添加到当前排列中。一旦达到排列的叶节点,就存储起来,并按字典顺序排序。代码:#include<bits/stdc++.h>usingnamespacestd;voidread......
  • 题解:UVA117 The Postal Worker Rings Once
    此题要求我们求欧拉回路的长度。使用Floyd算法计算图中任意两点之间的最短路径,对于度数为奇数的路口(最多有两个),找到它们之间的最短路径并将其加入总路径长度中。代码:#include<bits/stdc++.h>#defineINF1e8usingnamespacestd;intdegree[26];intpath[26][26];intal......
  • 题解:SP15553 STC00 - Hamsters
    首先,通过预处理计算每个名字的哈希值,然后利用哈希检查名字之间的最长公共前缀,从而确定从一个名字转移到另一个名字的最小代价。使用倍增动态规划计算转移的最小成本,\(f_{t,i,j}\)表示从名字\(i\)经过\(2^t\)步转移到名字\(j\)的最小代价,最后通过位运算处理\(M\)次转移的......