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

厚积薄发

座位调整
3 M& R* {! o+ J
: d6 Q1 E" r: d2 @题目描述：
( v7 K: L+ ?+ y* f' o$ Y/ d
百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。
1 L4 E/ q- h5 o. R3 {, U; G
) X: c% n- |3 `# ^& d. U调整的方法如下：

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

& ]8 n$ U/ U" ?, }+ r# {( O. ]2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。

3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。
8 b7 t+ r% x; J/ {5 I6 @& x
3 d7 A' a0 `3 z, j# S; e$ v数据输入：

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

第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。
. K8 J* H  s8 j% h  F8 \( g
紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。
4 s- Y! b# `0 c6 F8 K$ \
答案输出：
8 V$ a* X* d5 D
3 ?5 ?7 m) B$ i2 z对于每个测试数据，输出可以达到的最大的喜好程度。

输入样例

4 c  G4 ]. D9 V
/ c) S& t# r  O1 `& _2 C* q3 3
& b) s" ]/ c( q, v$ Z. Y! F6 w. H
# O; p' h" W1 P4 Q, w  \9 k1 1 1

100 50 25

9 F6 h) Y: K# a$ H6 R+ H- V. t100 50 25
* y/ y% L  P/ S0 d) S; e  R# Z, Q- W
- t. `6 `4 x7 N* D100 50 25
, Y3 o9 C* b* s3 Z( ?

输出样例

: w- A! K4 F0 ?# \9 n1 d/ ?- X
& j. P2 d/ B6 M- f! K3 R# ]0 ?175

" X! r/ l) G3 ~" h' E' K9 E6 p

* T! t+ X& \- t6 U: y
数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175

厚积薄发

6 j4 F4 H! l* A2 u  a8 j6 u# K5 b6 V
0 o. L9 q1 U( Q$ ]* p$ ^#include<iostream>
: @( t$ o4 f8 ]( u+ z" Iusing namespace std;
& c" i& G6 _5 aint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
* d3 K' f+ P$ k* w+ ?. Wint sum=0;
. ^' u' Z0 q. i# e0 ^2 oint max_num()
, I% ~% C: G/ d! V0 w{
" ^  ~; B+ q$ w1 U    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
/ @. z* J! ~# u+ t% O1 f: M, ~    {
        if(max<b[j])
4 G+ A$ e: H" M/ x! k        {
            max=b[j];
            x=i;
            y=j;
1 p; ?  q% q. H) C8 }  J
        }
    }
   
    if(a[y]>0)
2 s1 T1 u! m2 _3 ^9 I! K    {
        c[x]=y;
  O) h0 w1 G/ r, k- ]2 c" U0 J        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
        {
3 M! W+ M# I" D" P0 d) f            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
' b0 k  i. [# o2 F! \: j& H- X        }
    }
) Y2 Y: a  U* N    else
    {
( d8 |+ A6 A1 P6 K$ q, c        b[x][y]=0;
' Q  j- y+ O" ^- t- ], J+ u- \! s    }
% Y& d& [$ _1 o2 [   
    return sum;
}
int main()
{
   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
2 q. P+ u0 P' W    {
  _! h) J% y) ]! y% C% l% O        cin>>a;
7 @6 y* m; t6 n. Y" m7 m! y& Q( F    }
    cout<<"input 3*3 actangle:"<<endl;
4 H2 B- N+ b/ q! R! Z: q# g    for(i=0;i<3;i++)
+ F1 g* ~# u, p1 N6 O    for(int j=0;j<3;j++)
9 X4 o: E( j8 W3 a. D# M+ G    {
        cin>>b[j];
    }
    for(int k=0;k<9;k++)
' R1 ~$ A6 r+ A$ l    {
        max_num();
; q$ o/ w0 z+ v5 z. X2 ]    }
   
# y: i4 T( X6 [0 l7 q    cout<<"sum="<<sum<<endl;
0 l! ^1 K6 E  @; ]3 T    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
9 y9 B9 \/ J1 H1 O        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
    return 0;
* ^7 {6 o) O. B# H4 q3 @6 h}#include<iostream>
! _3 y, `! x6 B  g0 A8 Kusing namespace std;
( w  f( S) D+ [, vint b[3][3];//M*N矩阵
5 d* R$ h! h1 Rint a[3]; //区域人数上限数组
# h1 s/ f' k. b. n( O0 E: Yint c[3];//记录某人i去的区域j
7 ?# E$ T4 I- W! j( Y: dint sum=0;
int max_num()
; ~0 O' k, ^* h) A& N9 l7 K# \{
    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
* ?4 @5 D4 P5 R( ~! x. c4 O0 G2 @) V    for(int j=0;j<3;j++)
- I% B3 w' p" |* _- z    {
        if(max<b[j])
        {
            max=b[j];
0 Y+ N, K% u1 x# ^5 F  z( G: L& }( O            x=i;
            y=j;

        }
    }
( k; H3 D2 l& C' s+ {1 Y   
    if(a[y]>0)
# g8 j" J7 M9 H# k6 r* `/ A% v    {
        c[x]=y;
        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
- f% h' X4 s5 c: K1 `        for(int k=0;k<3;k++)
        {
3 p! ?' n' M2 O            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
% Z& z7 ~4 F' F. `" _/ h' N        }
1 N. d- d0 g3 _. w0 `    }
5 s" q. G& t: a) ?9 W    else
1 W, J7 {% i- X7 j. M; j    {
. |7 S8 j: U+ s9 b; \        b[x][y]=0;
. P2 |7 T* P! l3 w" M    }
   
& Y, E6 [- [0 [- `) }+ w    return sum;
}
int main()
$ b7 N$ R5 |8 A8 J# F2 W% s; B2 m3 i{
$ o5 D8 c7 L1 J; F   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
    {
        cin>>a;
    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
, O$ n' M, C" s1 Q. Z; m        cin>>b[j];
: L9 e' I3 G  f, ?    }
    for(int k=0;k<9;k++)
    {
        max_num();
4 [2 g) @( b; i, P    }
   
    cout<<"sum="<<sum<<endl;
( C# M' M) ~! e7 ?+ ]9 q  W# V    cout<<endl;
    cout<<"reslut:"<<endl;
. }, k9 a7 I9 o, F% W5 p4 D- @, D    for(i=0;i<3;i++)
    {
& D+ m. w" ~: D+ U        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
* ^8 P# v9 Z/ k1 T/ m8 j5 A% @* Y    return 0;
}

厚积薄发

编程代码二：
7 u9 c5 G  n3 q( g9 b8 Y) o4 v' d#include<iostream>
#include<cstring>
/ ]5 G' A/ `- q9 ^4 M- J#include<ctime>
using namespace std;
$ w2 d2 c! Y( t$ fclass ifo{//矩阵的元素
9 \. `+ h1 P) i" U' _1 A    int clerk;//员工号
5 u8 o: }; h! K2 @2 Q    int area;//区域号
    int per;//爱好度
public:
- u$ w# N# o! \3 |6 a    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
1 l" d& n/ ?8 n" f5 V$ f    int getclerk(){return clerk;}
    int getarea(){return area;}
9 L$ L% I: @: C5 L$ @2 }: b; E; A    int getper(){return per;}
! d; x2 A8 ?+ L- h! _4 {. v& I    void setclerk(int i){clerk=i;}
2 ?1 ~' K3 @3 u1 X+ |; L    void setper(int p){per=p;}
    void setarea(int a){area=a;}
};
class area;
8 W5 U- o5 E( q% ^9 U8 mclass clerk{
3 ~6 i; E- j8 j; f/ m7 m    int areanum;
    bool isin;
    int inarea;
9 L, I# C) w/ F+ b% g: n' kpublic:
2 K1 f- C. L" {) x  F    void set(int num){isin=true;inarea=num;};
    void setisin(bool b=true){isin=b;}
) j# K/ X6 c5 I  Y- ^    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
# L5 A- p, X( G};
, c; Q( I0 B9 i1 ]class area{
7 s3 x/ x0 Y, o0 T0 ~6 W    int num;
3 k: w1 ]' T6 y- _3 s: b/ J& f    int max_num;
9 c0 c/ j& s; l; }5 P" Epublic:
    friend void set(int);
    int getnum(){return num;}
    void setnum(int number){num=number;}
    int getmax_num(){return max_num;}
. m; W2 P/ t. q1 q6 b8 P+ F) [1 Y( s    area(int number=0){num=number;}
    int getclerk(){return num;}
    void addclerk(int ps){num++;set(ps);}
: F% g  n% M$ R};
' _2 `" T4 E( m8 K- \% `! Avoid getorderbyper(ifo array[]);
" T1 \8 R! b! I4 ~& O$ Fint areanums;
void main(){
    //input
# e, m& T& F) j! k% N/ l/ g0 f4 r    cout<<"输入区域数：\n";
; g# T2 r& O$ v* {$ d    int area_num;
    cin>>area_num;
    areanums=area_num;
5 y: N* u3 S! u( k& t    cout<<"输入员工数：\n";
: f3 z1 B9 H# t8 u  x& a2 H) a    int c_num;
  t- o% h! \* H- W8 |6 C    cin>>c_num;
    cout<<"依次输入每个区域能容纳的员工数:\n";
) y* w4 }; b1 c) O# i    int *max=new int[area_num];
9 Q( i0 ~$ W* s' H, ^1 b8 e* c    int nownum=c_num;
    while(nownum){
5 z# c, @+ }# K" ]& i        for(int i=0;i<area_num;i++)
! R& \6 L. |% l+ [3 N7 B0 L: N8 K        {cin>>max[i];nownum-=max[i];}
- c& `8 r9 X0 {# ?        if(nownum>0){
            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
            nownum=c_num;
( _% s1 @; `. t4 j0 _        }
        else nownum=0;
    }
0 }! q. N0 N# l$ s2 f. M, w    cout<<"按行输入每个员工的偏好：\n";
' A0 L5 }- @- m" ?; Y- I( Q    ifo** per=new ifo*[c_num];
    for(int j=0;j<c_num;j++)
        per[j]=new ifo[area_num];
, T: C* m2 u. }; Q    srand(time(0));
    for(int c=0;c<c_num;c++){
5 G" s3 d8 n) @: d" H, q1 g        for(int a=0;a<area_num;a++)/*
        {    int p;cin>>p;per[c][a].setper(p);
1 E* \" w3 ~4 s+ N            per[a][c].setarea(a);
            per[a][c].setclerk(c);
4 _. ]0 D7 @# P4 g  H' I" f        }
1 H, j" j7 R. D        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
        {    per[c][a].setper((rand()%60)+40);
            cout<<per[c][a].getper()<<'\t';
. q5 G6 ]" P& Z0 T        }//测试时懒得输入，故以60-100的随机数代替。
-    cout<<endl;
3 l& J$ o2 |! {8 ~- j) [) ~+ I    }
" i: s4 u& a% w  Q; W& f5 m3 p& Y    //output
        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
        clerk* people=new clerk[c_num];
        area*  areas=new area[area_num];
$ b- O- ?+ g! C% {3 l  r& G& q& k* k2 K& D        int totalper=0;
' y6 F+ b' t+ r, r' G. C        for(i=0;i<c_num;i++){
            for(j=0;j<area_num;j++){
. @' e& m4 X* e3 r& Q: ^9 d$ g0 C            if(areas[per[i][j].getarea()].getnum()<areas[per[i][j].getarea()].getmax_num())
                people[i].set(per[i][j].getarea());
7 {  B) ?9 l$ A+ j' p4 m# Q" I1 ^: N. W                people[i].setisin();
8 d3 }" T% p+ ^  X2 Y+ m                int number=areas[per[i][j].getarea()].getnum();
                areas[per[i][j].getarea()].setnum(number);
" p1 B7 h8 x) T7 P& D8 c- w! U- i, D  f                totalper+=per[i][j].getper();
                break;
3 V7 _0 Z1 I" W. p7 g! Z            }
: {8 y' g* U9 X/ d. q        }
        cout<<"能达到的最大喜好度为："<<totalper<<endl;
4 L5 p) j8 H! a6 z- K0 i% e}
+ S* E! C% g: n7 p6 Svoid getorderbyper(ifo array[]){
    int max=0;
; P+ T8 G7 ?* K4 e    for(int i=1;i<areanums;i++){
        for(int j=0;j<areanums-i;j++){
        if(array[i].getper()>array[max].getper()){
4 Y1 ~6 _7 {/ Q: H9 h8 `            max=i;}
        }
3 r$ c; L) s# s3 Q8 D$ _9 a        ifo temp=array[max];
        array[max]=array[areanums-i];
        array[areanums-i]=temp;
        max=0;
    }
}

厚积薄发

代码3：
/*
* h+ Z6 p+ N- c7 U9 z# b算法思路：
5 Z- B! R4 N7 g4 ^% W1 ]8 }（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
; C! Z7 k( {& |再加，该人的所有喜好度设为0，
. U" ^, O4 O# Y# B2 d! w5 n（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
(4)最后输出总喜好度。
$ J0 i' z& z" |6 |! \4 r/ K; ]  j*/
#include<iostream>
: c0 S; A. K4 e* {9 i7 o4 a/ Vusing namespace std;
int b[3][3];//M*N矩阵
% H; K/ A1 B/ g. N$ p' m0 w3 eint a[3]; //区域人数上限数组
4 U; ?4 [5 }" w' ^4 g% c5 a0 sint c[3];
int temp[3];
int sum=0;
; n9 D/ K  A# m0 D9 [int max_num()
1 U. D8 O& m) q+ u: R# L( L2 Y# c{
1 J* m* w9 H3 g' O8 b! O6 V8 |    int max=-32767;
# k  t  e4 w, P9 x+ r- M5 t. i    int x,y;
    for(int i=0;i<3;i++)
) z- z6 `& h" O6 V3 \* E# x    for(int j=0;j<3;j++)
    {
        if(max<b[i][j]&&b[i][j]>0)
        {
            max=b[i][j];
            x=i;
            y=j;

        }
5 W/ P$ {/ \3 t1 y7 u7 T! w    }
) ]& T8 y6 N0 ?6 H' a8 H" K   
    if(a[y]>0)
# f6 k  k' v: r) k  y0 t- e    {
        c[x]=y;
        //cout<<"c["<<x<<"]="<<c[x]<<endl;
3 P3 C; k- ]* l  k  {+ z+ \, z        sum+=max;//总喜好度加上添加
        temp[x]=max;
- \7 p' v4 S5 ]8 B9 E        a[y]--;//区域上限人数-1
    }
& \. G, H+ q; \0 |9 I    for(int k=0;k<3;k++)
    {
6 [' B5 U( X) G% H0 n( O; Z7 L        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
    }
* x" A" O+ l  R) ?6 O    return sum;
}
int main()
{
   
/ c5 C; Y: L  R7 t" z    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
    {
        cin>>a[i];
7 m; g( U2 n+ ]$ h& x    }
    cout<<"input 3*3 actangle:"<<endl;
; u$ x( P3 I' j    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
0 o" J4 U+ ^  |5 H2 j! [- R) x        cin>>b[i][j];
    }
    for(int k=0;k<3;k++)
    {
0 ~, J4 E# f" ^3 O! |$ [+ R0 R; j        max_num();
    }
) \3 |% `6 Y& Y3 t" Z    //cout<<"sum="<<sum<<endl;
    cout<<"sum=";
9 O' o( @' H" w6 j  `5 ]- B1 a    for(i=0;i<3;i++)
    {
        cout<<temp[i]<<"+";
    }
; R  |$ z$ I2 \5 S    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
  R1 y1 `7 d9 ^    }
% m; U4 \3 g, S4 Z    return 0;
}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
$ K5 Z& `6 u# v; h% a0 ?- c& [数学中国社区分享快乐！

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.
% J2 V0 G; |5 o) h% S% b

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！