2006 年百度之星程序设计大赛初赛题目 5
座位调整题目描述：
百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。
调整的方法如下：
1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。
2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。
3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。
数据输入：
第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。
第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a+a+..+a=M) 。
紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。
答案输出：
对于每个测试数据，输出可以达到的最大的喜好程度。
输入样例
3 3
1 1 1
100 50 25
100 50 25
100 50 25
输出样例
175
数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175 本帖最后由 厚积薄发 于 2010-5-6 18:48 编辑
#include<iostream>
using namespace std;
int b;//M*N矩阵
int a; //区域人数上限数组
int c;//记录某人i去的区域j
int sum=0;
int max_num()
{
int max=-32767;
int x,y;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
{
if(max<b)
{
max=b;
x=i;
y=j;
}
}
if(a>0)
{
c=y;
sum+=max;//总喜好度加上添加
a--;//区域上限人数-1
for(int k=0;k<3;k++)
{
b=0;//设为0是因为以后这行的喜好度用不上了
}
}
else
{
b=0;
}
return sum;
}
int main()
{
cout<<"input 3 zone's limit:"<<endl;
for(int i=0;i<3;i++)
{
cin>>a;
}
cout<<"input 3*3 actangle:"<<endl;
for(i=0;i<3;i++)
for(int j=0;j<3;j++)
{
cin>>b;
}
for(int k=0;k<9;k++)
{
max_num();
}
cout<<"sum="<<sum<<endl;
cout<<endl;
cout<<"reslut:"<<endl;
for(i=0;i<3;i++)
{
cout<<"people "<<i<<" go to zone "<<c<<endl;
}
return 0;
}#include<iostream>
using namespace std;
int b;//M*N矩阵
int a; //区域人数上限数组
int c;//记录某人i去的区域j
int sum=0;
int max_num()
{
int max=-32767;
int x,y;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
{
if(max<b)
{
max=b;
x=i;
y=j;
}
}
if(a>0)
{
c=y;
sum+=max;//总喜好度加上添加
a--;//区域上限人数-1
for(int k=0;k<3;k++)
{
b=0;//设为0是因为以后这行的喜好度用不上了
}
}
else
{
b=0;
}
return sum;
}
int main()
{
cout<<"input 3 zone's limit:"<<endl;
for(int i=0;i<3;i++)
{
cin>>a;
}
cout<<"input 3*3 actangle:"<<endl;
for(i=0;i<3;i++)
for(int j=0;j<3;j++)
{
cin>>b;
}
for(int k=0;k<9;k++)
{
max_num();
}
cout<<"sum="<<sum<<endl;
cout<<endl;
cout<<"reslut:"<<endl;
for(i=0;i<3;i++)
{
cout<<"people "<<i<<" go to zone "<<c<<endl;
}
return 0;
} 编程代码二：
#include<iostream>
#include<cstring>
#include<ctime>
using namespace std;
class ifo{//矩阵的元素
int clerk;//员工号
int area;//区域号
int per;//爱好度
public:
ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
int getclerk(){return clerk;}
int getarea(){return area;}
int getper(){return per;}
void setclerk(int i){clerk=i;}
void setper(int p){per=p;}
void setarea(int a){area=a;}
};
class area;
class clerk{
int areanum;
bool isin;
int inarea;
public:
void set(int num){isin=true;inarea=num;};
void setisin(bool b=true){isin=b;}
clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
};
class area{
int num;
int max_num;
public:
friend void set(int);
int getnum(){return num;}
void setnum(int number){num=number;}
int getmax_num(){return max_num;}
area(int number=0){num=number;}
int getclerk(){return num;}
void addclerk(int ps){num++;set(ps);}
};
void getorderbyper(ifo array[]);
int areanums;
void main(){
//input
cout<<"输入区域数：\n";
int area_num;
cin>>area_num;
areanums=area_num;
cout<<"输入员工数：\n";
int c_num;
cin>>c_num;
cout<<"依次输入每个区域能容纳的员工数:\n";
int *max=new int;
int nownum=c_num;
while(nownum){
for(int i=0;i<area_num;i++)
{cin>>max;nownum-=max;}
if(nownum>0){
cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
nownum=c_num;
}
else nownum=0;
}
cout<<"按行输入每个员工的偏好：\n";
ifo** per=new ifo*;
for(int j=0;j<c_num;j++)
per=new ifo;
srand(time(0));
for(int c=0;c<c_num;c++){
for(int a=0;a<area_num;a++)/*
{ int p;cin>>p;per.setper(p);
per.setarea(a);
per.setclerk(c);
}
cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
{ per.setper((rand()%60)+40);
cout<<per.getper()<<'\t';
}//测试时懒得输入，故以60-100的随机数代替。
- cout<<endl;
}
//output
for(int i=0;i<c_num;i++)getorderbyper(per);//将每个人的喜好排序
clerk* people=new clerk;
area* areas=new area;
int totalper=0;
for(i=0;i<c_num;i++){
for(j=0;j<area_num;j++){
if(areas.getarea()].getnum()<areas.getarea()].getmax_num())
people.set(per.getarea());
people.setisin();
int number=areas.getarea()].getnum();
areas.getarea()].setnum(number);
totalper+=per.getper();
break;
}
}
cout<<"能达到的最大喜好度为："<<totalper<<endl;
}
void getorderbyper(ifo array[]){
int max=0;
for(int i=1;i<areanums;i++){
for(int j=0;j<areanums-i;j++){
if(array.getper()>array.getper()){
max=i;}
}
ifo temp=array;
array=array;
array=temp;
max=0;
}
} 代码3：
/*
算法思路：
（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
再加，该人的所有喜好度设为0，
（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
(4)最后输出总喜好度。
*/
#include<iostream>
using namespace std;
int b;//M*N矩阵
int a; //区域人数上限数组
int c;
int temp;
int sum=0;
int max_num()
{
int max=-32767;
int x,y;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
{
if(max<b&&b>0)
{
max=b;
x=i;
y=j;
}
}
if(a>0)
{
c=y;
//cout<<"c["<<x<<"]="<<c<<endl;
sum+=max;//总喜好度加上添加
temp=max;
a--;//区域上限人数-1
}
for(int k=0;k<3;k++)
{
b=0;//设为0是因为以后这行的喜好度用不上了
}
return sum;
}
int main()
{
cout<<"input 3 zone's limit:"<<endl;
for(int i=0;i<3;i++)
{
cin>>a;
}
cout<<"input 3*3 actangle:"<<endl;
for(i=0;i<3;i++)
for(int j=0;j<3;j++)
{
cin>>b;
}
for(int k=0;k<3;k++)
{
max_num();
}
//cout<<"sum="<<sum<<endl;
cout<<"sum=";
for(i=0;i<3;i++)
{
cout<<temp<<"+";
}
cout<<endl;
cout<<"reslut:"<<endl;
for(i=0;i<3;i++)
{
cout<<"people "<<i<<" go to zone "<<c<<endl;
}
return 0;
} 其实我一直觉得楼主的品味不错！呵呵！
数学中国社区分享快乐！
程序最头疼 嗯,不错,支持一下.
必须顶！！！ C++,可是我喜欢c语言的，只是现在还没有到家 看不懂！！
页:
[1]
2