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

厚积薄发

座位调整

题目描述：

1 x9 j. S% K& R: u, J百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。

调整的方法如下：

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

2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。
7 i/ C( k" W0 J! p1 o) D6 w. A
3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。
# d: m* f$ T# n; K9 z1 @7 q
数据输入：

! [! g0 T# S" z& f+ K第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。

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

紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。
" j/ i; W7 k, n# k  H' ]
答案输出：
& D6 t' N- |- Q& Z
2 `1 U! l+ c! [" t对于每个测试数据，输出可以达到的最大的喜好程度。

输入样例

, v( ^( M; z) I" O3 3

* W  E0 E, i+ @4 Q  R6 N1 1 1

100 50 25

) L5 q' c( M4 v1 Y. N# P100 50 25

100 50 25
, a% n# p9 ]: N4 D

输出样例

  \; D9 Y# O* C1 [! n) A* J* o
. O: X/ f: M, Q4 @7 H1 S) J; A175

2 F. R1 L1 y( Z* X: K  M4 Q

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

厚积薄发

0 z( A: g6 w2 c9 }& p
#include<iostream>
using namespace std;
. \# m8 ^/ I2 L' zint b[3][3];//M*N矩阵
+ y# G* Q) ^# l* I$ d( ^int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
int sum=0;
3 ^# _# Q/ h& }. y$ Pint max_num()
* O) v" j3 V) t9 T: S# \{
5 P, m$ p9 i4 n6 F: P2 {( C    int max=-32767;
    int x,y;
5 a6 U! e) K" o( Y$ [    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
  K9 U" v! W# |) t    {
* P. o4 U2 d3 e) n! O5 |% w        if(max<b[j])
0 i0 x2 t6 x" B: V        {
" `) E, ~# n$ ^- X- Q2 A            max=b[j];
            x=i;
            y=j;
) r, X- X2 H8 A; P. u1 @2 r
        }
3 H& e8 K2 @3 [8 e& ]: X    }
2 ]2 C8 ~7 V- C3 f) r9 M1 P. N   
" h2 E; p4 }8 V0 Q0 X4 A" O8 \( i    if(a[y]>0)
    {
9 `5 j0 s6 L# H- H+ [% g8 c        c[x]=y;
9 K+ b* X9 J8 S7 O        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
& p, F/ q5 B8 E8 c2 k4 O0 }        for(int k=0;k<3;k++)
* l3 l& w$ X4 u2 x        {
. t  X, r1 D' G9 Z& N            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
    }
7 q  U  v9 z% B  ], N    else
    {
        b[x][y]=0;
5 m* l1 Q' }1 B! R' j, w    }
( K1 t: r; K  O- P; c   
    return sum;
}
8 E4 Y, g7 N2 N. B+ }9 y1 j1 Kint main()
{
   
    cout<<"input 3 zone's limit:"<<endl;
4 _: H! m9 P  U! a  h  p0 x  j  j    for(int i=0;i<3;i++)
    {
8 X' v  k2 K" d; L. b0 d* D3 I        cin>>a;
    }
" X* r9 V' _% }, l$ i    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
- w6 }* q$ `5 ^/ M1 h    for(int j=0;j<3;j++)
    {
& N0 v5 ?& Y: W2 y5 H* w& E        cin>>b[j];
# n' Q. N4 i* M9 L* I# |  S    }
    for(int k=0;k<9;k++)
! H1 W5 H* J- A& M3 g    {
3 y, Z9 c3 s% a5 Q6 O5 j        max_num();
    }
, |/ q/ u9 c- O   
    cout<<"sum="<<sum<<endl;
; S( `& [8 r3 D1 |( x) }    cout<<endl;
0 L' f1 b: P+ {/ a. l    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
/ p2 u8 `! s/ H5 C. R, g    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
  H' D# J' k* q    }
: P, s1 ~% O! y: I. z( L    return 0;
}#include<iostream>
using namespace std;
, ?, {5 m$ L) l% _! F% Pint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
int sum=0;
int max_num()
{
4 i  a% N/ u2 E: {5 f8 c) d    int max=-32767;
    int x,y;
; q4 |/ [/ Q5 S& T    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
0 y* H3 G# `- _* X5 Z! S  d    {
        if(max<b[j])
5 h0 v( t+ _1 b6 M) z( ~        {
            max=b[j];
& _& g+ H+ Q' z4 J! U# J6 Q            x=i;
            y=j;

        }
    }
7 ?: c5 B: w) S% f7 s% T. ~5 `# A   
    if(a[y]>0)
+ V" }7 }7 A! d4 k9 G( v. S. E    {
) u7 o/ H; `' A6 ~' b. [        c[x]=y;
8 v6 t* I3 t* G' \/ o) J        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
$ J$ e4 G! K) c/ t        for(int k=0;k<3;k++)
        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
1 Q/ o6 N" w; |, `        }
, t" u& k6 z9 }, d4 F" p5 P0 C" l    }
    else
) T1 T% G) f# j6 x7 o. M; _2 k    {
        b[x][y]=0;
, L' C0 m# _' c* p    }
8 _/ U' j) E1 u4 d+ a   
    return sum;
& Y( v- o2 S9 D1 G}
int main()
{
   
  Q7 k+ n+ q! D% r- A    cout<<"input 3 zone's limit:"<<endl;
/ h- ~3 D8 `  y  n    for(int i=0;i<3;i++)
) a' H& }. v: F+ B, C    {
0 {3 H# o2 L# a* G7 Y        cin>>a;
- w  h( e4 f; f# z2 d, q9 K    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
  |6 R2 E: q8 A# [, M# C    for(int j=0;j<3;j++)
    {
- P; ]  E! o% s4 i. v        cin>>b[j];
    }
( T* ]- j1 ]6 i, }    for(int k=0;k<9;k++)
# @  r) D5 w- E% n0 b( z    {
        max_num();
: J/ q/ Z) k. a    }
& l, K+ n3 @9 k  J7 {) z- f   
    cout<<"sum="<<sum<<endl;
    cout<<endl;
. B' [) g2 S+ O0 u' z    cout<<"reslut:"<<endl;
; z+ k$ @) d' I" i1 ]" B0 [: i    for(i=0;i<3;i++)
% e2 {& Y6 V2 y: Q    {
. p8 T  B8 F# ]& H7 w7 X        cout<<"people "<<i<<" go to zone "<<c<<endl;
, n' M5 R$ l" [9 L! r$ V; C7 x    }
    return 0;
* R$ C3 x7 D+ G, Q, I7 q}

厚积薄发

编程代码二：
$ m$ C* L  O$ f! X#include<iostream>
#include<cstring>
' O1 \+ ^7 i7 A+ I8 u2 d#include<ctime>
) f4 {: h- d; k7 c) m8 f, b9 H7 Iusing namespace std;
1 ~- R, f6 b9 f+ D) f3 u0 l- Cclass ifo{//矩阵的元素
    int clerk;//员工号
; C. e' z& p0 u5 P    int area;//区域号
    int per;//爱好度
; F) k+ l  d' h8 V( i' lpublic:
  ]% ?  J3 S& }    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
5 j8 p+ [, `3 |# y3 J5 L- U    int getclerk(){return clerk;}
3 ^+ g5 J4 f# `) M! M9 w    int getarea(){return area;}
    int getper(){return per;}
& S% {1 w+ {2 ?$ Z/ Q    void setclerk(int i){clerk=i;}
    void setper(int p){per=p;}
0 {! c" E$ ^) X6 A7 F2 D7 k+ |    void setarea(int a){area=a;}
};
class area;
# ~+ }  P9 y1 Y# {- Z- oclass clerk{
    int areanum;
    bool isin;
    int inarea;
# g2 d4 R  F& \+ R5 _) ipublic:
    void set(int num){isin=true;inarea=num;};
/ t- ^& Q: x) p1 k( [$ T. I    void setisin(bool b=true){isin=b;}
    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
};
* B9 K2 m8 @' x6 jclass area{
    int num;
    int max_num;
public:
8 t5 |: l+ E4 v4 m    friend void set(int);
    int getnum(){return num;}
. A: B2 B# A" V  w4 B6 b    void setnum(int number){num=number;}
0 p0 n0 M- K, `    int getmax_num(){return max_num;}
    area(int number=0){num=number;}
$ E; C, l/ ?5 m/ A) Z' ~* y! n    int getclerk(){return num;}
    void addclerk(int ps){num++;set(ps);}
) A4 r7 F' \" m# x};
void getorderbyper(ifo array[]);
- Z( |7 X3 f2 Q: [5 Y$ Qint areanums;
. u" H+ t3 G/ a+ g6 T0 e/ I" Q" Kvoid main(){
2 ?- H% H% D/ b! r$ c4 H5 [    //input
# a  B# Z4 V, p2 k; X$ J    cout<<"输入区域数：\n";
  q, C; k* N  m" c% M    int area_num;
3 {4 d' E; \( g1 _; T) Q) p    cin>>area_num;
7 j3 X4 P4 A! ?8 Q5 h+ ]    areanums=area_num;
- P4 r2 S$ u! m+ B    cout<<"输入员工数：\n";
# y. n4 L- g5 j4 P+ u' x    int c_num;
0 ~; b. P' ]% q' m    cin>>c_num;
$ j, ?8 Q. n7 J3 E4 J# r$ ^% c    cout<<"依次输入每个区域能容纳的员工数:\n";
" X* x; ]1 Q  F4 h$ ^    int *max=new int[area_num];
    int nownum=c_num;
8 ^2 J, v% D9 v" Z" E' z    while(nownum){
/ e& ?' G& z8 i; E1 M( [        for(int i=0;i<area_num;i++)
        {cin>>max[i];nownum-=max[i];}
        if(nownum>0){
            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
2 T& o" _2 ?4 ], e            nownum=c_num;
        }
        else nownum=0;
0 J% A( w3 U1 f+ p- S    }
    cout<<"按行输入每个员工的偏好：\n";
- E5 ^8 a. y  P( ?. v    ifo** per=new ifo*[c_num];
8 L9 _: Z5 v+ ^  m8 c& z  i    for(int j=0;j<c_num;j++)
        per[j]=new ifo[area_num];
2 Y# b4 i9 g* `# q* l    srand(time(0));
    for(int c=0;c<c_num;c++){
& h1 ?9 J* x) H/ ~1 Z        for(int a=0;a<area_num;a++)/*
6 O4 H7 `8 l) h# q# @, A        {    int p;cin>>p;per[c][a].setper(p);
            per[a][c].setarea(a);
1 L; t2 R: N  Y            per[a][c].setclerk(c);
( C2 k4 h/ W3 H1 Q0 `% f0 I$ E4 B        }
        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
        {    per[c][a].setper((rand()%60)+40);
            cout<<per[c][a].getper()<<'\t';
        }//测试时懒得输入，故以60-100的随机数代替。
-    cout<<endl;
    }
    //output
8 P; G0 Q3 S# f. g3 ]8 z        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
, }! \( ?6 u5 u) E        clerk* people=new clerk[c_num];
        area*  areas=new area[area_num];
        int totalper=0;
        for(i=0;i<c_num;i++){
8 i) c4 U4 M7 g$ b8 B            for(j=0;j<area_num;j++){
* C; h% b% N- y) i            if(areas[per[i][j].getarea()].getnum()<areas[per[i][j].getarea()].getmax_num())
0 q8 n6 z# [1 g4 A                people[i].set(per[i][j].getarea());
                people[i].setisin();
                int number=areas[per[i][j].getarea()].getnum();
' d  p+ u( r) s$ r                areas[per[i][j].getarea()].setnum(number);
                totalper+=per[i][j].getper();
" V) D9 _1 P  x/ j  E                break;
5 B3 p. x2 i  t! O            }
( E' Q3 I% X. c9 X        }
! Y0 T  B% H4 k9 H; M8 A! O        cout<<"能达到的最大喜好度为："<<totalper<<endl;
% u, j* ~- a9 r; Z1 U}
void getorderbyper(ifo array[]){
    int max=0;
; o, C8 t) ^$ |' ?( ?. f    for(int i=1;i<areanums;i++){
9 V; h# F$ I& X        for(int j=0;j<areanums-i;j++){
$ e" K5 t& g7 B  v. `) \        if(array[i].getper()>array[max].getper()){
            max=i;}
5 V- l$ a' d& g0 t        }
        ifo temp=array[max];
        array[max]=array[areanums-i];
1 w/ D, O0 H" l7 h        array[areanums-i]=temp;
        max=0;
    }
+ P3 }" g" _' p' c! W}

厚积薄发

代码3：
/*
; s; K) Q* e% ~% O/ Q" k算法思路：
- P* b1 r3 p2 |% _" w" q（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
- v. l# U0 _1 P5 o% ?7 s% c7 ?再加，该人的所有喜好度设为0，
, u# E) f# U2 v$ g) U, E% p3 ~（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
! l! o8 f: s+ Y9 }  q（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
7 n; i3 J& a8 a& s& t# o+ q(4)最后输出总喜好度。
' o- U" C# N# @1 r# [& c3 W$ y9 {*/
#include<iostream>
using namespace std;
, U7 `8 ?4 w. d+ c9 |* o6 V6 Hint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
4 H& X" j* ?- c+ g9 `7 {! Qint c[3];
int temp[3];
int sum=0;
; q& h( X1 O0 J$ Z: F- o7 iint max_num()
  w8 |* ^  h% B; U3 F{
    int max=-32767;
    int x,y;
" u5 |- z1 ^7 Q9 d- Y    for(int i=0;i<3;i++)
* R/ d2 l: {. r) Z- A$ A! _    for(int j=0;j<3;j++)
2 Y1 ^1 Y4 O+ h4 j8 I$ Q    {
        if(max<b[i][j]&&b[i][j]>0)
) P! N) `4 m) M' i$ v        {
            max=b[i][j];
/ W' \6 U- u: @            x=i;
            y=j;

        }
" A! N7 F4 y0 ~' t- ~* n3 l    }
   
( J. S+ v8 N7 z    if(a[y]>0)
    {
3 h, u% v$ H2 X  O        c[x]=y;
        //cout<<"c["<<x<<"]="<<c[x]<<endl;
        sum+=max;//总喜好度加上添加
        temp[x]=max;
4 x; H: D; C) E$ S- u        a[y]--;//区域上限人数-1
    }
$ c) V' s! _& E8 S    for(int k=0;k<3;k++)
    {
        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
    }
" C# x' `9 a! y5 f' S/ D3 m6 m, _    return sum;
# z3 X( w6 ?8 {6 R' x7 E+ v# S1 ]# M}
: k1 O8 u, ]8 W0 u. P, w  `int main()
{
  O! w+ g/ ^7 ~3 d4 F: P) S   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
8 W* R& Q" I  ?7 u9 j7 T    {
        cin>>a[i];
5 S  y7 h( {. A2 L    }
1 D) n9 k9 y* L5 F6 t    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
8 T* d2 U( f5 |2 c        cin>>b[i][j];
    }
7 {0 u& e, g  }' X0 b5 \    for(int k=0;k<3;k++)
    {
        max_num();
    }
0 F: A6 x7 s# \" D9 P# g    //cout<<"sum="<<sum<<endl;
    cout<<"sum=";
    for(i=0;i<3;i++)
7 Y7 I( n) ?0 ]4 v    {
4 I: o5 v  E- X8 t, ]2 s* p, P        cout<<temp[i]<<"+";
: r" \* H0 e6 {/ S$ h    }
    cout<<endl;
    cout<<"reslut:"<<endl;
4 E( K! ?) Q1 M, ~% I8 i    for(i=0;i<3;i++)
    {
2 ?/ s# M/ ?$ t        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
! R9 O8 f2 {% N! K    }
  _2 u0 [& T/ K) O0 n5 j  O    return 0;
}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
数学中国社区分享快乐！
" y5 d; ]; R0 w! u

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.
! q$ y6 N0 W8 ]4 F5 l" N

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！