首页 > 其他分享 >Codeforces Round 824 (Div. 2) B. Tea with Tangerines

Codeforces Round 824 (Div. 2) B. Tea with Tangerines

时间:2023-09-09 21:11:48浏览次数:46  
标签:lceil frac Tea Codeforces leq 2a Tangerines 橘子 rceil

有 \(n\) 块橘子皮,第 \(i\) 块大小为 \(a_i\) 。在一部操作中可以把一块橘子皮分成两块,即这块橘子皮为 \(x\) ,让 \(x\) 变为 \(y, z(x = y + z)\) 。

希望对于任意两块橘子皮,他们相差严格小于两倍。即两块中更小的为 \(x\) ,更大的为 \(y\) ,有 \(2x > y\) 。最少需要执行多少步操作。

观察一:显然关键在于最小块橘子皮,假设为第 \(x\) 块。只需保证其它橘子皮小于他的两倍,且中间过程不会出现比 \(a_x\) 更小的橘子皮即可。即 \(\forall i, i \neq x,\ s.t.\ 2a_x \leq a_i\) 且 \(a_i \geq a_x\) 。

观察二:可以贪心地考虑尽量分出最大块,将所有 \(a_i\) 分为 \(2a_x - 1\) 。

  • \(2a_x - 1 \mid a_i\) 时操作数为 \(\frac{a_i}{2a_x - 1} - 1\) 。操作数比块数少 \(1\) 。
  • \(2a_x \nmid a_i\) 时,操作数为 \(\lceil \frac{a_i}{2a_x - 1} \rceil - 1\) 。
    • 并不是真的切出最后余下的一块 \(r,(a_i \equiv r(\mod 2a_x - 1))\) ,可能存在 \(r < a_x\) 打乱全局。
    • 性质:逐渐分小时,最后一块为 \(2a_x - 1 + r,(1 \leq r < 2a_x - 1)\) 。考虑到取值范围在 \([2a_x + 0, 4a_x - 3]\) 。显然存在 \(h, w\) 满足 \(h + w = 2a_x - 1 + r\) 且 \(a_x \leq h,w \leq 2a_x - 1\) 。
    • 即考虑末尾反悔的合法性。(末尾反悔和中途反悔通常区分比较明显)

则答案为 \(\sum_{i = 1, i \neq x}^{n} (\lceil \frac{a_i}{2a_x} \rceil - 1) = \sum_{i = 1, i \neq x}^{n} (\lceil \frac{a_i}{2a_x} \rceil) - n + 1\)。

代入 \(x\) 也能符合,可化简为 \(\sum_{i = 1}^{n} (\lceil \frac{a_i}{2a_x} \rceil) - n\)

view
#include <bits/stdc++.h>
void solve() {
	int n; std::cin >> n;
	std::vector<int> a(n+1);
	for (int i = 1; i <= n; i++) std::cin >> a[i];
	int x = std::min_element(a.begin() + 1, a.end()) - a.begin();
	long long ans = 0; for (int i = 1; i <= n; i++) if (i != x) {
		ans += (a[i] + (2 * a[x] - 1) - 1) / (2 * a[x] - 1);
	}
	std::cout << ans - n + 1 << '\n';
}
signed main() {
	int _ = 1; std::cin >> _;
	while (_--) solve();
	return 0;
} 

标签:lceil,frac,Tea,Codeforces,leq,2a,Tangerines,橘子,rceil
From: https://www.cnblogs.com/zsxuan/p/17690137.html

相关文章

  • 【题解】Educational Codeforces Round 143(CF1795)
    A.TwoTowers题目描述:有\(a,b\)两座由红蓝色方块垒成的塔,其中\(a\)的高度为\(n\);\(b\)的高度为\(m\),用R代表红色;用B代表蓝色。你可以多次把其中一座顶端的方块移到另一座的顶端(可以不移动)。问有没有一种方法可以使两座塔中均没有连续的同颜色方块。题目分析:可以......
  • Codeforces Round 827 (Div. 4) C. Stripes
    在一个\(8\times8\)的网格上,一开始无色。每次一整行或一整列地染色,后染的颜色会覆盖前染的颜色。染色方式有两种,一种是横着染\(R\)色,一种是竖着染\(B\)色。给出最终染色的网格,问最后染的色是哪种。对每行开\(R\)计数器、每列开\(B\)计数器。遍历行、列,如果计数器的......
  • Codeforces Round 832 (Div. 2) B. BAN BAN
    给一个正整数\(n\),定义\(S{n}\)为字符串\(BAN\)复制\(n\)次。比如\(S(3)=BANBANBAN\)。可以对\(S(n)\)执行任意次以下操作:选择\(i,j(1\leqi,j\leq3n,i\neqj)\)。\(swap(s_i,s_j)\)。希望\(BAN\)不作为一个子序列出现在\(S(n)\)中,输出最小交换......
  • [题解] Codeforces Round 895 (Div. 3) F~G
    CodeforcesRound895(Div.3)F~GF.SellingaMenageri考虑如何让卖出的价格翻倍,那么自然是从\(i\toa_i\)。通过这样连边,我们可以发现,边集构成了基环树森林。显而易见的是,如果不考虑环,那么图就是拓扑图,按照拓扑关系跑一遍,就可以使得所有点价值最多。现在考虑环上的问题......
  • Codeforces Round 895 (Div. 3)
    CodeforcesRound895(Div.3)比赛链接A.TwoVessels题目链接给你三个数a,b,c每次把a,b中较大的数中拿去最多等于c的数给较小的数字,问多少次使得a,b两个数字相等。A思路:可恶,在写的过程中出现了精度丢失的情况,导致出现了好多问题,问多少次使得a和b相等,就是\[abs(a-b)/2/c向上取......
  • live555做流媒体服务器时解决rtp over udp模式下, 客户端没有发送teardown时直接关闭
    在我们使用live555作为RTSP服务器时,客户端在rtpoverudp模式下,rtsp客户端没有发送teardown而直接断开连接时需要等待65秒才回调关闭的问题。分析问题在RTSPClientConnection中没有保存相应的session值,所以在RTSPClientConnection断开时,并没有删除相应的RTSPClientSession;解......
  • 2023-09-08 类型“any[]”的参数不能赋给类型“SetStateAction<never[]>”的参数 ==》
    如题,react+taro+ts小程序开发,在给一个变量设值的时候报错,如:初始化变量const[isChecked,setCheck]=useState([]);设值setCheck([123]);原因:默认[]会被ts推导成never[]类型。解决方案:把useState改为useState<any[]>即可,即:const[isChecked,setCheck]=useStat......
  • CodeForces 960G Bandit Blues
    洛谷传送门CF传送门发现设排列最大值位置为\(i\),那么\([1,i]\)只可能存在前缀最大值,\([i,n]\)只可能存在后缀最大值。由此设\(f_{i,j}\)为长度为\(i\)的排列,前缀最大值有\(j\)个的方案数,有转移:\[f_{i,j}=f_{i-1,j-1}+(i-1)f_{i-1,j}\]意思是每......
  • Codeforces Round 406 (Div. 2) D. Legacy 线段树优化建图
    传送门题目大意:给定n个点,m个操作,和起点s。其中n和q大于等于1小于等于1e5,s大于等于1小于等于n其中m个操作有三种情况:  1.输入1uvval表示从u号点向v号点连一个权值为val的有向边,其中1<=u<=n,1<=v<=n,1<=val<=1e9  2.输入2ulrval表示从u号点......
  • Educational Codeforces Round 154 (Rated for Div. 2)
    EducationalCodeforcesRound154(RatedforDiv.2)比赛链接我都快忘了还有这一场比赛,今天打开cf看见这场比赛正好有时间就补了!!!2023.9.3也许是出去玩了一下午脑子不够用了??怎么现在读题都有一点读不懂了!!!2023.9.4我靠这场我怎么感觉没什么思路呢????A题PrimeDeletion题目链接......