首页 > ACM题库 > HDU-杭电 > HDU 3866-Moonfang’s Birthday[解题报告]HOJ
2015
04-13

HDU 3866-Moonfang’s Birthday[解题报告]HOJ

Moonfang’s Birthday

问题描述 :

It’s Moonfang’s birthday,and his friends decided to buy him a copy of XianJianQiXiaZhuan V.
  
Since some of friends have more money available than others, nobody has to pay more than he can afford. Every contribution will be a multiple of 1 cent,i.e.,nobody can pay fractions of a cent.
  
Everybody writes down the maxumum amount he is able to contribute. Taking into account these maximum amounts from everybody, your task is to share the cost of the present as fairly as possible. That means, you minimize the largest distance of the contributions to 1/n-th of the total cost.
  
In case of a tie, minimize the second largest distance, and so on. Since the smallest unit of contribution is 1 cent, there might be more than one possible division of the cost. In that case, persons with a higher maximum amount pay more. If there is still ambiguity, those who come first in the list pay more.
  
Since you bought the present, it is your task to figure out how much everybody has to pay.

输入:

On the first line a positive integer: the number of test cases, at most 200. After that per test case:
  • One line with two integers p and n: the price of the present in cents (1 ≤ p ≤ 1 000 000) and the number of people (2 ≤ n ≤ 10000) who contribute to the present (including you).
  • One line with n integers ai (1 ≤ ai ≤ 1 000 000), where ai is the maximum amount, in cents, that the i-th person on the list is able to contribute.

输出:

On the first line a positive integer: the number of test cases, at most 200. After that per test case:
  • One line with two integers p and n: the price of the present in cents (1 ≤ p ≤ 1 000 000) and the number of people (2 ≤ n ≤ 10000) who contribute to the present (including you).
  • One line with n integers ai (1 ≤ ai ≤ 1 000 000), where ai is the maximum amount, in cents, that the i-th person on the list is able to contribute.

样例输入:

3 
20 4 
10 10 4 4 
7 3 
1 1 4 
34 5 
9 8 9 9 4

样例输出:

6 6 4 4 
IMPOSSIBLE 
8 7 8 7 4 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
#define ll long long

struct Person{
 int id;
 ll maxm,out;
 bool operator<(const Person& p)const{
 if(maxm == p.maxm) return id < p.id;
 else return maxm > p.maxm;
 }
}p[1000010];
int n;
ll sum,tsum,aver;

bool cmp(Person p1,Person p2)
{
 return p1.id < p2.id;
}

int main()
{
 int test,i,j;
 scanf("%d",&test);
 while(test--){
 scanf("%I64d%d",&sum,&n);
 for(tsum=0,i=0; i<n; i++){
 scanf("%I64d",&p[i].maxm);
 p[i].id=i;
 tsum += p[i].maxm;
 }
 //printf("tsum = %I64d\tsum = %I64d\n",tsum,sum);
 if(tsum < sum) { puts("IMPOSSIBLE"); continue;}
 sort(p,p+n);
 for(i = n-1; i>=0; i--){
 aver = sum / (i+1);
 if(aver > p[i].maxm) aver = p[i].maxm;
 p[i].out = aver;
 sum -= aver;
 }
 sort(p,p+n,cmp);
 printf("%d",p[0].out);
 for(i=1; i<n; i++) printf(" %d",p[i].out);
 puts("");
 }
 return 0;
}

  1. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的