P1818电影投票数论题解

Math_rad_round · 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，那么算式就是

\frac{AN+x}{N+x} \leq B

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

AN+x\leq BN+Bx

移项合并，得

(1-B)x\leq BN-AN

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

x\geq\frac{BN-AN}{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;
}

~~数学推导就是好~~

P1818电影投票 数论 题解

P1818电影投票数论题解