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

厚积薄发

座位调整
9 k( X& D1 a3 N5 O4 z
  T* ^/ y( ~5 {+ w0 e4 }% H题目描述：
2 x" z$ g- X" Y; q
百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。

调整的方法如下：

( k% t/ i; L7 q" N1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。
2 \+ e9 L% w) ^
2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。
4 @' _# _9 W' _$ n# r
# c6 Q5 s$ `" ?* V3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。
7 Y+ G/ C* e+ P2 T& h& _2 o
# }& f% _# P' [, _数据输入：

. h, v0 G3 K; u9 f. S0 v6 Q3 r0 ?& _  K第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。
; f- x, a' p9 D' l* V2 W
) ?$ g( P7 w8 r/ ?$ p第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。
- \3 {: A5 W2 x  t) u1 p+ A" t
& j/ s# ~$ h3 N+ V) M. p紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。

) g) C7 X% U' S. N; P7 z% h) K答案输出：
  q# x  `( v; }+ `% r9 P/ X/ C
4 B7 H" {3 G2 |- K5 g9 z对于每个测试数据，输出可以达到的最大的喜好程度。

" f1 x1 p9 L( k' p2 I/ O& H输入样例

% F0 A9 I" `* D, }$ `6 }* ]
3 3
0 F0 f5 p. Y6 E
8 B2 a$ a9 B1 E' E) k( [: p. F1 1 1

+ Q" K( W: z4 r" J100 50 25
3 U+ O5 P) `& }9 Z
100 50 25

100 50 25
" g9 `+ b& O% ~: `  A' o; A6 N

输出样例

  Z6 F4 C% l* ?4 ?7 s
4 p" Z' k& j& [1 z& S" @175

3 I! h/ m) k7 ~7 |* Z; ~/ J

# B4 n; [1 V+ z& [" y
数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175

厚积薄发

- T" R% f8 g# ?* v! M
#include<iostream>
7 V4 M9 U$ i% Z% U: W6 `4 Ausing namespace std;
$ H9 R8 P7 t$ ]int b[3][3];//M*N矩阵
3 z" r; I; [! u6 wint a[3]; //区域人数上限数组
5 g) a" @- k8 ^int c[3];//记录某人i去的区域j
int sum=0;
int max_num()
- b' w% q/ M! G0 D{
    int max=-32767;
6 q4 z6 y, _" i% l& i    int x,y;
    for(int i=0;i<3;i++)
: ~: o5 J- x' e+ I0 c  q4 T4 ]$ j    for(int j=0;j<3;j++)
    {
        if(max<b[j])
        {
            max=b[j];
/ N: W5 x9 `  i9 }/ G4 w            x=i;
0 E: ]- E  D" f% h9 V$ e            y=j;
; K: i9 \% y3 \
4 e# k9 `9 h, L* a- ^        }
    }
   
    if(a[y]>0)
    {
  ?$ j* C1 s8 C/ I        c[x]=y;
" s2 Q- c7 r: p- x        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
2 }6 W' x. Y! J4 {. _; z' V" t        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
3 w- a3 o6 ~1 X* n: g$ x        }
    }
    else
( c  k; V* w$ M7 D    {
2 J8 D+ [( [. i4 M  \        b[x][y]=0;
1 H9 _& P% X4 @" ?$ a    }
2 P1 W# o/ v! f; P6 _1 D7 q# {# E1 I4 A   
" g- n. v$ W' v3 R2 N  |    return sum;
}
1 q9 P4 g5 O, n5 w. v2 O9 _, z: e- jint main()
7 \' e% o8 `$ H* p7 ~6 k{
, n9 K+ F4 d* G. k   
3 c$ ~5 t5 R, v# i3 `3 _& X    cout<<"input 3 zone's limit:"<<endl;
2 W- Q6 J& s/ r# Y! X    for(int i=0;i<3;i++)
! u7 b+ F. {; S: }    {
1 T0 o) n7 E+ b: O7 e! V        cin>>a;
    }
2 Y8 t3 X, n: I, r5 L    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
) j1 ^+ V- j+ ^) U  Y    {
        cin>>b[j];
' q. T$ A  R  n    }
    for(int k=0;k<9;k++)
    {
        max_num();
8 P, @2 J' m8 N! U: s# F% a    }
   
0 m3 h+ f& b1 o1 ^9 P    cout<<"sum="<<sum<<endl;
9 i: K7 ^% Y7 ?7 d9 K% S    cout<<endl;
4 H8 x3 K! u' R0 y9 x. @    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
0 u/ Q& _$ J- a% [/ n( r9 H( Z% Z    {
; m% e0 O" `* F+ t( _6 [        cout<<"people "<<i<<" go to zone "<<c<<endl;
% P$ ?& p% O- V: F- k8 ?    }
9 S: g+ }6 d' U. `    return 0;
( P: M) H. T9 i2 }5 w3 m( I* j}#include<iostream>
using namespace std;
* u; Z: t* r8 Hint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
. d* ^1 w. u4 z& k" `7 Zint c[3];//记录某人i去的区域j
- G4 r1 n9 `/ S6 e9 N& e! |( `int sum=0;
int max_num()
8 Q6 i8 O$ x  d& {/ C3 D4 _" b0 U7 O{
  F9 ?) d8 i! [. {' o' r    int max=-32767;
    int x,y;
% [; [9 J0 z4 I3 p. \    for(int i=0;i<3;i++)
1 O3 q7 R+ P6 Z3 b$ V( Q    for(int j=0;j<3;j++)
& T  N: l/ X# P) l    {
        if(max<b[j])
# [. l6 U0 ^# V+ b1 I" O        {
            max=b[j];
% E' t1 D/ ^( K7 \6 Y8 j4 E            x=i;
            y=j;

        }
    }
1 X2 s, n9 B! I9 {   
0 Y0 {: \9 g* w2 W6 a& b# ^$ F3 y- A    if(a[y]>0)
    {
" A$ Z4 M$ u! N7 u+ x* Y4 `        c[x]=y;
4 O% w5 }% V$ f; ~7 @        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
, t# P% D+ V9 U        for(int k=0;k<3;k++)
        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
6 A( L" N) @# V! e. ?        }
    }
    else
    {
# e; Y) i8 K- f6 L' n        b[x][y]=0;
2 ~/ Q" j1 p1 M0 j4 p3 j0 W    }
   
    return sum;
}
" n- B" Q& S4 D% ^6 e, }* pint main()
{
( H9 M. S8 ^2 E+ q   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
& l3 T+ H' ~* n) f  W    {
        cin>>a;
    }
    cout<<"input 3*3 actangle:"<<endl;
1 v7 B! U, }  f! }8 x    for(i=0;i<3;i++)
: J- T) E& t: O& L& d& U    for(int j=0;j<3;j++)
0 e7 e+ I' m1 V; a# _/ p0 P2 `7 l    {
' ]0 H5 w$ I- T- k        cin>>b[j];
, h3 A* e# c% V+ z; z$ U    }
    for(int k=0;k<9;k++)
8 r& B- j# Z7 w, r  A5 Y' \    {
        max_num();
  S$ b) |) @& h4 I    }
   
    cout<<"sum="<<sum<<endl;
( o4 _6 c- `7 F4 l* C8 q# c    cout<<endl;
  h7 F: _* T$ [' Q  O    cout<<"reslut:"<<endl;
4 X( S% b9 V/ x5 {( W, ~2 B  ]    for(i=0;i<3;i++)
! T* e( L2 D# {4 I2 ?0 e/ F* W    {
- e' w2 q2 I+ j1 [: Q2 [4 K6 N8 f        cout<<"people "<<i<<" go to zone "<<c<<endl;
5 M) B" m1 p' O0 @2 G# T& t- V    }
: ~; `  `% G& W    return 0;
}

厚积薄发

编程代码二：
  ?4 ^* t" m7 a( B( M; @% \#include<iostream>
$ Q2 x7 v% \7 W  S7 n#include<cstring>
: M+ t- w& Y! R, J* t: g#include<ctime>
& |9 X1 l7 R- G% Lusing namespace std;
3 g  F1 ^( g3 q3 ^2 z0 yclass ifo{//矩阵的元素
    int clerk;//员工号
    int area;//区域号
    int per;//爱好度
2 o' \2 R5 F: X! [% }public:
    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
    int getclerk(){return clerk;}
5 u2 m7 B6 N  d4 \* O! C# t  Y9 n+ Y3 ^    int getarea(){return area;}
" o( }. N7 E& W" V& B7 Y* v+ {! ~: l% v* D    int getper(){return per;}
! x! l, {+ {$ U2 S' E0 p' l    void setclerk(int i){clerk=i;}
    void setper(int p){per=p;}
    void setarea(int a){area=a;}
};
2 e- `% S: d" p" K9 G5 Oclass area;
4 M) C0 h9 Q9 }  ~+ oclass clerk{
- T& V' f4 Q3 x7 j: t+ w    int areanum;
# ~6 a/ D5 }. s, h' z& _9 ?* D    bool isin;
    int inarea;
public:
$ a7 E! [3 T! ^7 C* Y+ G0 W$ r  e    void set(int num){isin=true;inarea=num;};
    void setisin(bool b=true){isin=b;}
  D' i# u, z. o    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
};
class area{
    int num;
( n  M- k- B# w  c# f5 ?    int max_num;
' e. Q( A3 y4 U% g2 Apublic:
  Y7 K+ B; i2 x5 R+ j/ k5 Y) _    friend void set(int);
    int getnum(){return num;}
7 X8 @1 x5 c" B& X, Q    void setnum(int number){num=number;}
    int getmax_num(){return max_num;}
: S- `2 }8 O; B) s2 `# ]( W6 ^    area(int number=0){num=number;}
    int getclerk(){return num;}
    void addclerk(int ps){num++;set(ps);}
};
void getorderbyper(ifo array[]);
int areanums;
void main(){
    //input
    cout<<"输入区域数：\n";
    int area_num;
    cin>>area_num;
& J; u) ?" N2 p8 n2 A' P# ]. ~0 i    areanums=area_num;
    cout<<"输入员工数：\n";
1 {) E" B$ T4 F  x. z" ]/ k) w    int c_num;
    cin>>c_num;
    cout<<"依次输入每个区域能容纳的员工数:\n";
    int *max=new int[area_num];
* A- S: j1 i7 \2 Q, \2 F    int nownum=c_num;
    while(nownum){
        for(int i=0;i<area_num;i++)
        {cin>>max[i];nownum-=max[i];}
* a7 y% Q, ^! s  [        if(nownum>0){
            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
0 K; q& x# H0 g" W            nownum=c_num;
& y, o9 _* {. ~3 f7 k, {7 v        }
        else nownum=0;
6 J/ C/ d8 A- r% `    }
, @) @  D; t7 l  @4 s, o$ p    cout<<"按行输入每个员工的偏好：\n";
    ifo** per=new ifo*[c_num];
. |) E& ]! `% b5 y( _, @2 W    for(int j=0;j<c_num;j++)
        per[j]=new ifo[area_num];
    srand(time(0));
/ ~: C+ |; k; {: J& _+ Q    for(int c=0;c<c_num;c++){
* n; w9 y2 p$ j' q  c        for(int a=0;a<area_num;a++)/*
        {    int p;cin>>p;per[c][a].setper(p);
2 U$ B6 ^8 R# i% F# M* x4 m+ B            per[a][c].setarea(a);
: L$ b% C( `* t8 q# ^" V3 W3 j1 f            per[a][c].setclerk(c);
        }
$ q* ^' e, N/ f        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
        {    per[c][a].setper((rand()%60)+40);
, l: h$ z5 R0 H  I            cout<<per[c][a].getper()<<'\t';
. @7 X/ y8 [4 d, w; `! y( j' {% R        }//测试时懒得输入，故以60-100的随机数代替。
-    cout<<endl;
9 q. ^6 H& ]2 D: X8 e- D5 }    }
; Y" w9 Z4 n1 w( K( k* I% |2 L  Y: U    //output
5 W1 C7 F: B, ~, K        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
        clerk* people=new clerk[c_num];
        area*  areas=new area[area_num];
        int totalper=0;
        for(i=0;i<c_num;i++){
            for(j=0;j<area_num;j++){
  F8 X# d; n# J: R            if(areas[per[i][j].getarea()].getnum()<areas[per[i][j].getarea()].getmax_num())
, R' f2 T& \! v$ W: F                people[i].set(per[i][j].getarea());
                people[i].setisin();
9 W) X4 u; t- E- j& [' f                int number=areas[per[i][j].getarea()].getnum();
: j3 V- |0 j  N+ T8 L2 p                areas[per[i][j].getarea()].setnum(number);
                totalper+=per[i][j].getper();
) i9 C' ^" k8 J3 l                break;
3 d/ i# G* j! y            }
! ]  S' Z# P6 F1 I# w$ l        }
) t5 V8 d7 k' p) D4 g7 [        cout<<"能达到的最大喜好度为："<<totalper<<endl;
+ `1 v- B! L6 }! h% r% V" T}
9 v1 H) x' d7 I! ?void getorderbyper(ifo array[]){
    int max=0;
) W% l4 L9 B2 T3 ^    for(int i=1;i<areanums;i++){
        for(int j=0;j<areanums-i;j++){
  [0 f' S! Q  c1 f' G2 n        if(array[i].getper()>array[max].getper()){
            max=i;}
4 U4 L# l) ~6 C% v0 d        }
2 S# \# H7 R# i6 o# @        ifo temp=array[max];
. Y* S. H& |: l        array[max]=array[areanums-i];
6 Z# X  f+ V1 ]1 k! Q  s        array[areanums-i]=temp;
" i2 U- d0 y- R, x        max=0;
: L% C# F7 u) g) B* F( R    }
4 x, M3 Z; r9 K}

厚积薄发

代码3：
/*
4 b3 ?1 I: T( H8 f算法思路：
（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
再加，该人的所有喜好度设为0，
（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
& g! i4 b5 G8 E- d+ w8 w（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
(4)最后输出总喜好度。
*/
#include<iostream>
1 P" C0 O" ]" y% husing namespace std;
% O" a) V4 k% h* l6 Wint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];
int temp[3];
! J7 O) ~$ j+ @4 n# t; g* hint sum=0;
int max_num()
{
# o. z/ a3 i; ~4 e# J) T    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
5 X1 n5 l7 @9 i7 w    {
% f& V1 T  w8 g) Y        if(max<b[i][j]&&b[i][j]>0)
8 f, T- Q7 T' Q8 l/ w+ h        {
            max=b[i][j];
( O3 Z% ?! U8 c! U. t            x=i;
+ d! W! W! K; |- B' a) N1 k            y=j;

        }
    }
8 S4 l1 s( x. O6 K9 }: U* g   
% b1 M* m  _) {    if(a[y]>0)
8 R' K( x. i0 m    {
' Q; `2 _( a0 X8 b- G        c[x]=y;
  C7 g0 \9 [# S8 ?  p        //cout<<"c["<<x<<"]="<<c[x]<<endl;
4 p/ u8 {! t! H* l! V3 M        sum+=max;//总喜好度加上添加
        temp[x]=max;
        a[y]--;//区域上限人数-1
% d8 \; V0 k2 Q- Z# `8 R    }
8 F- e( F' F4 V: _& k    for(int k=0;k<3;k++)
    {
        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
, q* u6 V' g1 I8 J2 [0 H6 u    }
    return sum;
6 l; T. {: h2 \: Y}
int main()
, P; c* F( _4 S. W{
  z( E, }: P4 F) }   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
, `% W4 R6 K# S7 H0 q- I) W    {
) W% T$ `5 j9 G% \  m& ^, F1 X, z& `        cin>>a[i];
  C8 ^  K' \7 R' O    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
+ X6 H5 T) s, O8 q6 V5 a    {
' g+ n# h1 `! y& k2 q: u        cin>>b[i][j];
    }
% U+ m' `' e$ k# X5 Q) z9 r! E9 g    for(int k=0;k<3;k++)
5 ~9 g: S2 v4 C' A' @  P    {
        max_num();
    }
    //cout<<"sum="<<sum<<endl;
7 m+ F8 }2 X7 @4 R    cout<<"sum=";
  ^9 s( F. ?( o. K& F    for(i=0;i<3;i++)
" [0 c* F4 l4 D' o5 o    {
        cout<<temp[i]<<"+";
    }
5 S' q, K  c( y4 w7 L1 g( E9 N    cout<<endl;
" B% v' n( u3 p    cout<<"reslut:"<<endl;
/ y) y- o& y4 y/ g1 j    for(i=0;i<3;i++)
    {
. s6 e1 T; J1 ]8 G7 Z# B        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
( d$ Y3 }& {1 r/ H0 A$ Q* F% a    }
: e, U9 W, A0 O: v3 o  @1 t    return 0;
}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
( Q7 R% c2 ^1 ^( d/ p9 C% E" U数学中国社区分享快乐！
1 O: K) `$ {5 Z/ T

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.
' L2 n5 K0 h. e" }# i3 Q( w, _

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！