题解：P6485 [COCI 2010/2011 #4] PROSJEK

· · 题解

P6485 [COCI 2010/2011 #4] PROSJEK

这是本蒟蒻写的第一篇题解，大佬请勿喷。

题意

你有 5 种数字：1,2,3,4,5。

你需要从中选取尽量少的数字，使得这些数之和的平均数为 P。

需要注意的是，这 5 种数字每种有任意多个。

思路

依题意，易得方程 \frac{x+2y+3z+4u+5v}{x+y+z+u+v}=P，

我们只需求出 x+y+z+u+v 最小的一个解。

因为实数 P 可以化成一个最简分数 \frac{p}{q}，

所以原方程化为 \frac{x+2y+3z+4u+5v}{x+y+z+u+v} =\frac{p}{q}，

所以 x+y+z+u+v 最小为 q，x+2y+3z+4u+5v 为 p。

接下来只需求出 x,y,z,u,v 即可。

我们可以假设全都是 5 即 v=q，再微调便可以得出方程的解。

代码

#include<bits/stdc++.h>
#define int long long 
using namespace std;
string s;//使用字符串读入
int p,q=1;
int c[5]={0};
signed main(){
    bool f=0;
    cin>>s;
    for(int i=0;i<s.size();i++){
        if(s[i]!='.')
            p=p*10+(s[i]-'0');
        else
            f=1;
        if(f)
            q*=10;
    }//化成分数
    if(s[0]!=0)
        q/=10;
    int gcd=__gcd(p,q);
    p/=gcd;
    q/=gcd;//约分
    int x=5*q-p;//假设全是5会多出多少
    int n=x/q;
    int m=x%q;
    c[4-n]=q-m;
    c[4-n-1]=m;//调整数据
    printf("%lld %lld %lld %lld %lld",c[0],c[1],c[2],c[3],c[4]);
    return 0;//完美结束
}

若有疏忽，请及时提出。