数学建模社区-数学中国

标题: 2006 年百度之星程序设计大赛初赛题目 5 [打印本页]

---

作者: 厚积薄发    时间: 2010-5-6 18:47
标题: 2006 年百度之星程序设计大赛初赛题目 5
座位调整

题目描述：

百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。
. X- J  L9 Y/ J' S' C+ o+ m7 Q
  X. I8 _+ q: I0 c- X4 C调整的方法如下：

1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。

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

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

数据输入：

; i! v9 ]. F! R! M/ t第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。

9 ]# _* T. F6 ~3 i2 ]9 E4 n第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。

; g1 e# }. R3 K, H. |$ e紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。

答案输出：

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

3 {, H- T3 C0 e" z输入样例

4 S8 k0 k4 a6 {3 v2 |% [( r
3 3

1 1 1

100 50 25
8 i2 `: D! }, p) T
100 50 25

& ~6 |2 P0 P/ U100 50 25
) A" s8 d0 D& Z5 x

5 l- @% m8 C& q3 y# l* k% Q
( i" R( i4 ^! l  k输出样例

175

; T! J9 ]# c+ s/ V
5 g8 j$ j+ o8 E0 B: w数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175

---

作者: 厚积薄发    时间: 2010-5-6 18:47

7 Y+ n  O- J% T8 m" q7 M
#include<iostream>
( Q6 \+ X  v8 B( n8 {using namespace std;
int b[3][3];//M*N矩阵
1 q" n8 C2 I! T/ m: J- z3 }int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
int sum=0;
5 u5 Y, I  p* Jint max_num()
{
    int max=-32767;
9 z9 |6 h1 K+ l6 D/ |$ p9 r# O    int x,y;
3 n9 Z3 q- c7 v/ r* ^    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
4 k0 w# R$ o, J4 h# F' r; t/ o    {
        if(max<b[j])
        {
( {7 u7 O7 i: V* V2 e            max=b[j];
" S# [1 |& v9 {            x=i;
            y=j;

        }
    }
   
: k" C" ?( P+ w2 p    if(a[y]>0)
    {
        c[x]=y;
        sum+=max;//总喜好度加上添加
9 b: Y" f# f3 p5 C        a[y]--;//区域上限人数-1
7 ^- E$ V( b, s* s/ U- F; M& _        for(int k=0;k<3;k++)
* W) d$ m3 @: k& r# e! K* ~6 a        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
    }
    else
    {
        b[x][y]=0;
2 U% u9 c; t* E$ P/ `. ], }/ K    }
   
) i! O2 x' n; W" l0 b. ~    return sum;
}
int main()
{
   
    cout<<"input 3 zone's limit:"<<endl;
7 D# Y* Q" j' H( Y# ^- J    for(int i=0;i<3;i++)
    {
7 J( ^' a( j) w; B8 E# h( p. n        cin>>a;
    }
    cout<<"input 3*3 actangle:"<<endl;
- E1 G; j( w* t: E  q* _& o4 I" k    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
2 w, }) [4 x$ H" t+ G% x6 S    {
. Y4 _* q( }% e! }. @  S" w. y        cin>>b[j];
    }
! A: u; _& o" N) e" |3 B    for(int k=0;k<9;k++)
8 Y8 h0 ~. `) T. Q; C    {
. f& r: W0 s9 \3 b; m8 }        max_num();
    }
% J& L. z+ k- S4 |  O! ]; C) k9 c   
    cout<<"sum="<<sum<<endl;
    cout<<endl;
    cout<<"reslut:"<<endl;
) Z+ T8 W/ c4 j    for(i=0;i<3;i++)
5 c8 w) Y* E, @$ x6 T    {
9 C- G: K7 ^/ k) e6 `$ Q        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
    return 0;
}#include<iostream>
using namespace std;
& M( R8 k9 Y( ~* ^: T& Z! Q5 H7 Hint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
% c' @4 y6 s; }$ C, l( y8 Nint c[3];//记录某人i去的区域j
int sum=0;
int max_num()
! B0 t; m9 c% E' ?. Q1 X, I{
    int max=-32767;
+ ?1 B2 P' [( a) ^+ Q, w6 c& R    int x,y;
; C: r; d7 A* _9 o. n8 r    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
* M& J1 ^, k# K3 p2 Y. z    {
. }& k; O$ t% J6 d        if(max<b[j])
7 ], z5 r9 b# e/ Q% s( Y/ L" @        {
            max=b[j];
            x=i;
            y=j;
( ]6 o0 O% l3 f# B( X
        }
: y. e5 c4 T) J' J8 n: u! r    }
9 M  Y4 X0 v$ l3 f1 s   
2 L4 L, N0 E; P    if(a[y]>0)
' y) O* p7 e4 t# P8 |% T( G    {
        c[x]=y;
        sum+=max;//总喜好度加上添加
- j+ w" A; t: n        a[y]--;//区域上限人数-1
$ j- _" {& l9 U2 h" C' i2 Q        for(int k=0;k<3;k++)
  L1 T3 c5 q5 j        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
/ W- w" p" k& H, ^% [; J+ P. M        }
7 y# R/ o7 z/ G! U    }
    else
  f, |' [" s4 Y. B" w2 @% Z    {
        b[x][y]=0;
    }
   
    return sum;
}
; p4 V  I9 u: ]# G% M/ Y6 Rint main()
{
3 c( V3 C+ m# ~" m$ W; I$ r& F   
    cout<<"input 3 zone's limit:"<<endl;
  x, w* f, p; B( K    for(int i=0;i<3;i++)
6 M7 P3 k) r9 ^' O  O    {
        cin>>a;
. z8 u6 b7 o1 b3 e# I    }
    cout<<"input 3*3 actangle:"<<endl;
' y' m, h0 r. R$ A; I    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
' k7 L7 [& r, x4 L    {
        cin>>b[j];
7 ~9 d! {1 k# \# z3 d" D# G2 i    }
    for(int k=0;k<9;k++)
    {
* k7 l5 q# h0 \$ i6 o        max_num();
1 Q. I5 c+ k9 T$ D* m) G    }
2 Z9 z/ z$ b3 K9 a( @   
& T. d, C/ b6 ~3 U/ }% h    cout<<"sum="<<sum<<endl;
4 t, Q; j5 [" t    cout<<endl;
1 N8 F/ z2 ^% j    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
# ]/ y8 }. V$ Q( {7 ^- \  Y        cout<<"people "<<i<<" go to zone "<<c<<endl;
/ f; z0 Q  g/ x+ O+ D& s: j    }
    return 0;
}

---

作者: 厚积薄发    时间: 2010-5-6 18:48
编程代码二：
4 E  I* h* W$ B% M( K#include<iostream>
( V- f. C9 E% Z/ v  b: Z#include<cstring>
" n: S2 Y0 C/ d+ O/ a#include<ctime>
using namespace std;
class ifo{//矩阵的元素
9 U' U* K* X8 I/ |/ w: r* m8 _" F    int clerk;//员工号
) \. D0 m* G- ]% l; y# m) @    int area;//区域号
    int per;//爱好度
7 r4 r# |3 l; w8 f( hpublic:
3 \- W( b8 M' l* [  A1 V8 r) c    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;}
- b7 o/ L; e; X8 \( W    void setclerk(int i){clerk=i;}
0 R9 m5 n: H: y+ j8 D5 i, N    void setper(int p){per=p;}
" \; s7 p0 C3 \+ [% M    void setarea(int a){area=a;}
4 o2 R" A, u) q0 N  P! H! o};
class area;
/ z+ ]# U; R2 J* J5 W; Sclass clerk{
    int areanum;
    bool isin;
    int inarea;
public:
; J& q; p" ?" [9 g& y    void set(int num){isin=true;inarea=num;};
+ A+ `9 Q9 _4 w# B: T/ W& B    void setisin(bool b=true){isin=b;}
0 W( C' L2 V7 a$ {0 u2 H, J, n    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
};
class area{
    int num;
    int max_num;
public:
' g- k# q; u4 G& _& b9 `3 Z! `5 X    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;}
2 ^" h4 q& ]! D& a9 }; U0 a    int getclerk(){return num;}
    void addclerk(int ps){num++;set(ps);}
};
void getorderbyper(ifo array[]);
int areanums;
void main(){
    //input
: _0 g& l8 A4 ]: N    cout<<"输入区域数：\n";
    int area_num;
    cin>>area_num;
    areanums=area_num;
8 r2 H4 ?1 L) U  ]4 k+ R    cout<<"输入员工数：\n";
    int c_num;
    cin>>c_num;
* }% x1 @$ |& A    cout<<"依次输入每个区域能容纳的员工数:\n";
& ?0 l$ n. q/ k) b* h    int *max=new int[area_num];
' T& R- x9 B) G! y2 e2 {    int nownum=c_num;
    while(nownum){
0 n. B3 q/ _; x! [0 i        for(int i=0;i<area_num;i++)
        {cin>>max[i];nownum-=max[i];}
        if(nownum>0){
  h2 ~$ \0 G) v. X' z' ^; p. q            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
            nownum=c_num;
        }
        else nownum=0;
    }
    cout<<"按行输入每个员工的偏好：\n";
. g+ U8 D. m, L1 b% D) l    ifo** per=new ifo*[c_num];
7 F6 \1 E9 [) V* Q    for(int j=0;j<c_num;j++)
        per[j]=new ifo[area_num];
( T4 W7 }9 b4 \' u: d& U. b    srand(time(0));
    for(int c=0;c<c_num;c++){
        for(int a=0;a<area_num;a++)/*
        {    int p;cin>>p;per[c][a].setper(p);
' }6 _! F' L. W6 C& q  I0 c            per[a][c].setarea(a);
# q- \. i" v, D' r            per[a][c].setclerk(c);
; S5 P  {7 `* g5 a$ j        }
- c1 A0 |& Z- `7 W        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
        {    per[c][a].setper((rand()%60)+40);
! L$ ~; W: {$ L            cout<<per[c][a].getper()<<'\t';
        }//测试时懒得输入，故以60-100的随机数代替。
-    cout<<endl;
- J  }+ F$ b( `9 G) ?    }
    //output
! K5 l; e7 P4 I! w) F( X        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
4 w7 j+ }) D: F# O! Z        clerk* people=new clerk[c_num];
        area*  areas=new area[area_num];
5 v+ b% [/ E0 A$ M( _. I5 H        int totalper=0;
! d8 I# W: z$ P* M1 G        for(i=0;i<c_num;i++){
4 G3 R, ~+ f5 b" q; B9 j  [/ I            for(j=0;j<area_num;j++){
            if(areas[per[i][j].getarea()].getnum()<areas[per[i][j].getarea()].getmax_num())
% o9 ^; Z2 p$ i; I                people[i].set(per[i][j].getarea());
                people[i].setisin();
; r* c- K9 {; n5 D* v8 ]4 L                int number=areas[per[i][j].getarea()].getnum();
* P) ~3 g+ T3 F! n                areas[per[i][j].getarea()].setnum(number);
                totalper+=per[i][j].getper();
% b" J' N0 A; s' J2 [                break;
            }
3 l4 d" p+ E5 u5 y7 ]& K2 n        }
        cout<<"能达到的最大喜好度为："<<totalper<<endl;
( r9 @7 K) n: d}
1 m0 j+ z, |, {void getorderbyper(ifo array[]){
" n) R8 [8 `3 k' n5 p    int max=0;
- S2 I' u0 I3 r  d+ g) c2 }0 y! ^    for(int i=1;i<areanums;i++){
        for(int j=0;j<areanums-i;j++){
7 l5 P* E4 r7 u        if(array[i].getper()>array[max].getper()){
            max=i;}
        }
+ j& d3 I4 j8 y" b, \        ifo temp=array[max];
: K' G  }1 x" a$ [        array[max]=array[areanums-i];
        array[areanums-i]=temp;
/ F8 Z% G" H3 g, ^# L) Q        max=0;
$ t( R" R2 y: s5 Y( c    }
+ x5 X) m- Q8 Y$ M2 `+ w9 Y}

---

作者: 厚积薄发    时间: 2010-5-6 18:49
代码3：
/*
算法思路：
（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
再加，该人的所有喜好度设为0，
7 d/ e  \! Z8 s+ E3 m7 G( A6 c（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
(4)最后输出总喜好度。
*/
#include<iostream>
using namespace std;
  {9 H+ p! e( u* `( U" vint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];
3 p# B# V, \5 q0 b& Xint temp[3];
" e) ?7 b6 W; K3 P7 H  kint sum=0;
int max_num()
{
    int max=-32767;
" [# y# {) L* P! X( _, `    int x,y;
4 D' ]( O6 i( y: B" T    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
! ?4 i; G/ h$ H0 z6 n* t1 |    {
3 T. c, o& z0 A        if(max<b[i][j]&&b[i][j]>0)
7 V  X3 n8 Z; I: `$ h& X5 [        {
            max=b[i][j];
+ q  {9 a6 S  L: J5 T' ?            x=i;
& z0 N1 X; N0 P8 |4 y- Y            y=j;

        }
    }
   
    if(a[y]>0)
    {
        c[x]=y;
        //cout<<"c["<<x<<"]="<<c[x]<<endl;
. y+ U& ?) i1 W. S9 M        sum+=max;//总喜好度加上添加
! p* x* H$ P4 g8 T2 T1 t0 o8 h        temp[x]=max;
        a[y]--;//区域上限人数-1
* M7 K& [" t9 x/ n3 V6 O  |/ ^" _6 F    }
1 [5 j' w7 R( A8 C, O" c, O, f) a3 g0 j    for(int k=0;k<3;k++)
% v( T  T7 \4 g8 C! e+ Q9 O( i    {
        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
+ x4 X) Q; e( p" d+ g; D; i    }
    return sum;
* d  ?9 K! u, D( ^, Q, p}
int main()
{
   
: W: x' n/ m2 K- T    cout<<"input 3 zone's limit:"<<endl;
/ U3 y) e6 m; |- x) [    for(int i=0;i<3;i++)
+ V% b1 l, q3 Q/ o$ B6 B- f    {
# c5 K/ J& X( W/ }- z        cin>>a[i];
2 b/ @& m. a0 t; p/ r5 r    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
/ r' f5 R6 `! _+ g- X" ]    for(int j=0;j<3;j++)
    {
! \1 u3 i, ]$ e0 |3 h- T2 T& i, W7 H        cin>>b[i][j];
) F$ u1 J  h2 E  Z0 w    }
1 s: l! p0 k( h% X3 }' C    for(int k=0;k<3;k++)
2 Z) f' u5 b- Q4 U    {
        max_num();
    }
    //cout<<"sum="<<sum<<endl;
3 w; q( A# g1 k9 n$ n2 @    cout<<"sum=";
    for(i=0;i<3;i++)
7 q& F; V+ J* h! ?: k7 I    {
. h9 R- ^) j# I/ Q        cout<<temp[i]<<"+";
- q- z) f! Q& Z) w2 \    }
- m0 S& c" v+ M& m    cout<<endl;
, x! l, x) w8 u: Z+ A  G5 Z    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
) v7 H  _) _  z+ }& S    {
        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
    }
    return 0;
: n2 I3 h; D# o( [+ R) j}

---

作者: 葉_浅浅    时间: 2011-2-22 21:04
其实我一直觉得楼主的品味不错！呵呵！
) g$ K  w( `/ Z- V0 j数学中国社区分享快乐！
$ Y# `( C* y' ^! ]5 m! g' I' i5 p# g7 x

---

作者: _Amy_    时间: 2011-7-3 14:01
程序最头疼

---

作者: ehi28    时间: 2011-12-11 16:23
嗯,不错,支持一下.
( C1 V6 S& s  T

---

作者: schnee    时间: 2012-1-28 21:30
必须顶！！！

---

作者: 久玖九王    时间: 2012-10-1 20:18
C++,可是我喜欢c语言的，只是现在还没有到家

---

作者: hbdkfk2    时间: 2013-1-14 10:05
看不懂！！

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5