2 条题解
-
1
【试题分析】 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。 【参考代码】
#include<bits/stdc++.h> #define LL long long #define LD long double LD a,b; LL n; int main() { freopen("film.in","r",stdin); freopen("film.out","w",stdout); while (scanf("%llf%llf%lld",&a,&b,&n)!=EOF) { //如果a<=b,例如:2.0<=2.5,不需要再投票就已经满足条件 if(a<=b) { printf("0\n"); continue; } a=a+(LD)0.04999999999999;//解决精度问题 if(a>(LD)10.0) a=(LD)10.0;//A因为不可能超过10,所以都要对10取min //a=min((LD)10.0,a); b=b+(LD)0.04999999999999; if(b>(LD)10.0) b=(LD)10.0;//B因为不可能超过10,所以都要对10取min //b=min((LD)10.0,b); int f=a*n;//AN也是整数,必须先取整 LD d=((LD)(b*n-f)/((LD)1-b));//根据公式求解 printf("%lld\n",(LL)ceil(d));// } }
信息
- ID
- 1366
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- 递交数
- 49
- 已通过
- 6
- 上传者