数学建模社区-数学中国

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

---

作者: 厚积薄发    时间: 2010-5-6 18:47
标题: 2006 年百度之星程序设计大赛初赛题目 5
座位调整
/ _7 s$ a/ Y+ I+ k0 ~% Z+ w# H& p) R1 J
题目描述：

百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。
# z2 G( ?# C! K6 I# Q( f4 d7 k
调整的方法如下：
, K7 |# h$ g" J, M1 D0 b  |
; X% A- E+ P  W1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。
- a8 N, }4 T( `4 T4 m; S7 W! [
2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。

! l) W! j6 ]5 u8 M) l7 @  [3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。

数据输入：
8 H/ x+ t' f- p8 Z* @( C! V5 L
第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。

4 N* t/ H: X& H1 S% J  ~第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。

紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。
4 W6 E# V$ e3 t# W  J( d  x
答案输出：
; G9 w( s% s# r- [
对于每个测试数据，输出可以达到的最大的喜好程度。
2 v* \4 i9 W( V
输入样例

3 3

1 1 1

  @  ]" R+ }5 S) J: m100 50 25

100 50 25

100 50 25
' o( _9 R$ p" N

7 Z0 j  G8 v0 B' a1 y% b- T) ^% M
输出样例

. i7 k4 q% _* W( N8 _- L7 f
175

! B6 t4 X1 ?2 B( }4 A  G: ^

7 j! {* c. n& J( {4 g' H1 u/ s
9 B  {$ e, M9 A8 W3 N数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175

---

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


! A5 ^- a) j2 q, x% s#include<iostream>
- v0 M  m+ N3 T; [3 ^+ L8 ^. Husing namespace std;
int b[3][3];//M*N矩阵
. o6 Q/ U0 Z8 e8 kint a[3]; //区域人数上限数组
0 g. R0 e, W1 K2 yint c[3];//记录某人i去的区域j
int sum=0;
2 i! F9 P+ t- R- }2 ~" Oint max_num()
{
5 D% q5 E4 ?9 {    int max=-32767;
    int x,y;
& a& [) T& P8 R% Q    for(int i=0;i<3;i++)
$ _' M# ^$ G" C: `( h    for(int j=0;j<3;j++)
. A* O' X) g2 U" C" ]    {
; I9 g7 Q4 j! F& V        if(max<b[j])
        {
( l' A  o9 A: w7 o. z* V. j            max=b[j];
2 b& C; X% @' M$ i6 ]5 f; V6 z# T            x=i;
            y=j;
6 U; M/ [( y) J. B5 Z* X
# N% q* G4 S+ R        }
4 _4 J8 d" I* M5 k    }
   
7 F' \# ?. O8 S) s- v    if(a[y]>0)
    {
/ `7 F1 i* T9 X$ g. C' P  |        c[x]=y;
! [: c. t7 \; ]3 j  x        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
        {
& S1 _0 w# R: N0 F: c/ |            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
- s! o1 y. \5 J: N- K    }
    else
    {
        b[x][y]=0;
. {$ b. q9 m% l% }4 }9 l# r+ I( k- ?; d    }
   
: b5 C3 O+ y9 P4 L9 W    return sum;
! ~+ K: O/ @3 e5 X}
int main()
{
0 L: P5 _" H3 p( i$ M' H$ o   
    cout<<"input 3 zone's limit:"<<endl;
1 ^( j% f' v3 b( @4 ~    for(int i=0;i<3;i++)
    {
        cin>>a;
0 E; h0 s: v$ s0 k& t$ M    }
- T0 z4 K3 A' E; _/ L5 d    cout<<"input 3*3 actangle:"<<endl;
# W! X5 Q' U& K+ O6 z0 p4 \. Z    for(i=0;i<3;i++)
- w5 M0 ?/ C' C9 C" I    for(int j=0;j<3;j++)
7 G6 v& u" M" b) b; C- `$ m: E    {
        cin>>b[j];
8 `; {2 S$ b' ?8 f5 _1 p    }
    for(int k=0;k<9;k++)
/ t0 o- S9 G; L% b! n" }  l, n6 b    {
        max_num();
8 p0 A7 L+ b* ^! M- k, U    }
   
    cout<<"sum="<<sum<<endl;
+ I9 @* d+ R& N1 d. \2 d    cout<<endl;
( R! }/ E9 m8 Y& w8 P    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
' `. U+ x) v" E    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
! ^8 W, \7 f4 j2 e" ~+ ?, X    }
' L* L6 D0 [2 {& V7 Y) J5 X/ z    return 0;
' C% T# F2 ?$ p6 F+ j4 W}#include<iostream>
using namespace std;
$ [$ x6 g, }% \" b; W% Z! F1 Gint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
& n! I9 y5 l' m0 _int sum=0;
int max_num()
{
) q( I' r4 R$ f( Y; D; Y; K5 k% q    int max=-32767;
! h+ _0 ^# I$ q. \    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
1 w& @! t" V! M" [7 o        if(max<b[j])
5 r& a1 n4 p" \! w        {
            max=b[j];
# m$ [" H! I- B# @, s) b            x=i;
" ]0 N5 h% H, }: w            y=j;

2 N3 O& h% v' R        }
! \" O& b1 g( r# T    }
   
# W# s+ U6 C" m- B8 x* L    if(a[y]>0)
1 l" ]- s: B0 w    {
        c[x]=y;
2 ~0 W$ D- }" Y0 Q" Q9 p; d; y! m+ z, t        sum+=max;//总喜好度加上添加
, B! V! f2 u6 E& h4 J3 A+ R' S3 n        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
        {
8 Y$ T  n% q" P7 l  e0 ]            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
    }
0 g* Y- W) n6 s* w8 B    else
: \( n, M# e/ E0 F; r; M    {
        b[x][y]=0;
2 N! D( P" I8 o- X/ _: y- C1 A    }
   
3 Q4 v" a# G% U2 A1 S6 K1 r( d$ L    return sum;
}
int main()
{
- R6 Z6 K9 M# x3 j+ i: h% I1 Y   
    cout<<"input 3 zone's limit:"<<endl;
! X3 ], g0 Q$ p- A. i1 c5 V    for(int i=0;i<3;i++)
* B5 ~. L/ v* f; M1 j& s3 k* Z    {
        cin>>a;
5 Q; s( `  S4 E) e0 C    }
6 I4 ?- G1 o/ c$ z- W) W, l. R    cout<<"input 3*3 actangle:"<<endl;
- p$ N" }; `* C2 {2 y  X    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        cin>>b[j];
    }
% W* g; _) |( ~+ Y8 M    for(int k=0;k<9;k++)
    {
        max_num();
    }
   
0 k% ^5 B4 u$ k) v1 e9 E/ H' W( x    cout<<"sum="<<sum<<endl;
    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
5 B5 R! l' K) W    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
- B: ]' g; o; \" k5 O# `    return 0;
}

---

作者: 厚积薄发    时间: 2010-5-6 18:48
编程代码二：
#include<iostream>
#include<cstring>
. d, Z# ~8 H5 s: a& I#include<ctime>
using namespace std;
! k9 A1 Y# }$ b% Y# pclass ifo{//矩阵的元素
& ]4 b$ s) k% i, S" ]    int clerk;//员工号
2 b# D$ v- x) c7 w  @$ L! H    int area;//区域号
    int per;//爱好度
  c! w) R$ J0 s/ E! M3 jpublic:
0 P" x# f  S" \    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
- K( o1 P% h  v* b7 n    int getclerk(){return clerk;}
    int getarea(){return area;}
( ^" X/ k( A+ S+ h4 O( D# S    int getper(){return per;}
    void setclerk(int i){clerk=i;}
    void setper(int p){per=p;}
9 V2 [7 Y* e6 Z2 @0 t1 [5 ?; P    void setarea(int a){area=a;}
};
. ^4 q7 \! W, Q$ j$ wclass area;
class clerk{
    int areanum;
    bool isin;
    int inarea;
1 o. K0 R8 }, R: J0 U6 zpublic:
    void set(int num){isin=true;inarea=num;};
' w9 \) b2 B0 }! f+ r& _    void setisin(bool b=true){isin=b;}
8 W7 p/ z  P  ?3 j. c. S5 g    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
};
class area{
    int num;
2 r2 u% `$ v; f9 q& I  S    int max_num;
1 K. ]7 W3 {8 ^; l3 h) P) S, C  ipublic:
. k0 k: p; \7 J% T7 U! u. O3 J/ |    friend void set(int);
5 e* X8 E! ?4 @/ q7 f2 b    int getnum(){return num;}
    void setnum(int number){num=number;}
    int getmax_num(){return max_num;}
    area(int number=0){num=number;}
7 @3 K8 `4 Z. W" H    int getclerk(){return num;}
    void addclerk(int ps){num++;set(ps);}
};
% ]5 E$ W- D6 @4 H: }8 ~void getorderbyper(ifo array[]);
  I2 X: C0 N- l: G0 X9 f: Kint areanums;
" a# _, r- R6 v' Y% O1 m% Jvoid main(){
: z  [; L- l$ b9 |0 O, d/ ^: \( y    //input
4 w% f* U6 N) B) E/ s! a    cout<<"输入区域数：\n";
    int area_num;
    cin>>area_num;
5 J6 h5 o% {: a5 P    areanums=area_num;
5 o5 T* i& U7 L% `6 Q1 f    cout<<"输入员工数：\n";
: y* ^5 d8 H2 h! c' ^& t    int c_num;
    cin>>c_num;
    cout<<"依次输入每个区域能容纳的员工数:\n";
! D7 G& h2 M' P: I# F& B7 q    int *max=new int[area_num];
    int nownum=c_num;
    while(nownum){
        for(int i=0;i<area_num;i++)
8 `5 J6 G4 a9 `9 Z        {cin>>max[i];nownum-=max[i];}
* ~+ M2 |) Q0 Q8 r; u' G& R        if(nownum>0){
  L3 Y+ ~  C4 z  Z! v* ^            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
            nownum=c_num;
7 o! j, r" {' \' y9 A8 v" J8 I$ i        }
/ X: c5 W" |( X  G  k$ {  K        else nownum=0;
    }
* H' K% P5 t; R, ]    cout<<"按行输入每个员工的偏好：\n";
    ifo** per=new ifo*[c_num];
3 Y$ p: Y  S- T% G' V/ s* m    for(int j=0;j<c_num;j++)
! n1 J  N6 c1 H& c6 t& O        per[j]=new ifo[area_num];
    srand(time(0));
    for(int c=0;c<c_num;c++){
6 c% i5 s) p3 ^4 |        for(int a=0;a<area_num;a++)/*
7 H! Y  u* _' A( ?) F0 `( V* d        {    int p;cin>>p;per[c][a].setper(p);
1 |! \5 D* o8 K) U8 J4 ~            per[a][c].setarea(a);
            per[a][c].setclerk(c);
! _: u  I: S  a+ ^' J+ {0 }        }
# p: B0 \0 j" m: T7 f        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
' {. N% J: E+ a1 C+ `! s        {    per[c][a].setper((rand()%60)+40);
' N; @* v/ c, w  T/ s7 b            cout<<per[c][a].getper()<<'\t';
        }//测试时懒得输入，故以60-100的随机数代替。
8 `$ }0 u, i0 g4 w-    cout<<endl;
( {- K& r! y8 n7 ~    }
2 y  h* z  u7 ?: z    //output
        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
/ o% R' G( }1 c) E! d# y, ^/ z$ |        clerk* people=new clerk[c_num];
        area*  areas=new area[area_num];
        int totalper=0;
        for(i=0;i<c_num;i++){
  n7 h$ A5 l% S) C9 P            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());
                people[i].setisin();
                int number=areas[per[i][j].getarea()].getnum();
8 q$ M1 U1 J' R: Y& q                areas[per[i][j].getarea()].setnum(number);
                totalper+=per[i][j].getper();
                break;
            }
# o/ e2 ?; w7 t/ Y        }
        cout<<"能达到的最大喜好度为："<<totalper<<endl;
}
void getorderbyper(ifo array[]){
5 v" Y: _+ |; _) ~0 \6 V1 N( ]    int max=0;
- l9 ~# {2 T( ~+ M; T1 J/ |% g    for(int i=1;i<areanums;i++){
        for(int j=0;j<areanums-i;j++){
        if(array[i].getper()>array[max].getper()){
( q( P* [5 ~9 g# k) l$ c            max=i;}
        }
. X2 c/ C/ i* ?7 B: v) }( \, G        ifo temp=array[max];
        array[max]=array[areanums-i];
        array[areanums-i]=temp;
        max=0;
0 b- J* M' H% Q; Q    }
+ d2 ~; C: \( P8 S}

---

作者: 厚积薄发    时间: 2010-5-6 18:49
代码3：
9 O) q/ ^! x! U: y0 V/*
算法思路：
（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
再加，该人的所有喜好度设为0，
# P- k3 j  C0 e+ d% B& g（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
' C( \: B# w  F6 T  w( S$ M4 M（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
3 k2 B- u6 w8 O' B; V. L" }(4)最后输出总喜好度。
3 D( ?1 H) n) L: V4 T' q' @*/
# P) c( ^1 g5 B#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
3 {. T; g) I4 G" n( {int c[3];
7 n* u- c2 D3 Lint temp[3];
int sum=0;
int max_num()
{
- }$ W  p; ?: c2 J# c$ _9 O6 R; X    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
2 L8 L# C1 i" l+ Y    {
- C. |$ w4 n* f5 M* ~# a8 p: a        if(max<b[i][j]&&b[i][j]>0)
) B$ {6 q1 M3 S1 K        {
) v9 v" ^4 e; r2 h7 a4 x2 _6 T. Q7 S! K& [            max=b[i][j];
            x=i;
            y=j;
; w. y5 x- r/ o' c/ G& j
        }
    }
% V7 V1 V  d6 b) k   
- f* Z; R' }) F( H; M0 p* X    if(a[y]>0)
    {
, Y' f! X, i- U4 h6 L# L        c[x]=y;
: r/ G: Y+ G, n; y        //cout<<"c["<<x<<"]="<<c[x]<<endl;
5 C- n# p& U" ~  G, ]        sum+=max;//总喜好度加上添加
        temp[x]=max;
/ n5 p0 c' v  O- t7 ?        a[y]--;//区域上限人数-1
    }
    for(int k=0;k<3;k++)
    {
        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
& T5 J/ f5 ]3 N! A    }
    return sum;
+ f, U( j8 X/ s% F' M0 d7 U}
int main()
8 v" h  V3 W' F+ Z8 S) h{
2 `- Q  Y% E3 f4 y. L0 ~  c+ @' M   
3 N, W$ a- e9 e    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
/ S% U6 ?1 `! B9 p4 N9 |$ [    {
        cin>>a[i];
    }
    cout<<"input 3*3 actangle:"<<endl;
: y7 {% ?3 N* U) z  A    for(i=0;i<3;i++)
: N' A# o" Y  X) p7 [! v$ B    for(int j=0;j<3;j++)
, J) i* h* F7 }3 r( v9 w    {
3 c1 }) O9 u3 x* ^6 L9 D/ a& i        cin>>b[i][j];
    }
    for(int k=0;k<3;k++)
9 v0 R  s. k  q3 C' _; X6 N1 y    {
        max_num();
    }
2 `# M+ s* j8 p6 v4 J( m    //cout<<"sum="<<sum<<endl;
    cout<<"sum=";
    for(i=0;i<3;i++)
) [+ V1 y; n( W' C! k0 B    {
        cout<<temp[i]<<"+";
" l0 g5 a/ \4 a; Q5 I% v    }
    cout<<endl;
/ X# d1 V8 q7 F    cout<<"reslut:"<<endl;
) R9 t/ ]) k: x9 B    for(i=0;i<3;i++)
    {
; P0 B) J: R9 ^. J1 g3 X& y- Q# m        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
    }
    return 0;
; C; y0 \; d6 @, w}

---

作者: 葉_浅浅    时间: 2011-2-22 21:04
其实我一直觉得楼主的品味不错！呵呵！
, i/ p& v: P6 V, X) ]) X* r数学中国社区分享快乐！

---

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

---

作者: ehi28    时间: 2011-12-11 16:23
嗯,不错,支持一下.
" }4 x  L% ]& j$ \, ]2 B" `* [0 Z

---

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