数学建模社区-数学中国

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

---

作者: 厚积薄发    时间: 2010-5-6 18:47
标题: 2006 年百度之星程序设计大赛初赛题目 5
座位调整
& S$ U) h4 V1 o* b( l. x
题目描述：
, T5 e/ l6 s. T" c& ?' T
7 l6 v) F) @2 M  l3 x百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。
  C: s! w+ W3 Y- k# Q* L
调整的方法如下：

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

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

3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。
6 X" ^( \6 l% m/ }( J) t
' r2 s; U2 h; I数据输入：
- x# o+ n9 a7 D% ?9 ?2 ^0 h+ v2 g
% {) ~2 I5 C- e+ Y. E7 H第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。

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

4 w2 H0 n4 K1 j1 r5 I紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。
$ {$ f7 V* F' a
答案输出：

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

输入样例

! a1 W5 _$ Q- V& X( \
1 F/ K. Q$ ~4 D( s3 3
1 c# _3 C7 ]- P
1 1 1
1 L7 a* @( K4 _4 ?7 a7 V5 Z: k
100 50 25

100 50 25
# b% Z; z4 F0 u2 _
100 50 25

' D1 v0 e0 l: [7 c& y; {6 F
6 D- ~6 H, H1 I: Z输出样例

1 }  X, y' @! R( _" P# n4 V6 J
175

+ P& n" y( R/ x6 \: N, b
5 A8 k1 C( V" e; K. n* `* n  F数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175

---

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


#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
% A  Q7 o. k* r8 Cint a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
int sum=0;
$ m3 r9 m8 K7 |9 n5 A8 _int max_num()
{
% x/ Z/ y2 K. h* J& a    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
5 J+ f8 w$ H5 E$ x7 `4 n    for(int j=0;j<3;j++)
    {
        if(max<b[j])
; {$ i( v& @6 f        {
            max=b[j];
1 n$ C7 M( O, |( d* U            x=i;
            y=j;

        }
4 ?* `1 n1 F( G1 S    }
* D  m- u! [. B, K% k. r9 p   
4 P  Y$ r: k' ^0 x- w1 B    if(a[y]>0)
    {
        c[x]=y;
+ f* r6 V* `; L" f" o! r5 R        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
' r, u; V: J0 X        for(int k=0;k<3;k++)
: z' O0 l2 t" F; Z/ d        {
: ^, a, h* R* l( {( [- H/ |            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
9 d+ e8 b6 ^% M    }
    else
8 N$ s- M) u5 k) U6 s    {
        b[x][y]=0;
    }
! C7 G5 S4 [+ ~3 [' X0 |# ~2 @   
    return sum;
0 E* ?0 o3 B- x( p}
int main()
1 {. R5 U2 s! [0 G& x{
   
, O0 t$ i  ]- E! h- P" n1 o" M- d    cout<<"input 3 zone's limit:"<<endl;
" H/ e! ?7 v- O( x/ Y# ]2 f    for(int i=0;i<3;i++)
8 a; P6 d9 ~+ m    {
        cin>>a;
: N5 m  B6 ]1 B6 @4 B: v: H    }
1 h1 z: }/ s- N) u. r    cout<<"input 3*3 actangle:"<<endl;
, O& \# L" Y# x- K" Z4 t" D. Y    for(i=0;i<3;i++)
9 g2 m1 J0 R1 {. ]/ o    for(int j=0;j<3;j++)
    {
        cin>>b[j];
    }
( H# R# D& g6 `% v! \    for(int k=0;k<9;k++)
    {
        max_num();
    }
- o) N# X9 z' T( _8 ?0 [   
+ C" Y# ?( U% `* ~* A* h3 _3 M    cout<<"sum="<<sum<<endl;
    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
) T1 Q6 Q3 i. _4 ~2 n7 ?    }
! e  I: C( f/ A0 K4 P7 e( E    return 0;
& i/ f+ G& W& u2 K, u}#include<iostream>
: a; F. ], h# a5 |using namespace std;
! m+ T' y$ t9 f0 Q  Dint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
5 N& V# ^0 U' w7 g4 O  [( Pint c[3];//记录某人i去的区域j
int sum=0;
int max_num()
{
    int max=-32767;
: [9 t7 _8 F9 b' c& O, v7 ~7 I2 t    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
* ~/ }, m% R' s: g. u2 \3 Y    {
        if(max<b[j])
% J* P' f! I% k# V3 [, {        {
' a- v+ e. U' S3 ^9 w, g            max=b[j];
            x=i;
            y=j;

        }
2 d2 h, W6 v3 A    }
   
. A! p* J  c; w9 R$ i% u# l. l    if(a[y]>0)
    {
* R) Z# P! S; E. Y3 i$ W" z5 C        c[x]=y;
        sum+=max;//总喜好度加上添加
8 Y6 w. s- g: ^8 [        a[y]--;//区域上限人数-1
5 i# G0 ~! ?! S1 ]5 P        for(int k=0;k<3;k++)
8 M5 w! [, G& s- G        {
, E+ y" P: a% x' `$ A            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
7 T, ^% o( ?; l. T1 P4 L        }
    }
( m* `) s$ t5 h4 `8 B9 Y( T" U    else
    {
        b[x][y]=0;
    }
. w; _" k( ^: O/ W. M- x   
    return sum;
}
* Q8 u5 S: P$ ]  K+ Wint main()
0 q8 x) q; ]. v! {6 I* V{
   
5 X5 ^8 O7 l4 Q- v; ~0 N0 L4 v: ?    cout<<"input 3 zone's limit:"<<endl;
! M" L6 O- B3 ^( t5 S    for(int i=0;i<3;i++)
    {
        cin>>a;
0 y$ A# p' }3 m( }/ V6 V    }
    cout<<"input 3*3 actangle:"<<endl;
8 O' E) h( e7 u2 I$ t2 ~2 {    for(i=0;i<3;i++)
, O3 r/ M1 o- S, L    for(int j=0;j<3;j++)
6 w( N$ d7 G4 t+ r) O. l- E. g5 v0 r    {
        cin>>b[j];
8 w" F8 h* @$ t) T3 |    }
$ J% J0 ?1 M) b3 v& a    for(int k=0;k<9;k++)
7 x# L3 z# a8 ]9 I9 y- M    {
# W7 H+ b9 T1 R( [4 Y: P  ^; y3 W        max_num();
7 H1 c1 |) w: |9 U6 [    }
+ `1 ]7 }) m0 d4 Q1 Z. h   
1 r2 O* d" \9 m4 e    cout<<"sum="<<sum<<endl;
# Z3 r. d4 Z( u/ ?    cout<<endl;
6 X5 L! j. W; X  w) i: B    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
/ n) x9 _/ P2 n, Y- v    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
: U+ \0 T( ]: x8 c2 G: V% Z    }
& r8 M3 q1 B3 H. m/ }# U6 |    return 0;
* ^, R  p! b0 j; ?/ R}

---

作者: 厚积薄发    时间: 2010-5-6 18:48
编程代码二：
2 \. z* G  ~& M8 {#include<iostream>
) h0 @1 _( r! P, i, k4 e#include<cstring>
#include<ctime>
7 c( M- U0 \2 y+ j, zusing namespace std;
class ifo{//矩阵的元素
0 Z- H* k  ?% ^" o  X& Y3 L    int clerk;//员工号
8 l$ n7 C/ O' }8 C, L' p; T6 i    int area;//区域号
    int per;//爱好度
* A$ }9 x! b8 _) \public:
    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
! G6 e; `7 G. h2 S9 d: x8 q! g    int getclerk(){return clerk;}
: I+ s( n5 `' ^    int getarea(){return area;}
6 u# V, [8 p* @/ Y    int getper(){return per;}
    void setclerk(int i){clerk=i;}
" a3 Z: G7 i3 \4 _) d8 X    void setper(int p){per=p;}
    void setarea(int a){area=a;}
};
! W7 a! z# D/ s- @) Zclass area;
class clerk{
# h4 t* c- D! X; y    int areanum;
    bool isin;
    int inarea;
! F: Q% w; z# fpublic:
3 E* r" \# K. |* n, x" m" U    void set(int num){isin=true;inarea=num;};
* ^  V- W' l& t9 |1 ^, `$ c    void setisin(bool b=true){isin=b;}
) T+ K9 T: Y$ Y" b" V" [* S    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
};
( j& N0 x: ~! K9 V; zclass area{
4 l" ?3 }  j4 Y* Z, r* Z    int num;
) |  h; i* U0 U4 S, D" U    int max_num;
public:
" P" y5 f* ?5 L5 o    friend void set(int);
    int getnum(){return num;}
' Z; A* u5 @6 s; i! ?    void setnum(int number){num=number;}
+ y" C1 {. e9 B: m: ?  E( x    int getmax_num(){return max_num;}
    area(int number=0){num=number;}
    int getclerk(){return num;}
. r% C8 l! f' n1 q    void addclerk(int ps){num++;set(ps);}
};
void getorderbyper(ifo array[]);
8 V+ |( N4 B' |6 o1 j* B4 Rint areanums;
void main(){
8 _& V; M1 u- z7 ^$ N  N5 w    //input
    cout<<"输入区域数：\n";
    int area_num;
    cin>>area_num;
1 w+ n% \7 Q1 [4 i! P9 e    areanums=area_num;
    cout<<"输入员工数：\n";
    int c_num;
- @: f4 ]4 I7 f5 H1 r    cin>>c_num;
( M8 k$ c4 F2 |; `% {9 o    cout<<"依次输入每个区域能容纳的员工数:\n";
    int *max=new int[area_num];
. l: S$ z  Y* u  T9 O    int nownum=c_num;
    while(nownum){
8 b. Y$ E* _  V+ g7 l  s        for(int i=0;i<area_num;i++)
        {cin>>max[i];nownum-=max[i];}
9 W+ L4 [! K, M0 g& t  a4 P* a        if(nownum>0){
            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
            nownum=c_num;
        }
3 A' |: a! r" g" T: l  R& P0 a- Q        else nownum=0;
    }
0 ]3 |, j( Q* @0 J* s  R    cout<<"按行输入每个员工的偏好：\n";
3 e4 J+ W& h% m- V0 Z( ~    ifo** per=new ifo*[c_num];
+ t7 m7 U! m- w! I' u: u4 `) ~    for(int j=0;j<c_num;j++)
        per[j]=new ifo[area_num];
& D4 B( X1 f' D; o7 |" X! L1 n    srand(time(0));
, D; J4 j9 w* h, {# [, N    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);
            per[a][c].setarea(a);
            per[a][c].setclerk(c);
        }
        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
# z/ r8 r$ k' R8 B9 E: E        {    per[c][a].setper((rand()%60)+40);
2 X4 B8 g! c+ @: y; _            cout<<per[c][a].getper()<<'\t';
5 A& j, ^* T, L8 w2 c        }//测试时懒得输入，故以60-100的随机数代替。
-    cout<<endl;
, k! A, x) R5 A" K/ k    }
5 W5 j- C& _0 B4 ?    //output
$ ?) u) t* a1 @/ c2 ]: b7 n0 N        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
% r+ T* v% f1 D- T! o- g' C  U3 |* O0 j        clerk* people=new clerk[c_num];
: h# g( T6 b! B        area*  areas=new area[area_num];
' d, w# e' ]: z2 K        int totalper=0;
, r' m, T7 L6 p8 _# S        for(i=0;i<c_num;i++){
7 P! z3 K- t. S            for(j=0;j<area_num;j++){
            if(areas[per[i][j].getarea()].getnum()<areas[per[i][j].getarea()].getmax_num())
                people[i].set(per[i][j].getarea());
$ @4 G1 y/ j  N$ h8 w                people[i].setisin();
                int number=areas[per[i][j].getarea()].getnum();
, Z& q/ `  D- g! H/ k                areas[per[i][j].getarea()].setnum(number);
' S- C7 i0 Y/ G' R" c  H2 N0 ]7 E) A                totalper+=per[i][j].getper();
+ V0 m0 f# C2 O+ D                break;
            }
; M+ y, M  i1 c3 h  Q        }
% P; ^9 P( }8 b8 Y$ P; M        cout<<"能达到的最大喜好度为："<<totalper<<endl;
; d  k: r0 o3 U% k& X0 x}
* u. P" o6 m* ~0 R1 F5 \; F  lvoid getorderbyper(ifo array[]){
& i* e7 {# a0 s& T, X    int max=0;
    for(int i=1;i<areanums;i++){
        for(int j=0;j<areanums-i;j++){
: C$ `% {4 g# O6 O3 d" h$ U/ c        if(array[i].getper()>array[max].getper()){
            max=i;}
        }
4 J- i% P# B+ i( N        ifo temp=array[max];
        array[max]=array[areanums-i];
        array[areanums-i]=temp;
        max=0;
6 M4 ?* o5 t+ D# Z  H' E    }
7 o4 b9 T. h3 x+ W! }7 [+ U2 Q}

---

作者: 厚积薄发    时间: 2010-5-6 18:49
代码3：
9 h8 n- _5 O& c* z- J0 {/*
0 d& P6 c4 ?/ b, f8 s! X算法思路：
8 Z- b  R- h7 a$ H: l9 R（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
再加，该人的所有喜好度设为0，
: E  y6 {; h4 X9 w; r0 g' r（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
(4)最后输出总喜好度。
( L, u3 Y7 }% r. L( [/ r$ c' c*/
#include<iostream>
0 ~$ w( M3 l% j5 S) ^' Cusing namespace std;
int b[3][3];//M*N矩阵
9 P/ V. g' M) `int a[3]; //区域人数上限数组
  f1 W# B8 p+ N& Yint c[3];
* L6 L0 {  e! v& K' N& t. yint temp[3];
int sum=0;
" a. f- k2 a( Pint max_num()
. J7 n( V" i% `! D3 V0 o{
2 \& |0 C3 q& U$ \    int max=-32767;
6 w$ J: H& X3 X    int x,y;
# i7 H1 u1 q+ m    for(int i=0;i<3;i++)
% r) O: ^4 U( H  Y# }! A    for(int j=0;j<3;j++)
4 D( f4 |0 j! V0 ^3 f    {
4 D1 s! Q  H8 t7 z' S+ A        if(max<b[i][j]&&b[i][j]>0)
! q) Q. p7 t  J+ c        {
            max=b[i][j];
- r8 h% ?( y$ W# J% @            x=i;
: ]8 y7 l5 l8 B! l6 f2 h            y=j;
! z& [8 f3 Y* t4 H
6 [4 \+ A  C$ H! Z  C; B" @9 w        }
( ]7 Z' ~* I. }    }
   
+ S! S. n7 a& d2 K, O, g4 ~2 S    if(a[y]>0)
    {
7 ?1 T' z; F3 t5 f        c[x]=y;
6 Q9 w8 o6 O# v+ v9 }  t8 h        //cout<<"c["<<x<<"]="<<c[x]<<endl;
, M; S7 W" V4 Q4 a7 }6 f$ H        sum+=max;//总喜好度加上添加
. _! r9 |4 N, j8 s& g5 F        temp[x]=max;
        a[y]--;//区域上限人数-1
    }
- @  L6 W$ I# l3 G9 G( S: Z* ?1 I' R    for(int k=0;k<3;k++)
    {
5 O9 V2 [4 k" M: w        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
    }
. D6 a. b+ e5 S+ c! Z    return sum;
}
7 `7 A, ~5 E( W* H& lint main()
& y9 D- H9 ]4 C# g" B6 @. S7 f{
   
# o9 }. i; }" B0 L    cout<<"input 3 zone's limit:"<<endl;
- c: o0 t# l0 H6 e3 K( R2 _    for(int i=0;i<3;i++)
$ \$ c" K3 l- g    {
9 D2 z5 y' b0 n, K( J1 i, |# q4 a        cin>>a[i];
    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
* d: O0 b; l0 Q) q- x# j    for(int j=0;j<3;j++)
    {
        cin>>b[i][j];
    }
    for(int k=0;k<3;k++)
    {
! x/ ?1 l% m# F$ I. ~. s        max_num();
    }
& Y9 s) A+ D( f- o7 C2 i- a- j0 k    //cout<<"sum="<<sum<<endl;
    cout<<"sum=";
+ q1 T: S% K! h4 |$ ?& n: [    for(i=0;i<3;i++)
/ t% {+ f0 o; f* A( E! G! N# T, Z8 ^    {
        cout<<temp[i]<<"+";
    }
7 Q: W  a1 {, }    cout<<endl;
    cout<<"reslut:"<<endl;
" J  H- h* V2 a) u6 X/ Y( n0 R    for(i=0;i<3;i++)
    {
7 N) Q+ n: ?; s8 a        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
    }
7 j, B( u# _9 j    return 0;
}

---

作者: 葉_浅浅    时间: 2011-2-22 21:04
其实我一直觉得楼主的品味不错！呵呵！
1 W6 W. N+ A& i6 t. }! n4 i1 @6 G6 W数学中国社区分享快乐！

---

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

---

作者: ehi28    时间: 2011-12-11 16:23
嗯,不错,支持一下.

---

作者: 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