2632 - 席位分配

学校共有n个学院，分别是学院1, 学院2, ... , 学院n。每个学院有Ni名学生，现须按人数比例组织一个学生会，学生会有席位m个，请求出每个学院分配学生的席位个数。分配原则为：首先计算每个学院所占学生会席位的理想个数ai= m * Ni/sum，其中sum=N1+N2+N3+…+Nn，然后把ai的整数部分对应的席位个数分配该学院，按此分配后，m个席位如果分不完，则继续根据ai的余数（即小数部分）的大小依次逐位分配剩下的席位（如果碰到两个学院的余数一样，则人数多的学院优先，如果人数也相等，则学院序号小的优先）。

Input

输入包含多组测试数据，每组数组第一行是两个正数n与m，其中1<n<100, n<=m<10000，接下来第二行是 n个正数ni。

Output

对于每组输入，输出 n个学院所对应的分配席位个数，要求每个数之间用空格分隔（注意每行最后一个数没有空格）

Examples

Input

Output

10 6 4
9 5 4
0 2

Solution C++

#include <iostream>
#include <map>
#include<string>
#include<algorithm>
using namespace std;

const int N = 1000;
int nums[N];
int seats[N];



int main()
{
    int n, m, i;
    int sumNum, sumSeat;
    multimap<double, int> mm;
    double rest;

    while (cin>>n>>m)
    {
        sumNum = 0;        
        sumSeat = 0;
        mm.clear();

        for (i=0; i<n; i++)
        {
            cin>>nums[i];
            sumNum += nums[i];
        }
        
        
        for (i=0; i<n; i++)
        {            
            seats[i] = (m * nums[i]) / sumNum;
            sumSeat += seats[i];

            rest = (double)(m * nums[i]) / sumNum - seats[i];            
            mm.insert(pair<double, int>(rest, i));            
        }
        
        multimap<double, int>::reverse_iterator rit = mm.rbegin();
        while (sumSeat< m)
        {
            i = rit->second;
            seats[i]++;

            sumSeat++;
            rit++;
        }
        
        cout<<seats[0];
        for (i=1; i<n; i++)
            cout<<" " <<seats[i];
        cout<<endl;        
    }
    
    return 0;
}

Time Limit	1 second
Memory Limit	128 MB

Discuss Stats

上一题下一题