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

厚积薄发

座位调整

题目描述：
# ?& s& w0 y0 s8 O7 Q
百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。
: ]) C8 h/ J3 u1 b
调整的方法如下：

1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。
" |9 B- K1 p7 |3 ]* ?, T2 F
2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。

3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。

" |# G" J& {8 m, _数据输入：
8 i3 J' w9 j! ^5 u
第一行包含两个整数 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 个区域的喜好度。
5 W& `: s- w2 k1 @4 P
答案输出：

8 o/ e6 }: z! o1 j对于每个测试数据，输出可以达到的最大的喜好程度。
, w3 |0 K- B$ a/ O- R8 B" X
输入样例

3 3

5 `! O9 j: F' y- e; }3 E0 X6 H1 1 1

; J: x, P5 j) z4 L100 50 25

7 S8 ]8 v4 B0 W" M$ g# E4 ~  _, |9 z100 50 25
' J, Q6 n/ {3 o! S% @: T
100 50 25
" @! F! g0 Z- j9 |+ t4 F+ v

输出样例

3 \) U; c* \( a0 G* C* w8 L175
9 }. A9 i8 [! _1 g1 }% A! l: [: `9 }
0 M- ~5 V! h: L3 N% u

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

厚积薄发

& n- o9 B/ Q: P: Z1 p" }
#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
: o! E/ @( ~, I( K" m0 X9 e: yint a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
int sum=0;
! b* s6 K. _" j$ N  dint max_num()
+ A3 l1 j3 ?2 b1 m% I/ I. ^{
    int max=-32767;
# d# k5 l) T) G  Y4 c) p    int x,y;
    for(int i=0;i<3;i++)
% X+ y6 {  J# n( M& \: _: Z& D; M  \    for(int j=0;j<3;j++)
7 o; u2 f# v9 R    {
" c; f, Z8 Q' o* w% C9 l$ K+ Z        if(max<b[j])
8 C; F3 c& S4 g3 p        {
            max=b[j];
            x=i;
            y=j;

) ~+ X6 T1 Q. q        }
    }
! ~) e: @3 ]2 A' k+ }5 {   
    if(a[y]>0)
    {
        c[x]=y;
/ U, o1 n$ Q+ e. Q        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
/ Y# U/ u: ~' g4 r4 z! U        for(int k=0;k<3;k++)
, t+ `$ ?. ?, O7 X# p3 F        {
) z+ y7 x/ R0 t& q, N            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
1 X* \' c4 S/ Y& Y( K; g) q: w    }
  p! D0 c0 Q. N& @  j    else
7 g& O" H2 a: i7 H; ~0 W    {
. ?9 s3 y6 U6 o' w% r- v        b[x][y]=0;
9 d* f3 I* b# |. J/ z    }
) e7 S- ^- I# a8 K# H   
% y- g6 q. |6 i* h! w6 V, r    return sum;
}
int main()
5 U/ D) J2 e+ o7 Y3 o3 H8 O4 S{
   
    cout<<"input 3 zone's limit:"<<endl;
1 O* Z. J7 m* o, l# Y, [, g" a    for(int i=0;i<3;i++)
) d( g+ W- r: v9 h- ]    {
( ?. S! }, p; @2 x0 X5 b+ p$ E2 ~        cin>>a;
    }
    cout<<"input 3*3 actangle:"<<endl;
8 _' o# L% f$ E$ \6 L2 J9 P( i    for(i=0;i<3;i++)
4 t1 y) j2 {+ w( E7 O    for(int j=0;j<3;j++)
  p* |# ~% P6 J; B. k! I3 c8 d    {
        cin>>b[j];
    }
    for(int k=0;k<9;k++)
; O+ ~, F- k4 k1 H9 a+ p    {
        max_num();
# Q5 c  Z. ]7 {, T: `' ?; g    }
: S, t& J( [! m   
    cout<<"sum="<<sum<<endl;
    cout<<endl;
    cout<<"reslut:"<<endl;
3 B7 h& h! H! L1 [$ P: i    for(i=0;i<3;i++)
    {
! B% F% q2 @# j2 I0 K& ~% O* \        cout<<"people "<<i<<" go to zone "<<c<<endl;
2 N, u* b0 E5 R/ u4 \    }
    return 0;
}#include<iostream>
using namespace std;
; F' M, J# ~% O* Q9 o  ?6 Z1 o" qint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
4 [, h' V# ~2 xint sum=0;
int max_num()
/ ^4 b' e0 D" q{
    int max=-32767;
" W) r/ F. P) Q: {! a    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
  O5 H/ n( C( p" i" S0 o- ~    {
; W# w4 N/ Y; [        if(max<b[j])
        {
            max=b[j];
            x=i;
            y=j;
7 R2 |2 c+ b6 Q
3 S1 c1 o5 t0 |! g4 `$ {        }
    }
5 j" |) `! J/ {( S( o' J# t1 B! ~, O   
    if(a[y]>0)
    {
        c[x]=y;
        sum+=max;//总喜好度加上添加
- G# N7 |& c$ a& S        a[y]--;//区域上限人数-1
3 T  s( z+ M& f        for(int k=0;k<3;k++)
& c# e' l% O- R8 K; S0 r7 [! q        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
    }
    else
    {
0 @( E- O# Y; A* B5 ~, C        b[x][y]=0;
    }
   
& d# E0 H+ G7 B3 D* U9 `    return sum;
}
int main()
& s! q: \. D4 k) K8 W{
   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
    {
        cin>>a;
    }
/ G$ q- q: }" H- y2 A0 q( k    cout<<"input 3*3 actangle:"<<endl;
1 P% ~2 J2 F4 J! H/ ~+ S    for(i=0;i<3;i++)
) @1 m" j; r4 A# y5 W* i, \    for(int j=0;j<3;j++)
# a# q1 E/ }; C  G3 J    {
& G* N: R5 o# i; D  o  T9 e, m        cin>>b[j];
    }
$ |. a, L0 A. T9 L! n: F( Y    for(int k=0;k<9;k++)
    {
        max_num();
) k: u; }8 ^* u6 ]; T    }
; A( L2 k& b9 `2 l; _. W4 \# i   
    cout<<"sum="<<sum<<endl;
    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
* v- L  F" H; k) H/ p        cout<<"people "<<i<<" go to zone "<<c<<endl;
$ N$ L2 ], s# N- }    }
; z1 m( U$ g! C! y; l" F. E3 a    return 0;
5 k9 [3 d/ S) c. Z+ J) ]}

厚积薄发

编程代码二：
#include<iostream>
#include<cstring>
#include<ctime>
using namespace std;
class ifo{//矩阵的元素
    int clerk;//员工号
    int area;//区域号
    int per;//爱好度
& K9 s; v; m; W7 Apublic:
    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
    int getclerk(){return clerk;}
. I/ m) n7 @6 E. S7 a  b1 o: c    int getarea(){return area;}
2 x7 z& p0 o% V; F* N- C( X    int getper(){return per;}
    void setclerk(int i){clerk=i;}
    void setper(int p){per=p;}
  M# m' _- c% R. C    void setarea(int a){area=a;}
};
- V) w$ a# q0 x8 O: y' m. V+ Z! Pclass area;
) i" @' }2 G! ]- s  W& [: Q" |class clerk{
    int areanum;
$ p; l' e* l! r# p! }  A; z    bool isin;
# L7 ]$ b7 @: s1 b9 U0 ]1 l0 m    int inarea;
$ {0 {& ~2 _7 b7 y" p  Epublic:
" z$ Q& E% R  G+ w    void set(int num){isin=true;inarea=num;};
    void setisin(bool b=true){isin=b;}
: k7 U/ ]0 \9 @2 _    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
};
class area{
    int num;
7 C% k3 @% E/ T7 p    int max_num;
public:
/ ^# c, x: C- s* C' W    friend void set(int);
+ e6 Y: S- i  a; m1 k0 H7 D. o    int getnum(){return num;}
0 r' `5 |- v  k, V. C* Z    void setnum(int number){num=number;}
    int getmax_num(){return max_num;}
    area(int number=0){num=number;}
  R% z6 m! Z7 {9 o6 U5 Y; D    int getclerk(){return num;}
    void addclerk(int ps){num++;set(ps);}
  A* c7 p% B0 s& ?1 D$ Q. l};
, w! }  A" ]' _void getorderbyper(ifo array[]);
6 h9 J0 l" X7 ?5 V8 C& j7 Gint areanums;
) F  N) x5 _/ Fvoid main(){
    //input
    cout<<"输入区域数：\n";
    int area_num;
    cin>>area_num;
9 h0 _: h( q, H. R' d    areanums=area_num;
- C6 k8 W- `" r    cout<<"输入员工数：\n";
    int c_num;
' S5 O9 ^) w; H: j    cin>>c_num;
    cout<<"依次输入每个区域能容纳的员工数:\n";
' B- e, Z' d* u5 L6 u1 b1 g    int *max=new int[area_num];
; O6 u/ B% x; U5 v    int nownum=c_num;
5 j% \8 S% [# X    while(nownum){
7 s) h+ V7 k0 G) A) S3 ]+ G5 ?3 Q5 Z( n        for(int i=0;i<area_num;i++)
        {cin>>max[i];nownum-=max[i];}
        if(nownum>0){
/ B6 U3 f' e' b. e, S  K, H3 O            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
            nownum=c_num;
        }
        else nownum=0;
9 y% L6 b5 T3 `2 a% \; w# R0 P4 u    }
    cout<<"按行输入每个员工的偏好：\n";
    ifo** per=new ifo*[c_num];
7 O8 w' _/ P6 s    for(int j=0;j<c_num;j++)
. ]1 g4 s3 H6 Q( }  s3 S        per[j]=new ifo[area_num];
' T: Q8 o% h( z    srand(time(0));
    for(int c=0;c<c_num;c++){
        for(int a=0;a<area_num;a++)/*
& p- Q4 i9 v8 @2 Y5 k$ G1 c        {    int p;cin>>p;per[c][a].setper(p);
            per[a][c].setarea(a);
$ h" h% _: g* ], x            per[a][c].setclerk(c);
        }
) S- o! r5 @$ I" a1 D        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
! J$ z# U/ W8 n% p% O        {    per[c][a].setper((rand()%60)+40);
            cout<<per[c][a].getper()<<'\t';
7 Z, ~$ n, m8 z5 S( Q0 Z        }//测试时懒得输入，故以60-100的随机数代替。
-    cout<<endl;
    }
2 c# T' I0 {6 [$ x* B) g* I# _    //output
: z" [3 k; M5 `        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
        clerk* people=new clerk[c_num];
        area*  areas=new area[area_num];
! K5 V, A' ^: ^8 P$ s: \9 [: z  t        int totalper=0;
        for(i=0;i<c_num;i++){
; [  H( f: s9 |  p0 a) `            for(j=0;j<area_num;j++){
            if(areas[per[i][j].getarea()].getnum()<areas[per[i][j].getarea()].getmax_num())
" Y: n. X" d" E) G" z* O* `                people[i].set(per[i][j].getarea());
" F8 U: m- [& ~/ Z$ _                people[i].setisin();
                int number=areas[per[i][j].getarea()].getnum();
6 h- D- u6 z' u                areas[per[i][j].getarea()].setnum(number);
  w8 D) p: K' Q                totalper+=per[i][j].getper();
                break;
            }
        }
# Q! x* [$ _. b, G! A        cout<<"能达到的最大喜好度为："<<totalper<<endl;
}
void getorderbyper(ifo array[]){
    int max=0;
/ c0 W1 w, D1 D* n# d# O7 r8 U0 p    for(int i=1;i<areanums;i++){
2 M: ^- I/ A+ j2 w" {        for(int j=0;j<areanums-i;j++){
  f0 f2 F3 O4 S        if(array[i].getper()>array[max].getper()){
% P5 `" k9 t" @( V0 k3 U            max=i;}
        }
/ k/ J5 U/ {% g/ H$ |        ifo temp=array[max];
        array[max]=array[areanums-i];
% `1 H' a! Q% h! E( q        array[areanums-i]=temp;
# O& c. V0 h3 w$ J        max=0;
6 g! n/ ]4 y6 V; t- t! P    }
}

厚积薄发

代码3：
/*
+ g# \% ]& M+ `. z算法思路：
" N9 C3 I* _7 ]8 B, |（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
再加，该人的所有喜好度设为0，
  y2 l% [% O: r8 `6 b: y- X（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
(4)最后输出总喜好度。
2 T1 X% x3 E. w- H- s4 H*/
#include<iostream>
8 m9 i" i8 v& c4 R- fusing namespace std;
int b[3][3];//M*N矩阵
$ g5 X( G! r( \int a[3]; //区域人数上限数组
int c[3];
( n  L1 C! I* w4 h9 i) a& `! n# Vint temp[3];
# [6 z! X( _# _- i( N/ \) T; Qint sum=0;
int max_num()
, R6 p' b3 F' L7 v4 I{
    int max=-32767;
    int x,y;
4 i1 }/ B( _0 T( f: n7 B    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
' ^7 l) \9 j- o( k. X" k    {
- S  `" e5 p+ N, z6 w9 M        if(max<b[i][j]&&b[i][j]>0)
3 V1 E( l) h8 g5 L5 U" t" ~- r        {
            max=b[i][j];
            x=i;
            y=j;

' R/ q' C" I  d% {2 Z3 z7 m2 a        }
0 z0 ]5 e' E6 i* _: `    }
   
/ p7 e- ~0 l2 m/ M$ }9 U8 d2 U# k    if(a[y]>0)
    {
        c[x]=y;
8 i/ W; n2 [: M7 n; G0 R; C' p6 m        //cout<<"c["<<x<<"]="<<c[x]<<endl;
        sum+=max;//总喜好度加上添加
! s1 P3 n; `: P+ f        temp[x]=max;
        a[y]--;//区域上限人数-1
2 m  E5 v7 E6 r  u. Z    }
    for(int k=0;k<3;k++)
5 q" U. A& t9 x: q    {
        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
    }
2 O* A8 [  a) n' L* d    return sum;
6 U! a0 D  G2 W, C0 w# R% d}
int main()
, H: V  m: L% n- d$ h) b/ k{
8 ?3 v- U: l* M+ V# D   
    cout<<"input 3 zone's limit:"<<endl;
; `, K6 m/ i$ [    for(int i=0;i<3;i++)
$ H" t: ~- A. {    {
        cin>>a[i];
    }
    cout<<"input 3*3 actangle:"<<endl;
4 m2 [3 z! l, x% y0 f1 X& m    for(i=0;i<3;i++)
% g/ F! I8 W' c; r2 F( c% |7 Z- D2 h* s    for(int j=0;j<3;j++)
$ s+ @, h  U+ ^7 d0 q* P2 F    {
        cin>>b[i][j];
& k. I3 T9 m$ ^: y/ X- e4 B    }
& x: b  _) z' ^$ W8 N+ ?$ d, O    for(int k=0;k<3;k++)
  N, T6 [2 ?) j4 a    {
        max_num();
    }
    //cout<<"sum="<<sum<<endl;
  M5 V" F9 F$ `5 |3 Q    cout<<"sum=";
    for(i=0;i<3;i++)
    {
6 ^. F5 ^: B2 T9 i0 P$ I& p        cout<<temp[i]<<"+";
* V- }- B& P) y% X6 N- H4 E4 P* l/ f    }
/ C" F( }  B! j. c" p+ B; _    cout<<endl;
% j+ U! i+ c, y) K    cout<<"reslut:"<<endl;
) w) S: C" N# I/ i9 P! K    for(i=0;i<3;i++)
5 _- R8 C* p( z6 T  k( k    {
) \; |2 H- p9 a6 k6 T3 B# n: L" y  _/ O9 a, [        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
" ?3 E  p  w$ i4 W' M% e    }
8 Z; I( Y8 P, j, U" k! e  [    return 0;
}

葉_浅浅

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

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.
* c7 _7 r0 n  I2 ]" l

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！