自动搬运

查看原文

来自洛谷，原作者为

	Math_rad_round 旋转卡壳有2^4种读法，你知道吗？||NOIP退役苕皮

搬运于2025-08-24 21:30:39，当前版本为作者最后更新于2020-03-12 16:02:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原题 P1818

简要翻译

N个可取1-10的整数的平均数四舍五入保留一位小数是A，现在要你再放上x个整数使平均数四舍五入保留一位小数降至B，给你X,Y,N，求x最小值

这道题既然范围很大(n>1000000,T>10000)，很明显就不能硬模拟，要数学推导

我们既然要将平均数降至Y，那么肯定只有全放1才可以更好地降低平均数 否则把高的改成1肯定平均更小

首先先忽略精度问题，列出算式，设仍要投x张票可以达到目的的话

原先数的总和就是AN,而新的数总和为x，最后就一共有N+x个数。这些数平均数要小于等于B，那么算式就是

两边乘N+x，因为都是正数，所以不用变号

移项合并，得

所以两边除1-B，得到以下式子（因为1-B恒负，所以变号）

因为x为整数，所以ceil向上取整即可

现在讨论精度问题，最坏情况下，真实的平均数是A+0.0499999......（这样初始分数最大）最后目标是B+0.049999999......（同理，因为四舍五入，这样就可以达到平均数）

所以上式中的A要用输入值加上0.0499999......，B也同理

这就是为什么1-B恒负而不会出现0的原因（本来就B≥1,加上0.0499999......后必定>1）

但是这题有坑，因为N个数中每个数都是整数，所以AN也是整数，必须先取整

另外，0.49999999......中9的数目多了会当成0.05，少了不准，在这可以用12个9

此外，A和B因为不可能超过10，所以都要对10取min

再之后，A可能小于等于B,这时要回答0

求解原式的过程是O(1)，所以T组数据复杂度是O(T)比二分更快

上AC代码

#include<iostream>
#include<cmath>
#define LL long long 
#define LD long double 
using namespace std;

int main(){
	LD a,b;
	LL n;
	while(cin>>a>>b>>n){
		if(a<=b){
			cout<<"0"<<endl;
			continue;
		}
		a=a+(LD)0.04999999999999;
		a=min((LD)10.0,a);
		b=b+(LD)0.04999999999999;
		b=min((LD)10.0,b);
		
		LL f=a*n;
		LD d=((LD)(b*n-f)/((LD)1-b));
		
		cout<<(LL)ceil(d)<<endl;
	}
   return 0;
} 

数学推导就是好