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

厚积薄发

座位调整

5 R8 o9 a9 }' ~题目描述：
" ^2 E3 }# h9 \7 e) \
% L+ c3 c+ f7 w6 s: W- P百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。

$ r* u) V* f7 M% \调整的方法如下：
) J" x8 e% A' v
6 O/ I5 W/ g& c( ]2 {1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。

: w' I9 j# f: J  r$ J1 C2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。
0 R8 I4 W$ _$ A! ^
3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。

6 T% @( ^" W) I# G数据输入：
" }' O; H4 ]- l1 ]3 F0 A
第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。
8 v' L! N; [& j2 i  ^4 S; Y) N
  g9 Q+ N& l" y1 D8 E( \7 i第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。
/ h, Y9 E) F, N' R) Q
. M( c# u9 m9 b( W* B1 W, V& u紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。
; l$ }- w4 _- {- X. G
2 h& V2 d# F. {2 g9 e# z4 R9 r答案输出：

3 m5 W' c4 P  l$ Z- ]) C/ P对于每个测试数据，输出可以达到的最大的喜好程度。

输入样例

: [8 D' H8 D  H) D% _; F3 3

1 1 1

100 50 25

# U4 c$ o  i  i2 Q; T1 b  y100 50 25

100 50 25

输出样例

) `' _2 F: q  C, q$ T6 F3 w
0 R6 M2 g; ?: R# f175

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

厚积薄发

: `) z6 t% A: _3 |; k8 P& ~  v
: ]# m& X: @% `/ x& K4 X( C#include<iostream>
$ s) |/ K; \- L! rusing namespace std;
, |8 X8 V# }; j/ E" M7 _) T& kint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
/ t% _+ m1 t# F% ], _int sum=0;
int max_num()
{
6 ]; k) t1 t+ W    int max=-32767;
3 E1 Z  {& x& w0 J: w% _$ H) k& M% R    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
: v! M3 K  t# w- n( `    {
) O5 C/ q% Z) l* x; O* S2 ~        if(max<b[j])
        {
: l" T# j2 J, o/ Y& m            max=b[j];
6 L/ X; R) e6 ^- a3 u            x=i;
: _) c4 h  _% e            y=j;
# N2 ~0 x3 K2 R1 @( L# ^& b
        }
    }
) \& M/ x! R; T* f   
    if(a[y]>0)
    {
1 I' w1 F% _* `1 m0 Z3 {        c[x]=y;
" t& @( e6 A* [0 _; @& Z; Z* L6 H# k        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
7 M2 k4 X, _  N) ^1 G        for(int k=0;k<3;k++)
        {
, p2 q/ Q+ j( k- T* A1 P            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
    }
    else
! |7 I; J! X' K    {
# j# m. F: Y& M        b[x][y]=0;
    }
   
    return sum;
}
int main()
{
   
7 a( m4 h- }0 M) {    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
0 i$ ?9 V' q2 v, s    {
        cin>>a;
  c% T3 O2 J- S6 _- _9 d# I    }
    cout<<"input 3*3 actangle:"<<endl;
; `- C& K+ S# g$ q% ]    for(i=0;i<3;i++)
1 T0 I5 R9 x3 ~& c* S* q    for(int j=0;j<3;j++)
) H, C$ f& n4 s6 v* O0 S/ ~8 W: f    {
1 \, K8 s6 P1 @1 `        cin>>b[j];
    }
    for(int k=0;k<9;k++)
1 x. ]/ q4 @" P0 V9 x% n9 g    {
        max_num();
    }
   
7 `8 K' H9 p5 p    cout<<"sum="<<sum<<endl;
    cout<<endl;
% d, G4 e4 k$ h" x* q" \! @0 d    cout<<"reslut:"<<endl;
' B+ e% \$ ?  U4 O7 L. W# ~    for(i=0;i<3;i++)
$ j, V- ^9 w3 r  a4 c  e" ~    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
5 m  `3 Q$ |! l    }
2 H* c4 }  w. p8 A    return 0;
}#include<iostream>
  ~" C/ W0 O6 ~' X5 z( S0 nusing namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
7 Z3 H* y5 x! S5 r6 R/ Y; mint sum=0;
int max_num()
{
    int max=-32767;
- f! ]# t) [3 Y2 M    int x,y;
: [9 s9 m  O+ @    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
6 i* A. U8 N' N7 a2 R. [. W3 r4 M: r    {
        if(max<b[j])
, w1 S% T5 N' t        {
            max=b[j];
4 r/ r  k2 f  t6 l. u' @$ x            x=i;
) R4 }9 v6 d2 B) [            y=j;

        }
    }
   
* G0 @; K7 M' O- a) b$ }5 d  ]    if(a[y]>0)
/ _% a) {9 S" I$ y$ C$ E    {
. Q5 j! o3 w6 \3 o        c[x]=y;
        sum+=max;//总喜好度加上添加
6 m4 i% i& J5 L# r        a[y]--;//区域上限人数-1
: C2 Q$ U/ s+ `& m2 n        for(int k=0;k<3;k++)
( N/ {. d7 V! `$ G        {
& r) v# T/ p* E6 G5 e            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
! v' `3 Q, K& G+ Y        }
4 o# ?; H( ?- S0 ]    }
( l  `4 u( ^& c% d, a1 ~    else
    {
  m! J$ d. p' D# |* P3 n; U! w        b[x][y]=0;
5 L' f4 v0 f2 P    }
( R' T8 B* B) P& K/ {9 A" W6 C   
, i& }3 H6 ~4 d    return sum;
}
, c1 D  \" O( H: r. Oint main()
{
   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
    {
( c% J  f6 q8 Y) a        cin>>a;
+ {, u3 D/ I& }7 {+ @1 P    }
% \' m: R  p6 J  K' S+ }% ~" a    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
$ p% r- e1 J, F2 T3 a/ C: ~$ X  ]/ P    for(int j=0;j<3;j++)
    {
        cin>>b[j];
    }
! F9 {. ]) O8 \& q3 N9 U4 }, h    for(int k=0;k<9;k++)
1 a. W6 k9 J8 T3 u& W7 D    {
        max_num();
" v4 E, z- N+ Z" k    }
   
    cout<<"sum="<<sum<<endl;
8 w; y4 Y( e: R0 D    cout<<endl;
8 m0 a! b" D( k# Z6 F1 S* n  I- d0 Z    cout<<"reslut:"<<endl;
  I8 x9 \7 a0 g9 q& o5 |    for(i=0;i<3;i++)
    {
: A) `4 `. |  y, `        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
, y) W" k! N% K8 N$ _! }( [    return 0;
& P5 Q' F. b$ g4 }& P- `3 J  z: }}

厚积薄发

编程代码二：
#include<iostream>
#include<cstring>
7 ^. Q2 ?$ r1 }' j9 L  ]5 @#include<ctime>
/ a8 S1 D. h1 R3 j0 Husing namespace std;
! m6 A% E$ F; p9 w* q6 Oclass ifo{//矩阵的元素
    int clerk;//员工号
) _, F7 U7 ]: |" e! P7 H& H    int area;//区域号
    int per;//爱好度
public:
- {6 h7 @2 t1 P4 x: L2 R- m- g# q    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
    int getclerk(){return clerk;}
    int getarea(){return area;}
1 V$ J( J5 E2 R8 @/ D" i4 {    int getper(){return per;}
% C) a- _1 n' |- |8 X# J  o. I    void setclerk(int i){clerk=i;}
    void setper(int p){per=p;}
    void setarea(int a){area=a;}
& G; y! n$ \/ O9 @};
class area;
class clerk{
. w& j+ L+ o" I, p( |, M4 v5 p; W/ j    int areanum;
    bool isin;
+ D* }) b/ j2 D' {  l9 M  T7 W3 d    int inarea;
public:
' g3 ~* S& }6 U: j6 k, h    void set(int num){isin=true;inarea=num;};
7 E, A5 y, {( r& W    void setisin(bool b=true){isin=b;}
2 N2 u$ ^5 J6 }4 R+ W! t    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
! W3 B6 V/ ]7 z6 n};
* W( }/ j, q: m4 jclass area{
9 u3 t' q% x3 N2 |6 C, l( w) y. A    int num;
    int max_num;
( B! F1 ~1 \; k' Q& r) l& n! m; h8 epublic:
    friend void set(int);
, n- b0 f$ c6 Z$ p- e' y7 `    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;}
! Q- \& E. L' v( Y( _    void addclerk(int ps){num++;set(ps);}
2 d  x; U& |' o5 q0 [- K};
void getorderbyper(ifo array[]);
4 C1 }4 j! ^# r) J2 ?" Oint areanums;
void main(){
/ l, k, z( N1 \, x0 R    //input
+ D* y$ c5 k9 ~3 |2 \    cout<<"输入区域数：\n";
    int area_num;
' n# o6 u8 i2 s$ q4 A    cin>>area_num;
/ Q' J" a: Z+ }0 J    areanums=area_num;
! N/ e  C+ A/ p2 `3 j/ ]8 a    cout<<"输入员工数：\n";
4 w4 k* l& q4 k4 \6 c    int c_num;
    cin>>c_num;
5 B; x; ^- K4 n7 w    cout<<"依次输入每个区域能容纳的员工数:\n";
    int *max=new int[area_num];
7 ]% I! ^* `3 M    int nownum=c_num;
    while(nownum){
        for(int i=0;i<area_num;i++)
; l" q6 T+ F1 G% o. O1 I) G8 r        {cin>>max[i];nownum-=max[i];}
0 S% B0 }" C5 E$ O+ x        if(nownum>0){
4 |1 K" i* }% R# S  I2 o- T            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
( s  \7 d3 z" }& `            nownum=c_num;
        }
        else nownum=0;
- t* G: Q+ f' m: I3 K7 y7 q3 D! j: C    }
6 A5 B& @8 Q0 p    cout<<"按行输入每个员工的偏好：\n";
    ifo** per=new ifo*[c_num];
: \6 S& Y& @+ e# \& U2 w* Q3 Q    for(int j=0;j<c_num;j++)
        per[j]=new ifo[area_num];
; P+ o' M- J" I0 T  G, z3 j+ Z    srand(time(0));
- Q* B/ ]- M$ M6 g7 p2 F5 m1 q    for(int c=0;c<c_num;c++){
        for(int a=0;a<area_num;a++)/*
+ c  l3 B+ R8 X* E# n+ S8 B5 q        {    int p;cin>>p;per[c][a].setper(p);
7 y' R3 O- \% z. q            per[a][c].setarea(a);
            per[a][c].setclerk(c);
* l8 H8 `, r  }" j6 ]        }
2 `+ _! l* G5 I' e" a* f        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
        {    per[c][a].setper((rand()%60)+40);
            cout<<per[c][a].getper()<<'\t';
9 N# Z! s5 \$ P7 b* ]        }//测试时懒得输入，故以60-100的随机数代替。
-    cout<<endl;
% l  f- U3 n, F" u/ m. H$ Q    }
    //output
        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
        clerk* people=new clerk[c_num];
' m+ o  v; t3 \7 y+ e        area*  areas=new area[area_num];
% y& I/ `8 ^# x1 `        int totalper=0;
        for(i=0;i<c_num;i++){
            for(j=0;j<area_num;j++){
, h4 `' v! l4 e, G6 P) G            if(areas[per[i][j].getarea()].getnum()<areas[per[i][j].getarea()].getmax_num())
4 F! e" J0 ?6 j; w# ]$ @' U1 T                people[i].set(per[i][j].getarea());
" W# C& t% u1 P                people[i].setisin();
                int number=areas[per[i][j].getarea()].getnum();
                areas[per[i][j].getarea()].setnum(number);
; J* C" U6 I4 t6 u9 v' ~                totalper+=per[i][j].getper();
" A* O7 d" ~8 K+ f! M( y                break;
            }
0 N/ D/ P3 ?: K: g8 y        }
        cout<<"能达到的最大喜好度为："<<totalper<<endl;
}
void getorderbyper(ifo array[]){
# a% f& c: n) i$ G% p- ^    int max=0;
. @6 \6 A8 }- w4 \, A1 [    for(int i=1;i<areanums;i++){
& l( ~2 z- T4 a3 }6 i: W! g/ ?; j        for(int j=0;j<areanums-i;j++){
        if(array[i].getper()>array[max].getper()){
+ s9 F- }! e$ _& G            max=i;}
! i0 R8 T5 T9 Z, ^5 p* w4 W( i        }
        ifo temp=array[max];
2 W' l, O2 R% P8 E. ]/ N& E' u        array[max]=array[areanums-i];
        array[areanums-i]=temp;
        max=0;
5 l7 ?+ u, V& f- O! G7 o+ L# G    }
& f% J0 M) e% h5 N( H; H( b}

厚积薄发

代码3：
% q6 y4 P5 u  \; J% }/*
算法思路：
（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
8 |) t# u1 y% r! R1 T2 d) b再加，该人的所有喜好度设为0，
6 S3 m& ~1 K% O7 \% m6 w（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
. s0 Y/ E9 O7 I4 b- |（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
$ s! W) w8 e5 W- j(4)最后输出总喜好度。
*/
#include<iostream>
& g6 Q) T4 E: ^2 A. o% g- a) C' Fusing namespace std;
2 J# X2 i) P3 Z  m( Oint b[3][3];//M*N矩阵
2 q8 H: C# Z! G2 j5 ~int a[3]; //区域人数上限数组
+ N1 Q9 m5 ^# C3 R, f3 aint c[3];
int temp[3];
- w  w: ^* R3 S7 Aint sum=0;
int max_num()
{
  s8 h% p; b2 P  T6 P3 ?# `    int max=-32767;
    int x,y;
( @" U% C, W: \( T' W3 O, K    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
1 D$ K# ?7 r8 r; |' R6 P1 N' q    {
: A4 D) `# q. S7 w7 K        if(max<b[i][j]&&b[i][j]>0)
        {
  G- \# f( Q1 |% A2 k; H- J4 a# ]  ]            max=b[i][j];
            x=i;
, a0 Y7 J4 `" `. n# D2 t            y=j;

3 Q, u2 R( E( f$ i: z6 G        }
6 S2 S. K5 T0 G' h/ G9 J; g9 d    }
2 B5 ]' P$ f9 w: e   
6 ^$ e" }* t( x: w    if(a[y]>0)
    {
        c[x]=y;
, Y+ V. e+ R& D2 r) j        //cout<<"c["<<x<<"]="<<c[x]<<endl;
* P% M. V, g+ {6 a        sum+=max;//总喜好度加上添加
        temp[x]=max;
        a[y]--;//区域上限人数-1
    }
    for(int k=0;k<3;k++)
    {
        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
; s* |! |4 n; z4 ~    }
! |2 s3 h; ?+ O9 u3 D    return sum;
}
8 o$ i" u  A! |$ x" a8 kint main()
5 d! u# L  H1 g) n. u6 h% j+ d{
   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
    {
! e4 F* S+ D2 k5 a# C1 M6 ^        cin>>a[i];
    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
/ |' g8 ~- R0 v. |" u1 E4 D; h    {
$ g4 ~+ j9 g0 `( k5 {        cin>>b[i][j];
: J" f8 R2 P1 }$ Z/ y3 g    }
    for(int k=0;k<3;k++)
* G2 Y! s& M; Q7 D/ t& ?. i& T    {
        max_num();
    }
% E/ L& N- K1 W) w' }9 C    //cout<<"sum="<<sum<<endl;
3 K1 Y5 b$ ]  _. ]    cout<<"sum=";
    for(i=0;i<3;i++)
8 [5 y6 \0 Y) v# p' x    {
        cout<<temp[i]<<"+";
. J" H& @8 F% f4 W. d) L    }
    cout<<endl;
% R. I' T" m! i& X% t; H    cout<<"reslut:"<<endl;
6 w: i" T( {' v' m% S7 e: I    for(i=0;i<3;i++)
) T0 s- I! D( s( l; x    {
, _$ N6 C1 _; p# N  C; e8 ]0 ]2 D! ]5 \        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
    }
# a* V9 T8 I6 z9 B    return 0;
. ^3 H% u* Y1 @. u}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
数学中国社区分享快乐！
4 t" L$ M! N/ `. G: s0 G

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！