{"id":116,"date":"2011-08-09T23:05:00","date_gmt":"2011-08-09T15:05:00","guid":{"rendered":"http:\/\/wangkaixuan.tech\/?p=116"},"modified":"2020-06-03T23:06:24","modified_gmt":"2020-06-03T15:06:24","slug":"hdu-3866-moonfangs-birthday","status":"publish","type":"post","link":"http:\/\/www.wangkaixuan.tech\/?p=116","title":{"rendered":"hdu 3866 Moonfang&#8217;s Birthday"},"content":{"rendered":"\n<pre class=\"wp-block-code\"><code>\/*\n\u5173\u952e\uff1a\u5bf9\u5b58\u653enum\u548cmoney\u7684\u8282\u70b9\u8fdb\u884c\u4e8c\u7ea7\u6392\u5e8f \n\u539f\u6587\uff1a\u201cIf there is still ambiguity,\n those who come first in the list pay more.\u201d \n*\/\n#define LOCAL\n#include&lt;iostream>\n#include&lt;cstdio>\n#include&lt;cmath>\n#include&lt;cstring>\n#include&lt;cstdlib>\n#include&lt;iomanip>\n#include&lt;string>\n#include&lt;algorithm>\n#include&lt;ctime>\n#define N 10005\nusing namespace std;\ntypedef struct \n{\n    int num,money;    \n}Node;\nNode pay&#91;N]; \nint moneycmp(const void *p,const void *q)\n{\n     if(((Node *)p)->money==((Node *)q)->money)\n         return ((Node *)q)->num-((Node *)p)->num;\n     return ((Node *)p)->money-((Node *)q)->money;    \n}\n\/\/\u5173\u952e\u70b9\uff1a\u7531\u4e8e\u603b\u4f53\u662f\u6309money\u5347\u5e8f\u6392\u5217\u7684\uff0c\u800cmoney\u76f8\u540c\u65f6\u5148\u5230\u8005\u8981\u591a\u4ed8\n\/\/\u6309\u7167\u8fd9\u4e2a\u601d\u60f3\u591a\u4ed8\u8005\u56e0\u8be5\u6392\u5230\u540e\u5934\uff0c\u6545\u5e94\u8be5\u6309num\u7684\u964d\u5e8f\u6392\u5217 \nint numcmp(const void *p,const void *q)\n{\n     return ((Node *)p)->num-((Node *)q)->num;    \n}\nint main()\n{\n#ifdef LOCAL\n       freopen(\"input.txt\",\"r\",stdin);\n       freopen(\"output.txt\",\"w\",stdout);\n#endif\n \n    int m,n,sum,i,ave;\n    cin>>m;\n    while(m--)\n    {\n             cin>>sum>>n;\n             for(i=0;i&lt;n;i++)\n             {cin>>pay&#91;i].money;pay&#91;i].num=i;}\n             qsort(pay,n,sizeof(Node),moneycmp);\n             ave=sum\/n;\n             for(i=0;i&lt;n-1;i++)\n             {\n                   if(pay&#91;i].money&lt;ave)\n                   {sum-=pay&#91;i].money;ave=sum\/(n-i-1);}\n                   else if(pay&#91;i].money>ave)\n                   {pay&#91;i].money=ave;sum-=ave;ave=sum\/(n-i-1);}\n                   else{sum-=ave;ave=sum\/(n-i-1);}       \n             }\n             if(sum>pay&#91;n-1].money)\n             { cout&lt;&lt;\"IMPOSSIBLE\"&lt;&lt;endl;continue;}\n             else if(sum&lt;pay&#91;n-1].money) pay&#91;n-1].money=sum;\n             qsort(pay,n,sizeof(Node),numcmp);\n             cout&lt;&lt;pay&#91;0].money;\n             for(i=1;i&lt;n;i++)\n                 cout&lt;&lt;\" \"&lt;&lt;pay&#91;i].money;\n             cout&lt;&lt;endl;\n    }\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7],"tags":[],"class_list":["post-116","post","type-post","status-publish","format-standard","hentry","category-06-01-acm"],"_links":{"self":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/116","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=116"}],"version-history":[{"count":0,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/116\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=116"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=116"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=116"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}