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
staticconstint M =3;
staticconstint N =3;
staticint capac[]={1,1,1};
vector<int> eraseRow(const vector<int>&v,int i,int currentArea)
{
int colSize = N - currentArea;
vector<int> 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<int> eraseCol(const vector<int>&v,int currentArea)
{
vector<int> newVec;
for(int i =0; i != v.size();++i)
{
if(i%(N-currentArea))
{
newVec.push_back(v[i]);
}
}
return newVec;
}

int getMax(vector<int> 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"<<endl;
return-1;
}
elseif(numOfPeop == numOfCapac)
{
for(int i =0; i != numOfCapac;++i)
{
max += v[i];
}
}
else
{
vector<int> 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"<<endl;
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<int>& v)
{
int delim =1;
for(int i =0; i != v.size();++i,++delim)
{
cout<<v[i]<<"\t";
if(!(delim %3))
{
cout<<endl;
}
}
}
void main(int argc,char**argv)
{
ifstream ifs("IntrestArea.txt");
vector<int> v;
v.reserve(M*N);
int i;
while(ifs>>i)
{
v.push_back(i);
}
int max = getMax(v,M,capac[0]);
cout<<max<<endl;
}
多积累函数，才是最宝贵的。。。。并不是 要自己一定能够编写出来哟！！！多读读