微波EDA网,见证研发工程师的成长!
首页 > 硬件设计 > 嵌入式设计 > ACM座位调整题目的解答

ACM座位调整题目的解答

时间:12-01 来源:互联网 点击:
座位调整

题目描述:

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

调整的方法如下:

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
staticconstintM=3;
staticconstintN=3;
staticintcapac[]={1,1,1};
vectoreraseRow(constvector&v,inti,intcurrentArea)
{
intcolSize=N-currentArea;
vectornewVec;
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());
returnnewVec;
}
vectoreraseCol(constvector&v,intcurrentArea)
{
vectornewVec;
for(inti=0;i!=v.size();++i)
{
if(i%(N-currentArea))
{
newVec.push_back(v[i]);
}
}
returnnewVec;
}

intgetMax(vectorv,intnumOfPeop,intnumOfCapac,intcurrentArea=0,intstart=0)
{
intsum=0,max=0;
intcurr=currentArea;
if(numOfPeop{
cerr<"the numOfPeople is smaller than Capacity"return-1;
}
elseif(numOfPeop==numOfCapac)
{
for(inti=0;i!=numOfCapac;++i)
{
max+=v[i];
}
}
else
{
vectornewVec;
if(numOfCapac==1)
{
for(inti=0;i<=numOfPeop-numOfCapac;++i)
{
sum=v[i*(N-curr)];
newVec=eraseRow(v,i,curr);
newVec=eraseCol(newVec,curr);
if(curr{
sum+=getMax(newVec,numOfPeop-1,capac[curr+1],curr+1);
}
max=(max>sum?max:sum);
}
}
else
{
if(numOfCapac<1)
{
cerr<"numOfCapacity is smaller thanzero"return-1;
}
for(inti=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);
}
}
}
returnmax;
}
voidprintVec(constvector&v)
{
intdelim=1;
for(inti=0;i!=v.size();++i,++delim)
{
coutif(!(delim%3))
{
cout}
}
}
voidmain(intargc,char**argv)
{
ifstream ifs("IntrestArea.txt");
vectorv;
v.reserve(M*N);
inti;
while(ifs>>i)
{
v.push_back(i);
}
intmax=getMax(v,M,capac[0]);
cout}
多积累函数,才是最宝贵的。。。。并不是要自己一定能够编写出来哟!!!多读读

Copyright © 2017-2020 微波EDA网 版权所有

网站地图

Top