ACM座位调整题目的解答

发布者:cannon928最新更新时间:2015-05-07 来源: 51hei关键字:ACM  座位调整 手机看文章 扫描二维码
随时随地手机看文章
座位调整 


题目描述: 

百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现,员工如果可以在自己喜欢的美食旁边工作,工作效率会大大提高。因此,百度决定进行一次员工座位的大调整。 

调整的方法如下: 

1 . 首先将办公区按照各种零食的摆放分成 N 个不同的区域。(例如:可乐区,饼干区,牛奶区等等)。 

2 . 每个员工对不同的零食区域有不同的喜好程度(喜好程度度的范围为 1 — 100 的整数, 喜好程度越大表示该员工越希望被调整到相应的零食区域)。 

3 . 由于每个零食区域可以容纳的员工数量有限,人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。 

数据输入: 

第一行包含两个整数 N , M ,( 1<=N , M<=300 )。分别表示 N 个区域和 M 个员工。 

第二行是 N 个整数构成的数列 a ,其中 a[i] 表示第 i 个区域可以容纳的员工数, (1<=a[i]<=M , a[1]+a[2]+..+a[N]=M) 。 

紧接着是一个 M*N 的矩阵 P , P ( i , j )表示第 i 个员工对第 j 个区域的喜好度。 

答案输出: 

对于每个测试数据,输出可以达到的最大的喜好程度。 

输入样例



3 3 

1 1 1 

100 50 25 

100 50 25 

100 50 25 
 



输出样例



175 
static const int M = 3;
static const int N = 3;
static int capac[] = {1, 1, 1};
vector eraseRow(const vector &v, int i, int currentArea)
{
int colSize = N - currentArea;
vector newVec;
newVec.reserve(v.size() - colSize);
newVec.insert(newVec.begin(),v.begin(),v.begin()+i*colSize);
newVec.insert(newVec.end(),v.begin()+(i+1)*colSize,v.end());
return newVec;
}
vector eraseCol(const vector &v, int currentArea)
{
vector newVec;
for (int i = 0; i != v.size(); ++i)
{
if (i%(N-currentArea))
{
newVec.push_back(v[i]);
}
}
return newVec;
}

int getMax(vector v, int numOfPeop, int numOfCapac, int currentArea = 0, int start = 0)
{
int sum = 0, max = 0;
int curr = currentArea;
if (numOfPeop < numOfCapac)
{
cerr<<"the numOfPeople is smaller than Capacity"< return -1;
}
else if (numOfPeop == numOfCapac)
{
for (int i = 0; i != numOfCapac; ++i)
{
max += v[i];
}
}
else
{
vector newVec;
if (numOfCapac == 1)
{
for (int i = 0; i <= numOfPeop - numOfCapac; ++i)
{
sum = v[i * (N - curr)];
newVec = eraseRow(v,i,curr);
newVec = eraseCol(newVec,curr);
if (curr < N)
{
sum += getMax(newVec, numOfPeop -1, capac[curr+1],curr+1);
}
max = (max > sum ? max:sum);
}
}
else
{
if (numOfCapac<1)
{
cerr<<"numOfCapacity is smaller than zero"< return -1;
}
for (int i = start; i != numOfPeop - numOfCapac; ++i)
{
sum = v[i * (N - curr)];
newVec = eraseRow(v,i,curr);
sum += getMax(newVec, numOfPeop -1, numOfCapac - 1, curr, i);
max = (max > sum ? max:sum);
}
}
}
return max;
}
void printVec(const vector& v)
{
int delim = 1;
for (int i = 0; i != v.size(); ++i, ++delim)
{
cout< if (!(delim %3))
{
cout< }
}
}
void main(int argc, char **argv)
{
ifstream ifs("IntrestArea.txt");
vector v;
v.reserve(M*N);
int i;
while(ifs>>i)
{
v.push_back(i);
}
int max = getMax(v,M,capac[0]);
cout< }
多积累函数,才是最宝贵的。。。。并不是 要自己一定能够编写出来哟!!!多读读

关键字:ACM  座位调整 引用地址:ACM座位调整题目的解答

上一篇:关于MSP430中断、中断嵌套的一些注意事项
下一篇:共阳数码管连接体会

小广播
添点儿料...
无论热点新闻、行业分析、技术干货……
设计资源 培训 开发板 精华推荐

最新单片机文章
何立民专栏 单片机及嵌入式宝典

北京航空航天大学教授,20余年来致力于单片机与嵌入式系统推广工作。

换一换 更多 相关热搜器件
电子工程世界版权所有 京B2-20211791 京ICP备10001474号-1 电信业务审批[2006]字第258号函 京公网安备 11010802033920号 Copyright © 2005-2024 EEWORLD.com.cn, Inc. All rights reserved