CF390B Inna, Dima and Song Solution

发布时间 2023-11-05 08:41:58作者: Ushio_Noa

转裁自我的洛谷博客 :https://www.luogu.com.cn/blog/653832/solution-cf390b

题目传送门

思路:

  1. 如果 $b_i \le 1$ 则无解。
  2. 如果 ceil((double)b[i]/2)>a[i],即最好情况下,两个人的音量平均,但是较大的音量还是大于 $a_i$。那么也是无解的。
  3. 否则,要使他们的乘积最大,两个数就要尽量接近。先除以 $2$,然后一个向上取整,一个向下取整即可。

特别地,因为 $10^6 \times 10^6 $ 会爆 int,所以 ans 要开 long long。

核心代码:

for(int i=1;i<=n;i++)
{
	if(ceil((double)b[i]/2)>a[i]||b[i]<=1)ans--;
	else ans+=ceil((double)b[i]/2)*floor((double)b[i]/2);
}