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

厚积薄发

座位调整
/ U4 v( x3 m( r  z0 P
2 A) n  w/ Z% X. V! |8 c, |; \题目描述：
8 N& q. I9 [1 ?8 N0 A' C/ C
百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。

# l* z! M1 H$ Z调整的方法如下：
8 l1 C1 ]) c6 Y! z7 V
1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。
% G- x, }4 }/ W0 m
2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。
: s& B& q3 P  N/ c4 W9 P
3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。
2 M- S( x' W$ C
数据输入：

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

: C& w* p- U- Q! k2 ~第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。
( e( E- ?/ k2 c
. V- \4 f9 W: S" D$ E2 {( }紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。
7 ^, @/ n) C2 c8 W
答案输出：
# M- [1 ]; w% v$ L( F
. _2 ~) E* G9 p7 G- j0 x; ~& _对于每个测试数据，输出可以达到的最大的喜好程度。

5 Y. B( B. H. f2 A3 O8 D6 K输入样例

) t! S! ^* {0 G2 e
3 3

1 1 1

100 50 25

100 50 25

) ?, W* _; ?6 z3 b100 50 25

& z# _% g4 f7 Q" ^
输出样例

- z; m8 {% Y3 P2 }; p! u  O7 Y
. j% H% s. g" `' i1 G, P175

; G% |$ c; ]+ R% O( V数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175

厚积薄发

! z& y- R$ s+ F+ S. {* u" }#include<iostream>
using namespace std;
) ^8 {1 R& e$ ]' ]int b[3][3];//M*N矩阵
- U  L& o1 q$ x- t% f- u+ Nint a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
. c/ D; R( Z& G" h9 Z. hint sum=0;
int max_num()
( s# h$ A) I7 ?( A2 f{
    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        if(max<b[j])
8 o* E* E( Q. u+ f5 Z        {
            max=b[j];
4 c: h' G0 p/ S8 v            x=i;
' Y5 S' [& h" X* N+ V; L/ }            y=j;

  M3 e( c7 Y; A4 K4 F% B2 {        }
4 X9 Z1 N( ^) F0 k$ x6 q  X    }
   
    if(a[y]>0)
! Q. H, [$ G6 u6 f    {
        c[x]=y;
        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
2 p* X1 q* ~0 s9 _7 P( S6 [        {
) I# I6 L6 |: u            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
    }
    else
    {
        b[x][y]=0;
6 V: k) E/ {7 k' s0 ^  N    }
   
    return sum;
: X( c, }. N) o/ t8 X/ g* ~}
int main()
: [7 s: a) j9 [: d) p. H# |{
   
% q# V5 z+ B1 _" T" J! m    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
    {
        cin>>a;
    }
  ^4 c8 T5 ^4 b1 T; i0 \* ^    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
4 q. b$ c# f4 V0 }0 Q5 d    {
        cin>>b[j];
    }
3 s( f2 u+ P7 q, R& p* _& y    for(int k=0;k<9;k++)
    {
        max_num();
& o4 }2 h- S9 ]7 W- u  E& Z" B& g    }
   
    cout<<"sum="<<sum<<endl;
    cout<<endl;
% Y) I& a8 z, E- T# _    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
3 p. `; F& M. C6 u    {
' ]% K7 V5 ]& {3 ^8 B0 j        cout<<"people "<<i<<" go to zone "<<c<<endl;
; S5 o3 J6 S6 R, t# I) ?( S# U    }
    return 0;
}#include<iostream>
& Q& t; Z& a2 I* u3 h, h" Q: Cusing namespace std;
0 @( [2 T: @: q, G6 D6 g( Z0 nint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
6 m6 g% Y: H; k) W; Zint c[3];//记录某人i去的区域j
int sum=0;
# s: b! }0 v! u3 nint max_num()
; n/ d- G- M- p7 a/ {0 g: H) e{
    int max=-32767;
! ~" Y$ `; W6 ^! I3 y    int x,y;
    for(int i=0;i<3;i++)
: w2 @% _$ S- j1 Q6 o    for(int j=0;j<3;j++)
- l! R, a) g1 {1 {. B, h    {
        if(max<b[j])
+ o* S8 k( X( Q! K        {
8 H" w" f, x" B& G/ |5 q- d            max=b[j];
            x=i;
* q/ }7 f' q) j% J! N1 z            y=j;
; i' V7 S/ |  \6 }% v  q
$ t. V! P4 a3 S# ~: ]: q        }
$ c9 Q, u8 Y5 N( ]: r( t4 h    }
6 F) J* M' Y3 ?! m5 x   
8 r- n6 p5 l6 V; i5 c% K5 m* {% ^    if(a[y]>0)
8 Q% B: z1 h/ F. k& F' T3 s# J    {
# ^6 u8 y, ^! O        c[x]=y;
        sum+=max;//总喜好度加上添加
* M1 h8 L9 ^" \9 J; G  z& E        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
        {
/ V2 |! G) u$ a( x) ]1 t            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
    }
    else
    {
5 Q+ g2 P2 w! h        b[x][y]=0;
    }
   
. W. c: u5 M8 V0 b; V    return sum;
: }( q8 I% m; o}
int main()
% h  Q! P$ n8 R3 G4 J( v; |. h{
! |  L5 X+ C# |  R  i' m   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
1 O! l0 t7 B* Q- }6 F    {
        cin>>a;
% h" E# `# W3 X    }
' g) _- n: a) r: Y8 Q    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        cin>>b[j];
    }
    for(int k=0;k<9;k++)
6 \: W, H! }5 O3 _  b    {
        max_num();
    }
   
    cout<<"sum="<<sum<<endl;
    cout<<endl;
    cout<<"reslut:"<<endl;
% L& W2 `' Q4 D, |2 f' a! M8 P* r    for(i=0;i<3;i++)
+ z6 L0 @  z- _& J    {
7 A1 V, w+ G+ _% `        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
* w" C; S% c6 [2 I    return 0;
, R5 a& a" U3 H; p1 v1 `. t! g$ w}

厚积薄发

编程代码二：
6 Q& a: l8 h; L* g! y4 j#include<iostream>
0 `, ^& q4 \0 ]1 |  m#include<cstring>
#include<ctime>
$ I; j1 E6 R# j6 ~) _using namespace std;
+ f" B* {: G8 _6 ?# l+ M& F( Y% Eclass ifo{//矩阵的元素
    int clerk;//员工号
: O! t& n) ?& h; c. x    int area;//区域号
    int per;//爱好度
public:
    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
7 \# T* O. B+ ]$ w/ A$ G% h$ M9 ~1 |    int getclerk(){return clerk;}
, j4 Q( y  u" E( f6 A    int getarea(){return area;}
    int getper(){return per;}
    void setclerk(int i){clerk=i;}
    void setper(int p){per=p;}
" y) {  H1 [/ |& f! f6 x4 T" W    void setarea(int a){area=a;}
0 }! o) ?, y; A! W, d% K};
+ T* M1 \1 M  y  H/ d) }class area;
( q; T. c3 [3 @! zclass clerk{
    int areanum;
    bool isin;
    int inarea;
0 ?% _; D" I! }; l" y+ C. lpublic:
    void set(int num){isin=true;inarea=num;};
4 C% t; _- J1 O    void setisin(bool b=true){isin=b;}
    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
};
5 S' \: @7 N+ r/ k- Tclass area{
    int num;
7 m+ R, `& d% [9 ~; e    int max_num;
public:
% x* Q+ q4 L; b& e    friend void set(int);
) e9 _' {9 a& ?* u8 j' h    int getnum(){return num;}
6 M& b  B2 ^( v    void setnum(int number){num=number;}
" ~' l  v/ s9 X5 g    int getmax_num(){return max_num;}
    area(int number=0){num=number;}
    int getclerk(){return num;}
    void addclerk(int ps){num++;set(ps);}
( [8 b( ~: v/ j};
void getorderbyper(ifo array[]);
int areanums;
void main(){
    //input
    cout<<"输入区域数：\n";
    int area_num;
8 }6 t7 d" t4 Y) e6 L    cin>>area_num;
! v1 H: l$ t* h1 c8 F    areanums=area_num;
    cout<<"输入员工数：\n";
    int c_num;
    cin>>c_num;
    cout<<"依次输入每个区域能容纳的员工数:\n";
9 ~, j; ~+ ~/ z# I8 Y1 ]* i    int *max=new int[area_num];
% A* G5 |$ b4 w8 Z( _0 F    int nownum=c_num;
4 z: g3 z& G! @+ U# M9 J$ e6 R, `5 @/ T    while(nownum){
5 L( s% N4 e( |, o9 |        for(int i=0;i<area_num;i++)
* _% o# I6 c2 u        {cin>>max[i];nownum-=max[i];}
        if(nownum>0){
            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
# m, H, v% V  |            nownum=c_num;
2 U; n2 v7 T. k  k& \        }
        else nownum=0;
    }
    cout<<"按行输入每个员工的偏好：\n";
, s+ }1 h1 @3 y    ifo** per=new ifo*[c_num];
! X& G" {0 _( A/ y) y1 _. j# n; S    for(int j=0;j<c_num;j++)
        per[j]=new ifo[area_num];
) r" i, D2 z4 E0 \/ N    srand(time(0));
8 [' t# t# i- i; B3 s* x    for(int c=0;c<c_num;c++){
8 d$ n0 K) ]$ E- ^7 u        for(int a=0;a<area_num;a++)/*
2 U& P6 F4 Z2 x+ E# X        {    int p;cin>>p;per[c][a].setper(p);
            per[a][c].setarea(a);
            per[a][c].setclerk(c);
        }
5 j; \2 {* g; H  N1 M0 F        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
        {    per[c][a].setper((rand()%60)+40);
% c! e7 l  R' I' f$ r2 }6 o% |5 b            cout<<per[c][a].getper()<<'\t';
+ `6 g2 V: L4 S8 b6 d, u7 R        }//测试时懒得输入，故以60-100的随机数代替。
: L! ?" z; P2 Z' E+ G' @-    cout<<endl;
    }
    //output
# w# }4 b, W; f) ~        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
        clerk* people=new clerk[c_num];
        area*  areas=new area[area_num];
" R6 A, O5 @! u# _8 C1 X9 V        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())
$ {$ ]2 d# ^- d% }: c                people[i].set(per[i][j].getarea());
                people[i].setisin();
( U% J- l0 |$ a% {+ P+ q) }                int number=areas[per[i][j].getarea()].getnum();
; |0 W& ^+ q5 H( i3 k4 T; Y0 j                areas[per[i][j].getarea()].setnum(number);
( t6 p2 F  E5 S- J0 |- k- p                totalper+=per[i][j].getper();
                break;
            }
9 p+ w4 `0 p& j6 |, f9 e        }
& `* a! \# H, t, b! \3 b        cout<<"能达到的最大喜好度为："<<totalper<<endl;
" b4 Y3 h0 z" M1 A}
6 Y# X) F' `$ o$ ^( X6 Mvoid getorderbyper(ifo array[]){
    int max=0;
& G  q2 ~, R" a    for(int i=1;i<areanums;i++){
        for(int j=0;j<areanums-i;j++){
7 J" u9 ]* e, P9 E( l9 p; V( {        if(array[i].getper()>array[max].getper()){
9 b! r6 E7 V" G% R% M" o  D            max=i;}
: k7 r. y, u5 E) Q' c7 N! H. e$ K        }
        ifo temp=array[max];
        array[max]=array[areanums-i];
        array[areanums-i]=temp;
        max=0;
    }
& T  B8 A! y% l" t: t$ m}

厚积薄发

代码3：
/*
! t5 q5 N3 _. n$ r$ A5 Y算法思路：
（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
再加，该人的所有喜好度设为0，
3 @. {% b- _4 `* J1 x（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
1 K1 e) S8 N( I  X* `( S# W5 f5 D（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
  }9 E+ e( R+ I(4)最后输出总喜好度。
5 x/ [& p$ j; f0 E7 K6 s*/
#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
4 }# M3 E8 R4 [6 F# z. ?int a[3]; //区域人数上限数组
  z( o& k1 M! B: g, [int c[3];
int temp[3];
$ U/ j8 d" n1 T" uint sum=0;
( j% i4 e5 ?2 c7 }5 ~3 Aint max_num()
+ @% T# _9 {# I3 J, D/ b{
    int max=-32767;
0 G( O4 x& Z& i- ^' k& d: q    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
) c! y  J9 p) ]! N* v9 |, K    {
        if(max<b[i][j]&&b[i][j]>0)
        {
            max=b[i][j];
            x=i;
4 M3 `% s' X  y  D% V, W            y=j;
$ h( V; y* o5 R# e+ L# L
4 s) N/ B3 W* I8 n* M        }
) u1 G% |  x1 B/ T1 |, h- }! p& I. v    }
   
    if(a[y]>0)
    {
        c[x]=y;
0 ]/ g3 w4 A  h$ W/ g$ {        //cout<<"c["<<x<<"]="<<c[x]<<endl;
        sum+=max;//总喜好度加上添加
        temp[x]=max;
        a[y]--;//区域上限人数-1
: O2 j+ _% \0 ^& ]9 m    }
    for(int k=0;k<3;k++)
    {
' d, E) W9 Y5 e  x        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
0 Y: k* p. S4 Y5 A    }
    return sum;
/ i& f/ a, @& g: G6 O}
int main()
/ {- O. p! C- x3 u  Z{
   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
    {
5 P: ~# Q6 K. A$ p  z% k+ m        cin>>a[i];
    }
    cout<<"input 3*3 actangle:"<<endl;
- Q, Z* _, `) d4 A: X' H4 t4 A    for(i=0;i<3;i++)
- x6 Y7 \! h2 h: o; H    for(int j=0;j<3;j++)
! F  l- h/ ~- R( A; t  q/ `    {
        cin>>b[i][j];
    }
/ y  I' c& z) O/ d% o0 }, l3 }/ h, I! j$ G    for(int k=0;k<3;k++)
    {
. e8 w  I( @+ x5 ]        max_num();
/ E7 [. q  X8 i/ V8 S+ L    }
    //cout<<"sum="<<sum<<endl;
    cout<<"sum=";
    for(i=0;i<3;i++)
: L# P, j$ V" y    {
/ F; @: u- J+ b% Z7 X, ^  B# |        cout<<temp[i]<<"+";
/ H" r; b) |4 L, J! r! V* K+ p3 _    }
4 s3 m" G! k8 k8 ?% f: A! h    cout<<endl;
7 d7 H; L% O. f8 l6 v# ~    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
$ Q/ ]6 r1 N/ ]7 E0 V/ q: N5 M        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
- T" Q2 a7 O8 Z4 M5 Z    }
    return 0;
}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
9 W  `7 {( P+ a' j! g" a; m数学中国社区分享快乐！

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！