2006 年百度之星程序设计大赛初赛题目 5

厚积薄发

座位调整
7 D( P' ]  B5 v
题目描述：
' C5 H0 a/ C* f4 Z
$ ?. K0 x, h5 T% S6 z: p8 Q百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。

调整的方法如下：
$ h4 Z' f* I2 {  w# P
1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。

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

& l7 X' R: _2 y/ |3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。
; E% z4 P8 _8 z: t9 W" R$ G) ?
$ @* z& k9 l+ E3 r  ?7 c5 C数据输入：

) i9 t% g6 T$ C. z' ?! {( @8 ]第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。
: N! C; r8 w( C9 @6 g! X
, g: a2 X* ]# n5 x第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。

紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。
8 `0 N( ~$ _! B. d; ~
+ P4 a& h" u3 }. g9 i; J9 l答案输出：

  ?& s$ `3 T' {" K; w! _( M5 c对于每个测试数据，输出可以达到的最大的喜好程度。
" F/ G8 g+ _8 i: [. C
输入样例

# x: D/ j( D8 K5 T8 q0 \3 3

3 m5 l5 v  R0 ]+ b6 r3 L1 1 1

100 50 25

100 50 25

- u% E+ `/ c' I9 a; K# ?& N100 50 25
6 r0 k, C, H$ I6 F

$ i' S2 h) s7 F" v2 u输出样例

% g- A$ {5 Y% D( W  f' m( n! [
175
7 g5 i9 Z: {5 [& M' b* l
' Y4 P2 D, w& i- e0 J: Z- I# K. S

数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175

厚积薄发

8 ?6 e/ O2 D1 |. I& o: X
: `! C& D% d8 s5 }# G#include<iostream>
- J7 ~1 B; @! m& fusing namespace std;
/ W! \: g3 P% q% U! n9 ^/ @int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
5 M6 H, p+ U2 Cint c[3];//记录某人i去的区域j
- R% l0 K# r0 F5 oint sum=0;
int max_num()
{
. F/ J1 \2 y8 i2 F    int max=-32767;
) \2 E0 C7 O" `4 d9 e0 O/ M    int x,y;
    for(int i=0;i<3;i++)
" Q, P1 S3 V; U( y) G  I& n# x    for(int j=0;j<3;j++)
) }: x: y7 L6 }    {
8 L7 ^0 e  D: Y0 w1 H" _        if(max<b[j])
8 I4 t+ K0 G' p+ @7 C# D: \% R        {
            max=b[j];
            x=i;
# z5 j3 D9 K3 a5 T/ N& B+ ~* ?            y=j;

* t5 I; U+ V4 K  Z  S; k        }
/ t, z0 ~+ f, [    }
3 r; r8 r: F" v" s" g" J% X" |3 S5 v  E9 Q   
    if(a[y]>0)
8 P. H% W; C% C: F8 h9 M0 z, q    {
        c[x]=y;
! k" M( h. ?& d        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
" q, q5 L4 a9 F2 ]+ d: e+ T        for(int k=0;k<3;k++)
        {
/ P/ X% a9 T7 s4 B; O$ s            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
6 M- }1 K% j& F8 v* i3 v. v4 |2 C4 V8 r        }
% f7 [0 @4 _# p& i0 F* }4 K$ T    }
    else
8 l; l+ M) d, V: }7 \* t    {
" G  X" v3 P8 k& t4 g( M( E! O2 G        b[x][y]=0;
    }
% D% s' F- d! q3 ^& o3 }* j- p   
    return sum;
4 j9 i0 r# N& W& g* r}
int main()
( F9 f) b6 J+ E, Q2 Z! m# E. p{
, i( K1 l% y4 q( p7 _) \% }   
, a, i: h$ s( B7 r7 u) r' q8 E    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
/ U/ O' O, g2 p5 q2 p0 ]0 X    {
        cin>>a;
, `0 e& H& q6 V% |" a) @    }
3 _) t' q. s  u% q    cout<<"input 3*3 actangle:"<<endl;
7 b2 Q* o  b$ T- H/ k% r    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
% f8 R! N7 O6 {) U! q    {
        cin>>b[j];
    }
    for(int k=0;k<9;k++)
7 {. X- V' I1 `% k, t    {
; G: _6 k( L0 L! [3 \! N        max_num();
    }
) r+ W& Z3 o* |   
    cout<<"sum="<<sum<<endl;
    cout<<endl;
8 d& D; b& m7 A: R0 \1 t$ G    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
! }1 E3 m; v' o& }    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
1 ?4 s* R! f8 g; v9 }5 ~% P/ l    return 0;
}#include<iostream>
* Y: k) {1 B# j  B, |8 `using namespace std;
) ?/ I" e2 g$ t/ z8 c# }8 ~int b[3][3];//M*N矩阵
1 t8 ~" G4 Q# ?' o. pint a[3]; //区域人数上限数组
6 u  F$ `) t$ g1 W( w2 iint c[3];//记录某人i去的区域j
int sum=0;
# ~+ z( ^1 h& xint max_num()
{
0 X# D; X5 Y8 y0 E9 ?+ P( g    int max=-32767;
    int x,y;
; L! X. w' `' j% Y/ p- N    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
( b9 N. u: s8 [6 _6 R$ f        if(max<b[j])
# v( Y9 F8 o' s# c        {
. h4 U- v$ o. b: |, J            max=b[j];
            x=i;
            y=j;
, V. u6 }& K- h# ?% R. N
: P5 i+ N$ N7 g- D* z        }
    }
. E. D8 K1 ?$ D- V7 u. j$ A  z   
! F* d# Q7 W! k% I: a    if(a[y]>0)
    {
        c[x]=y;
% x  [! x0 y5 E+ a. D% p6 v9 }        sum+=max;//总喜好度加上添加
6 T5 l' I3 A; r$ R        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
        {
$ S, S8 u: m. q, f5 P* @. Q9 R# O            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
    }
3 O" _3 u$ z! t  t* t7 ^# E8 s    else
0 o5 x; ]" n- R" e7 g+ t    {
        b[x][y]=0;
* Y8 c/ r0 D8 a2 ^    }
   
    return sum;
6 w; _4 m% X1 D, B4 G}
. T6 J9 c3 }& w9 L; a, wint main()
/ W7 k7 g* _- z{
   
  r" c( W: v( @! ]: Q! q: n6 j    cout<<"input 3 zone's limit:"<<endl;
7 o7 t; h- p0 l/ [    for(int i=0;i<3;i++)
    {
- p; J- j8 ^# ]! F! i; ~  c        cin>>a;
    }
    cout<<"input 3*3 actangle:"<<endl;
7 f9 }4 Y  |! C. r5 [    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
& ~9 f2 _# y( T; [! [3 R7 C    {
0 r; N* S9 i' N2 h# _' T9 `3 Q        cin>>b[j];
    }
* y0 b: s" |- h/ H/ h; B    for(int k=0;k<9;k++)
    {
" H5 `/ t; y2 t9 _% ?+ l        max_num();
    }
   
' L' o9 w3 V6 ?3 }. |# M/ H( ~7 ]    cout<<"sum="<<sum<<endl;
    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
# \% n* T* P6 `3 B) t+ y' z        cout<<"people "<<i<<" go to zone "<<c<<endl;
% k- n9 n& g8 r% E    }
    return 0;
- g4 Q% {% h& W  |- z" w; U}

厚积薄发

编程代码二：
#include<iostream>
#include<cstring>
#include<ctime>
4 w2 y. U" v5 D5 gusing namespace std;
class ifo{//矩阵的元素
    int clerk;//员工号
; J& k* J/ E* f/ R$ q0 e6 N. l- W- N    int area;//区域号
( ^( C8 L/ e8 v# v    int per;//爱好度
public:
4 e% z4 g) H0 a( J+ _    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
    int getclerk(){return clerk;}
. {. x" J! `$ u    int getarea(){return area;}
    int getper(){return per;}
* s3 q" i; i- q# T, {1 l    void setclerk(int i){clerk=i;}
: t# C5 S0 Q$ s& C& C: Q    void setper(int p){per=p;}
( C$ ~1 r# s: [$ P+ l; J) e    void setarea(int a){area=a;}
& J! e# n  t% }4 }; Z/ R( `5 D};
class area;
9 \' u5 j, d3 @& |% U$ Y8 Jclass clerk{
7 X6 P0 V8 A, m" Z8 F& K    int areanum;
3 W. D3 I* ^/ ^    bool isin;
    int inarea;
- {$ n* y. ]4 t, s: t5 s. E* C# P" v% lpublic:
$ y# O) }7 v1 N. m    void set(int num){isin=true;inarea=num;};
    void setisin(bool b=true){isin=b;}
- X( {8 _1 L/ p) p+ K6 ?. Q    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
. l, b  C9 j; {0 L+ g* ^4 c/ E0 w. T};
1 ~" u8 [8 w  M* Gclass area{
/ h- w9 N  O8 I9 j( W0 c    int num;
8 \7 ~6 H5 F  I) t; _; ^5 O    int max_num;
5 a" G' E9 z" X0 P, F$ `public:
6 M' S  J( r1 T- O$ R9 z" O    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);}
};
, |& o6 u( W; q9 P$ M# ivoid getorderbyper(ifo array[]);
/ r- T9 C: d5 N, D0 C" oint areanums;
; \7 s! _8 o3 t4 Dvoid main(){
    //input
) L) b- x* _6 E    cout<<"输入区域数：\n";
    int area_num;
    cin>>area_num;
    areanums=area_num;
    cout<<"输入员工数：\n";
; ~# ^' d" S: X3 C! ]! T0 I    int c_num;
    cin>>c_num;
    cout<<"依次输入每个区域能容纳的员工数:\n";
9 R0 k# d& Q  e    int *max=new int[area_num];
    int nownum=c_num;
    while(nownum){
        for(int i=0;i<area_num;i++)
        {cin>>max[i];nownum-=max[i];}
        if(nownum>0){
            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
            nownum=c_num;
3 g. B( e" K% Y; c4 x. u2 p        }
        else nownum=0;
    }
# D0 U* ~9 r2 u  ]    cout<<"按行输入每个员工的偏好：\n";
/ o5 K& C5 e  G9 x/ U  w    ifo** per=new ifo*[c_num];
$ ^  k4 h# T4 _* k* ~4 }    for(int j=0;j<c_num;j++)
1 d+ e: e+ u! @: R        per[j]=new ifo[area_num];
    srand(time(0));
; _4 v/ _4 K* i1 U" i4 j    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);
! Z- ?, H$ E# \" S$ V            per[a][c].setarea(a);
            per[a][c].setclerk(c);
        }
2 A: C9 m0 q- I4 D) E+ m7 Z) e# I        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
        {    per[c][a].setper((rand()%60)+40);
7 n5 B' F0 ^' u9 X7 v6 f6 s+ b            cout<<per[c][a].getper()<<'\t';
" u" P/ ^* Y1 V2 b7 C        }//测试时懒得输入，故以60-100的随机数代替。
-    cout<<endl;
! r6 D# V4 f% C+ t    }
    //output
4 M3 M* x# g5 O* [. O        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
        clerk* people=new clerk[c_num];
2 y& N* p, o8 O: W- U; o7 }  W        area*  areas=new area[area_num];
        int totalper=0;
        for(i=0;i<c_num;i++){
& M. ~6 S( ?6 `" U            for(j=0;j<area_num;j++){
/ W+ f4 m0 t5 y# r. Q' `, y            if(areas[per[i][j].getarea()].getnum()<areas[per[i][j].getarea()].getmax_num())
" Y' Q( K. J( t& D7 w; k                people[i].set(per[i][j].getarea());
                people[i].setisin();
                int number=areas[per[i][j].getarea()].getnum();
                areas[per[i][j].getarea()].setnum(number);
                totalper+=per[i][j].getper();
" O( {- t" h. q0 z( q                break;
+ g; h. p* ?, g! ]: L            }
        }
        cout<<"能达到的最大喜好度为："<<totalper<<endl;
4 |! U5 H3 V6 E/ w' T2 U" O$ N}
! v4 n$ e$ E* e: v% h( v8 vvoid getorderbyper(ifo array[]){
    int max=0;
5 }8 z1 U0 o/ ?- ?: p, w- C    for(int i=1;i<areanums;i++){
3 y$ Q, P8 i. e3 J2 x: q        for(int j=0;j<areanums-i;j++){
/ e& P  T3 b: X# X8 q7 K        if(array[i].getper()>array[max].getper()){
            max=i;}
        }
        ifo temp=array[max];
        array[max]=array[areanums-i];
& b' k8 a- S9 g. O$ P4 V        array[areanums-i]=temp;
        max=0;
+ i5 e: c+ k/ M9 z    }
* ]0 C# E/ ~* }/ G- I}

厚积薄发

代码3：
/*
; n; G+ y  V, V" s算法思路：
（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
再加，该人的所有喜好度设为0，
; }0 k% C% I  t+ Z& i& q（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
0 Q4 D, v! D7 v$ E' Q5 @+ `3 r（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
/ M1 U3 k9 O. u* i8 o# t4 i' j(4)最后输出总喜好度。
*/
2 b7 Z- s1 P" @  V#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
) B' ?! o/ T2 e6 D7 ^4 Zint c[3];
- D  n8 z) o3 z  \% {. U: P2 Oint temp[3];
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++)
    {
7 f1 A) F- x8 }1 |, I% q        if(max<b[i][j]&&b[i][j]>0)
        {
( `8 e) q: \9 k" c, D( N* R            max=b[i][j];
            x=i;
- ^# ]8 j# I" ^. e            y=j;
) s6 z- ~0 ]5 R4 ?2 Q) K
        }
    }
   
- Y/ I6 D5 ^( U5 F0 ~% W! H    if(a[y]>0)
  C$ z' T% E$ W    {
0 F% H* F9 h5 G; j. P        c[x]=y;
1 l; [+ B0 Q5 E, f; c        //cout<<"c["<<x<<"]="<<c[x]<<endl;
. d) S( o: d5 a2 y0 L        sum+=max;//总喜好度加上添加
* d" c7 t. W- M1 S+ d5 Q1 D        temp[x]=max;
        a[y]--;//区域上限人数-1
5 ?0 B' |% e+ U/ Z; T    }
+ j0 X2 v! l6 M8 d% J    for(int k=0;k<3;k++)
1 L$ C, C0 W& q6 Y8 f! ^    {
) z- ?6 y( Y4 l" j) p        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
9 a$ E( g1 ]( w+ G  d    }
) p8 ?1 O; o# z/ c  v# D- K6 ~5 A' E    return sum;
7 d$ |; B: F5 N  @* x% _' j! E( W}
int main()
. @) g& Z1 Q+ Y9 b8 W{
   
* v/ D2 }6 S; Z3 P  l' \' Q    cout<<"input 3 zone's limit:"<<endl;
) w( j* X- r5 a9 t) U    for(int i=0;i<3;i++)
( g0 e* N6 X) ~# i* r* x( v- z. m# G: @# a    {
6 a, M3 K2 i8 I3 ]* o) U9 ^1 V        cin>>a[i];
" g- R5 F% \; c- h2 t0 m$ \+ F4 W    }
    cout<<"input 3*3 actangle:"<<endl;
2 W, i3 T" i/ u2 a9 l2 K    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        cin>>b[i][j];
    }
    for(int k=0;k<3;k++)
# c2 |/ Y$ j0 {+ k' e    {
. E8 Z0 l3 F) B7 T        max_num();
    }
  z- ^& t5 C$ x, Y# N5 U; P    //cout<<"sum="<<sum<<endl;
    cout<<"sum=";
/ X# E5 D* t, F  t$ Z- F& f7 Y    for(i=0;i<3;i++)
7 C. _; z4 O6 ^8 u7 ~7 ^' u6 z: l    {
0 u' u- ?7 o0 F! h5 i        cout<<temp[i]<<"+";
    }
    cout<<endl;
# f, t8 k7 N2 p* o9 T5 M  W    cout<<"reslut:"<<endl;
- E2 n. I+ b: X9 J    for(i=0;i<3;i++)
. J1 j8 Y/ p  N( p. P/ |) Z; A/ F    {
3 h9 d6 [% [# R2 y+ u# j        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
5 J8 M* F, C) h2 X    }
    return 0;
5 g% z$ Q  x* ^6 [}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
数学中国社区分享快乐！

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.
, A5 a+ K4 t  M4 H) T, r

schnee

必须顶！！！

久玖九王

C++,可是我喜欢c语言的，只是现在还没有到家

hbdkfk2

看不懂！！