题目链接:
http://uva.onlinejudge.org/index.phpoption=com_onlinejudge&Itemid=8&page=show_problem&problem=1078
题目意思:
给出n个人的花费情况,以美元为单位,精确到美分,然后要你求出最小的总交易额使得每人付出的钱数之差在1美分。
解题思路:
先求出平均每人应该支付的钱数,去掉美分后面的,精确到美分,记为aver,每人应该支付的应该是aver或aver+0.01,然后统计比该钱数大的人数ca,比较sum-aver*n与ca*0.01的大小,尽量让出钱多的人付aver+0.01的份额,这钱使付钱少的的人尽量出aver的份额,这样可以使得总的交易额达到比较小的水准。具体详见代码。
代码:
#include<iostream> #include<cmath> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<algorithm> #include<vector> #include<map> #define eps 1e-6 #define INF (1<<20) #define PI acos(-1.0) using namespace std; int main() { int n; double money[1200]; while(scanf("%d",&n)&&n) { double sum=0; for(int i=1;i<=n;i++) { scanf("%lf",&money[i]); sum+=money[i]; } double aver=(int)(sum/n*100)*.01; double ans=0; int ca=0; //计数大于aver钱数的人数 for(int i=1;i<=n;i++) if(money[i]<aver) ans+=aver-money[i]; //如果付钱少了,则应该付钱 else if(money[i]>aver) ca++; if(sum-aver*n==0||sum-aver*n<ca*.01) printf("$%.2lf\n",ans); else printf("$%.2lf\n",ans+sum-aver*n-ca*.01);//尽量让付钱多的人付aver+0.01的份额 } return 0; }