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

厚积薄发

座位调整

题目描述：

百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。
- K! l' N: {" A- i! G, c
调整的方法如下：

: s& c' T" b& K! W2 N- T1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。

* V4 K- M( o% B8 @7 M' Q4 X) c+ O2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。

+ |+ g- T/ i4 G; E1 ^& o8 j3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。
5 o' ?2 |3 r3 P( [( v) @8 s: a
9 g, w& T& I1 S4 t: D$ t; O数据输入：

第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。

第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。
4 `1 l& [9 n5 y& m2 l
$ O7 C- z( b+ h( |* s9 a( U7 C紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。

答案输出：
! s% S3 O, T1 j$ o) x
$ H; ~; O$ l; j( k5 e对于每个测试数据，输出可以达到的最大的喜好程度。

输入样例

* c! q4 q# Y$ ^: d: G3 3
9 a0 C; _; s7 A4 U6 Q
1 1 1

2 b2 R- Y, X3 G100 50 25
  ]1 o  n2 Q% x, ^) ]2 F
! c8 W9 @% ^  ]6 I" R! e100 50 25
1 W1 K& ]& \/ C7 Z8 _
9 T- j* r6 ~. Q( F100 50 25

. Z6 M  }# l+ U8 ^" q
输出样例

175
  e' I3 T$ R9 f
, n. d. I6 J% [5 O+ e/ y/ b

0 g0 m6 h2 i7 h4 {' _+ Z. r) u
数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175

hbdkfk2

看不懂！！

久玖九王

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

schnee

必须顶！！！

ehi28

嗯,不错,支持一下.
/ W9 f* J5 S3 q) {1 ~2 A3 B" b, b

_Amy_

程序最头疼

葉_浅浅

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

厚积薄发

代码3：
/*
* ~, e/ d3 g  C, T8 l1 N算法思路：
7 F; M- A  A: f# X4 u$ p（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
再加，该人的所有喜好度设为0，
（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
8 p; O6 D, B7 E7 _5 n（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
(4)最后输出总喜好度。
" z6 D( x* [4 [$ o) o*/
#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
+ k8 ?: a1 ~+ F( l9 |9 D$ F0 J+ eint c[3];
, f% ?5 Z6 T0 I* g# U/ Aint temp[3];
int sum=0;
7 o7 X  ]) h7 ]& _9 v5 dint max_num()
3 X4 N6 J& |5 p$ w{
    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
" |7 l- ~6 R9 A" V  y- I9 J    for(int j=0;j<3;j++)
* h7 H  _. Z. j' q    {
3 m6 B, \/ I/ O' C. V! f        if(max<b[i][j]&&b[i][j]>0)
" f" D" b2 k0 d: f5 h; W- r        {
% ?/ Y9 B& c/ Q& O. W            max=b[i][j];
            x=i;
            y=j;
4 B" s: G0 m. G
        }
    }
   
    if(a[y]>0)
' P) \. f( q1 J5 h    {
8 M) Y+ |- v( q        c[x]=y;
3 k- s7 \. J' b& a' L6 b        //cout<<"c["<<x<<"]="<<c[x]<<endl;
. ^% A4 ^5 G6 `& ^        sum+=max;//总喜好度加上添加
        temp[x]=max;
        a[y]--;//区域上限人数-1
$ ~: X: o1 A9 m    }
3 J9 N* ~+ t+ T0 G! @6 y    for(int k=0;k<3;k++)
! W) F* n. d2 p" K) d5 D    {
        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
7 j: k3 R% Z, j$ p& S    }
( ]& Z1 o6 H: C3 H$ Q$ \. q  Q    return sum;
}
$ t4 `1 e" k2 h. t& F3 h4 pint main()
{
9 w, |& U! [7 j$ ^1 x   
* N- F( r/ m' _6 v* Z# C. l7 N5 [    cout<<"input 3 zone's limit:"<<endl;
) o" {; l: S  J7 T0 F5 F    for(int i=0;i<3;i++)
2 v% M  C7 }+ w4 O, D# e+ V% Y    {
4 U& T+ V1 V$ T+ @        cin>>a[i];
    }
, v* }% M- h8 r* {7 w9 g% @* \5 o- u    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
3 R, z) c; J0 i2 e. b    for(int j=0;j<3;j++)
    {
' b& D" X7 J2 N+ Q1 u        cin>>b[i][j];
' o' e. }3 k7 \9 ^1 j0 j9 R9 [    }
6 Z' u  J" d7 r    for(int k=0;k<3;k++)
. P7 S* G7 }, T" p  \    {
1 C1 q- t* m) t& U' D! Y$ p7 W        max_num();
    }
! z7 U- [, v1 y    //cout<<"sum="<<sum<<endl;
' d7 m+ i( P6 j. |! p$ E    cout<<"sum=";
$ Y9 J$ j) o3 a. S2 B    for(i=0;i<3;i++)
    {
        cout<<temp[i]<<"+";
. V5 O/ r' J. o9 p  W    }
    cout<<endl;
$ k# I' ^) i/ l& W    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
3 C3 m4 P( v" k9 G/ R! H" t& H    {
* X6 O( D  T5 \3 F( O* W& f        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
* l" i; r& l! t, i4 \2 \# J# _    }
    return 0;
}

厚积薄发

编程代码二：
6 |( n* h9 n7 ~) Y. N# x0 O#include<iostream>
3 C( m2 w- p" E# Q3 U#include<cstring>
  O& ~$ e3 K% A#include<ctime>
- D. g" s( e$ N8 R8 ?& J  Z6 r/ Dusing namespace std;
1 \7 B' j& L* ~# F3 ]6 yclass ifo{//矩阵的元素
! b: f) A0 q! R# U6 L    int clerk;//员工号
: Y; f& O3 G# g. t) P* g    int area;//区域号
" X( F0 T8 ^  L  ?8 @    int per;//爱好度
% O9 V! _* x: ], D5 g7 i# h4 @public:
; f) M. c5 C9 Y) k8 @" U" ]4 z5 a    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
    int getclerk(){return clerk;}
    int getarea(){return area;}
    int getper(){return per;}
5 V6 `5 W. g0 j: d8 Q    void setclerk(int i){clerk=i;}
    void setper(int p){per=p;}
  G% F: Z* ?! n# _    void setarea(int a){area=a;}
};
class area;
! i9 q5 s# y' Z) O& nclass clerk{
" H5 [. C$ f' ~    int areanum;
$ H1 @/ `2 C) g( {% g, P    bool isin;
, I% U" E# r$ c: Z    int inarea;
public:
5 |! b0 p- y9 m* `: Q    void set(int num){isin=true;inarea=num;};
    void setisin(bool b=true){isin=b;}
. E# n% i( S9 Q4 ]5 S/ Z2 t* N! Y    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
};
class area{
+ q3 Z- J) G! k. o    int num;
$ W6 r. [3 X+ S! p' p) U: }    int max_num;
, g0 P- ]! j  k9 f, U) apublic:
" u7 c4 C! ?7 ]. |7 }5 R$ J/ d    friend void set(int);
    int getnum(){return num;}
    void setnum(int number){num=number;}
5 T2 s1 e9 r& M4 J5 S6 w    int getmax_num(){return max_num;}
    area(int number=0){num=number;}
7 z* v. b5 G% S: B: [    int getclerk(){return num;}
- u* W# B% G! i* ?1 Y    void addclerk(int ps){num++;set(ps);}
. Q6 H) y4 X/ \3 D, S};
5 u- E; I4 d  L; j, Z! \void getorderbyper(ifo array[]);
int areanums;
void main(){
    //input
    cout<<"输入区域数：\n";
2 _  d0 y4 S6 ?* X- W: i    int area_num;
    cin>>area_num;
5 b% I- e7 T/ g0 _7 s! b    areanums=area_num;
    cout<<"输入员工数：\n";
    int c_num;
    cin>>c_num;
    cout<<"依次输入每个区域能容纳的员工数:\n";
' X/ n4 `3 K+ j    int *max=new int[area_num];
    int nownum=c_num;
" w/ C2 Q, `& q* E$ T4 O) l    while(nownum){
        for(int i=0;i<area_num;i++)
3 P  F; z) X* z& M" t        {cin>>max[i];nownum-=max[i];}
        if(nownum>0){
            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
            nownum=c_num;
5 c- F# N3 v' v% j2 q; E& }9 O" x        }
9 P" L2 K1 W4 t* [$ i9 B( b) O        else nownum=0;
    }
- {  X: [. a) @6 S1 T! |5 u    cout<<"按行输入每个员工的偏好：\n";
    ifo** per=new ifo*[c_num];
/ M3 z7 ?3 T" s" @    for(int j=0;j<c_num;j++)
3 M) _3 P) G: l* w$ F+ [2 p; v' L        per[j]=new ifo[area_num];
    srand(time(0));
    for(int c=0;c<c_num;c++){
5 Z% B5 u$ ]* f2 V        for(int a=0;a<area_num;a++)/*
        {    int p;cin>>p;per[c][a].setper(p);
            per[a][c].setarea(a);
6 c1 H' @% y0 M/ V4 Q# O' p2 I* n            per[a][c].setclerk(c);
; |4 x: }" d9 w! a9 ?        }
        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
        {    per[c][a].setper((rand()%60)+40);
            cout<<per[c][a].getper()<<'\t';
  p! `0 J# W3 n7 [7 n1 P4 d        }//测试时懒得输入，故以60-100的随机数代替。
" f1 F6 e% w3 Q4 @: U2 Y8 t-    cout<<endl;
7 k9 s3 S. c; F$ J* P& L% n    }
    //output
        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
3 t1 h: [! m& K/ G% W9 ?. ?( [        clerk* people=new clerk[c_num];
" d* v: d, b) ?        area*  areas=new area[area_num];
        int totalper=0;
        for(i=0;i<c_num;i++){
            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());
) M2 w5 j) y9 L3 [5 U                people[i].setisin();
                int number=areas[per[i][j].getarea()].getnum();
                areas[per[i][j].getarea()].setnum(number);
                totalper+=per[i][j].getper();
5 ~4 D5 }+ z1 \8 p- ~9 z) v2 O                break;
            }
* w9 k/ T' \3 Y        }
/ W5 I( y. P7 u" a( d6 i- U8 A        cout<<"能达到的最大喜好度为："<<totalper<<endl;
}
void getorderbyper(ifo array[]){
4 _, X  X3 B$ |. K5 O/ c$ J8 r    int max=0;
8 W' i2 v; Q4 H/ ?* {7 b    for(int i=1;i<areanums;i++){
        for(int j=0;j<areanums-i;j++){
# I% \+ d" _7 r* Y) c2 V$ `        if(array[i].getper()>array[max].getper()){
. [0 I) Y0 M- R6 U9 p: P& E- ^* J            max=i;}
+ l( }7 W( C' L0 b8 |        }
        ifo temp=array[max];
        array[max]=array[areanums-i];
2 c/ }  G6 ]# x8 }8 d' U$ u4 ]7 t$ |1 l        array[areanums-i]=temp;
        max=0;
! i- I9 Z- ?* G2 H! O    }
% ?% D& m& `) }- Z. w' h}

厚积薄发

#include<iostream>
using namespace std;
3 I/ U& Q( Q' ^4 y( Pint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
# _  t, _: w/ V! v0 y: iint sum=0;
int max_num()
+ W  r+ |" c' q1 O- V0 H. [{
    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
' f7 ~6 M6 |9 ~# z+ }/ v        if(max<b[j])
' g6 v4 Q  K8 c        {
- U1 T+ }; W$ H/ U; @5 S+ [# S0 _            max=b[j];
            x=i;
            y=j;

* [0 T9 K2 F; U9 H        }
    }
   
$ i9 V" i8 r1 m' }    if(a[y]>0)
6 l' `2 G1 G% T2 e% e! D! t3 b9 J9 M    {
. [6 ^' Z% S: B# l        c[x]=y;
& F. G8 ^6 r  t' w7 W& x        sum+=max;//总喜好度加上添加
( w% e  n, a# P, l        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
1 n6 L- B: V% H& O        {
6 p0 r4 N" V( W            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
    }
    else
    {
# K7 c. v+ `& d+ i9 C, p        b[x][y]=0;
8 s5 |; r! o- o5 s8 m    }
   
    return sum;
& i9 t" |" b+ K) _: I$ N}
* ^9 \& O' h* V6 {2 T' ~* V, cint main()
{
   
' \; e% p* o) {    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
" j4 g; l) i' l  n' e( m( P    {
+ U+ a$ l/ o  S/ ^5 ^% i6 ?* G" T        cin>>a;
; j6 j) _' y- X7 v    }
    cout<<"input 3*3 actangle:"<<endl;
) o" A3 l- @2 n6 E: s) v    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
& V, t  W2 e) V; y# u2 l- E) M+ {& W0 S        cin>>b[j];
: E& y* b& G# T    }
" E% G& i) R1 y    for(int k=0;k<9;k++)
" n. M% k, t7 K: c# c    {
        max_num();
    }
" k3 ]; u0 x' V9 b& q5 P   
5 z9 ~+ Y; I/ S* h2 \' t; x1 I! l0 h  K    cout<<"sum="<<sum<<endl;
8 s( l; \3 d) i7 {! i# K% X    cout<<endl;
  y6 V% c8 {& s6 E3 ^# b. o+ h    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
$ b4 W. y0 X- p  K    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
( \- F1 V) {  k) K: M$ T    }
    return 0;
& \' R5 T* r' Z' ~& C}#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
' h( l2 f, z: A# Tint a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
3 W# ?" {5 V" Kint sum=0;
int max_num()
4 X# N  \; H. X- R& [* \# w{
    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
  z7 A8 n8 j1 s3 j) u    for(int j=0;j<3;j++)
    {
        if(max<b[j])
5 o: i) u/ C) r' u( I1 V        {
2 y  h  D8 r9 _: P8 ~* {" |8 U! R            max=b[j];
            x=i;
2 J/ [' ?5 x$ V0 B5 I/ b0 ]            y=j;
/ s, W: ~! Z/ @6 O2 ^
5 ?, l- f) ]' t/ d0 z. X8 s: b        }
! K2 r! Z: D9 n4 ?3 T+ m' _5 R8 Z* n8 o    }
   
    if(a[y]>0)
, I4 [4 W1 W1 n( O# F4 H    {
        c[x]=y;
        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
    }
    else
1 X1 N2 g( J0 O    {
; N8 C5 N/ m. H) w        b[x][y]=0;
    }
   
    return sum;
}
int main()
{
/ H! u& M0 @7 M, _$ C- l- N8 D) Y   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
- b4 `/ }+ P3 _# d0 K    {
        cin>>a;
: B7 V; c: J% g2 `" g' L    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
$ O3 }% x! F$ y; P! A7 e    {
        cin>>b[j];
# S" i" P# g+ Q9 N    }
    for(int k=0;k<9;k++)
    {
% n* j( D" p( h6 ]- R/ T) f  A4 v        max_num();
    }
) }. w: n& d6 E1 Z   
* y) M6 \, u1 e; c* d4 ?9 n    cout<<"sum="<<sum<<endl;
    cout<<endl;
& c/ o' p  u) ~9 K' l( D7 C    cout<<"reslut:"<<endl;
$ l% S1 q. J5 R/ q$ [    for(i=0;i<3;i++)
    {
# t7 ^; w4 V) Y2 Y" q- w, I        cout<<"people "<<i<<" go to zone "<<c<<endl;
8 P, J- O0 A: d8 e1 U: R    }
' L6 W+ P* k: J- _+ S    return 0;
}