代码
注意
get函数中&是引用,一定要加,就是在本数据上进行修改。
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
long long getgcd(long long a,long long b){//求最大公因数
return (b==0?a:getgcd(b,a%b));
}
void get(long long &fm,long long &fz,long long m,long long z){//fz/fm表示前面相同的总和,z表示剩余没有改变的数据
long long gcd=getgcd(fz*m*m+fm*z*z,fm*m*m);
fz=(fz*m*m+fm*z*z)/gcd;
fm=fm*m*m/gcd;
return ;
}
int main(){
while(~scanf("%d%d",&n,&m)){
int i,a[n];
int tot=0;
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1,greater<int>());//从大到小排序
for(i=1;i<n;i++){
int x=a[i]-a[i+1];//存储两个数之间得差值
if(tot+x*i<=m)//这个一定要加
tot+=x*i;
else
break;
}
long long rem=m-tot;
long long fz=a[i]*i-rem;//分子
long long fm=m*i;//分母
long long gcd=getgcd(fz*fz*i,fm*fm);//因为分数都是最简的,所以要把最大公因数求出来
fz=fz*fz*i/gcd;
fm=fm*fm/gcd;
for(i=i+1;i<=n;i++){
get(fm,fz,m,a[i]);//每加一个数就更新一次
}
if(fm==1)
printf("%lld\n",fz);
else
printf("%lld/%lld\n",fz,fm);
}
return 0;
}
#include<algorithm>
using namespace std;
int n,m;
long long getgcd(long long a,long long b){//求最大公因数
return (b==0?a:getgcd(b,a%b));
}
void get(long long &fm,long long &fz,long long m,long long z){//fz/fm表示前面相同的总和,z表示剩余没有改变的数据
long long gcd=getgcd(fz*m*m+fm*z*z,fm*m*m);
fz=(fz*m*m+fm*z*z)/gcd;
fm=fm*m*m/gcd;
return ;
}
int main(){
while(~scanf("%d%d",&n,&m)){
int i,a[n];
int tot=0;
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1,greater<int>());//从大到小排序
for(i=1;i<n;i++){
int x=a[i]-a[i+1];//存储两个数之间得差值
if(tot+x*i<=m)//这个一定要加
tot+=x*i;
else
break;
}
long long rem=m-tot;
long long fz=a[i]*i-rem;//分子
long long fm=m*i;//分母
long long gcd=getgcd(fz*fz*i,fm*fm);//因为分数都是最简的,所以要把最大公因数求出来
fz=fz*fz*i/gcd;
fm=fm*fm/gcd;
for(i=i+1;i<=n;i++){
get(fm,fz,m,a[i]);//每加一个数就更新一次
}
if(fm==1)
printf("%lld\n",fz);
else
printf("%lld/%lld\n",fz,fm);
}
return 0;
}