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

厚积薄发

座位调整
7 e* f2 m/ N# `' P; ]" L# a- H1 g
* g4 F# W3 y: W0 K1 J& s& E题目描述：

百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。
1 K6 ~1 O: @. ]( D
调整的方法如下：
6 U+ K" {( [7 S1 E) k2 O5 f
1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。

) c# v' U* F% E* w6 g- k2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。

3 d3 A( b: N! ?' N9 }; O% `* X0 e$ g3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。
( }  u0 H: E# x# L- m2 `, x. |
数据输入：

第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。
- b$ W4 L. [8 A
第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。

7 j, a0 D; c% M1 Q! W3 R紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。
* }  K1 B# @% Y( \/ T$ z# L
/ K/ {% _% @' g' U7 r答案输出：
+ L/ }) F" T/ X6 [
7 i) r5 U3 R+ b1 a( _8 v对于每个测试数据，输出可以达到的最大的喜好程度。
! g0 g& |8 P8 ~
输入样例

  f$ T6 V2 u1 s. F9 A; |' z$ k3 3
' c  f! b+ r# Z6 I; S( L! w
  p2 @8 e0 B+ p+ B8 b, n" H1 1 1
( ~$ W3 A. ]) z  L
100 50 25

100 50 25
" Q7 Z" E! Q4 c" ^- l
3 g  S7 }, a/ B' G6 O( @8 p9 F100 50 25

( V) f2 C( _9 S& N; K8 M  v输出样例

. q5 B9 {, k0 I0 |6 R3 Q5 Q. _- G- J
3 F7 c( ~- G6 j9 l175
& f8 t; K! f1 L0 H+ L

$ q; }3 h( W. o1 \- o# v" y数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175

厚积薄发

' r) S0 S1 R% @3 d0 S
#include<iostream>
/ R% i( J" W% ~/ }7 _using namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
( `' v5 c; t  H' w- T- r2 Bint sum=0;
int max_num()
{
    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
+ j) V: r' e' r* d5 Y- Z    for(int j=0;j<3;j++)
    {
7 P; f5 J, @5 V  Y4 G9 K3 E        if(max<b[j])
  n5 j: g2 v. R; G/ W2 Z$ K        {
/ Q" P* A( n8 c  {) o  m' M            max=b[j];
+ a  ^, |* z) @) G1 y6 S            x=i;
            y=j;
2 N6 J( Q3 G2 X
        }
/ X; H9 s) S) w5 M* Q" O' I    }
- A$ \! [! c: F4 n" G  @- K   
$ J0 a' w  M4 N0 {    if(a[y]>0)
    {
0 N9 v  S$ e4 i1 r3 C        c[x]=y;
1 `) n( A" {% P* E1 ]        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
" u. m8 d3 o& u) O& t7 X        for(int k=0;k<3;k++)
" w/ |( c4 w& ?) D( |2 q- a0 J        {
6 {" v2 N1 q  }0 h; |0 A( D4 F            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
    }
    else
( R: F; B, P- {3 F9 g    {
5 E6 K. }% z4 y# u5 u1 [& S        b[x][y]=0;
8 |' a: V0 q( P    }
   
/ \$ e3 }3 q& v0 v9 s5 \    return sum;
}
int main()
{
   
! h- n3 c$ Q8 K$ v, R$ _    cout<<"input 3 zone's limit:"<<endl;
0 p+ F% w: P# _    for(int i=0;i<3;i++)
& w, U8 W$ h2 ]; n    {
        cin>>a;
0 b& o, m8 v: i    }
* Q! r- _/ p0 j  L- k; K    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        cin>>b[j];
" H  u; o& |8 C: ]9 I6 K, S    }
    for(int k=0;k<9;k++)
5 R$ A3 i) b* L) H    {
        max_num();
+ J7 {1 J6 b9 f    }
" n& [# H( u4 N! ~' C   
    cout<<"sum="<<sum<<endl;
    cout<<endl;
    cout<<"reslut:"<<endl;
4 b6 c$ ^1 L) @) r7 L# X    for(i=0;i<3;i++)
    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
- P( }) T) Y2 Q$ Q    }
6 G$ t$ a. V5 I# ~/ i4 F0 C6 ^    return 0;
}#include<iostream>
, v! g6 \, S: W6 O( P8 J2 wusing namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
* Y) [2 e& N  H. R" [0 n7 [int c[3];//记录某人i去的区域j
1 g& S5 G4 b. y# l9 C7 \2 X5 bint sum=0;
int max_num()
{
    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
* x! u7 S( \. C    for(int j=0;j<3;j++)
; L; r! b  B! M! Y* y1 \; |    {
        if(max<b[j])
. ?, N8 F9 U. B        {
            max=b[j];
            x=i;
            y=j;
' v3 J. v: ^8 z2 T4 N! N
        }
    }
. a+ D; a2 D( Z/ p   
7 f6 a8 G6 K( G. @    if(a[y]>0)
    {
7 M2 R6 p' k# {/ i8 \5 a( H, S        c[x]=y;
        sum+=max;//总喜好度加上添加
$ \4 i8 u' x5 w0 l4 l2 D- u        a[y]--;//区域上限人数-1
, L! g7 G2 C! w) q4 G: [* B8 O        for(int k=0;k<3;k++)
9 M5 P. M8 Q/ ^' ?* R8 k( A/ s        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
- S9 z; k; H" D: u4 A        }
    }
    else
    {
. r8 y+ g% \! N: f* `        b[x][y]=0;
    }
   
+ M/ Q9 j6 ]/ f; J+ E8 ^: r    return sum;
}
int main()
2 e# R, b. J) q% [. l5 j# b% o" T{
   
2 p4 t% k9 w5 \- G, y3 Y    cout<<"input 3 zone's limit:"<<endl;
: S1 M; r3 t. K8 [6 j7 h9 v    for(int i=0;i<3;i++)
# t- @5 M9 r/ X/ \    {
/ a- m3 a6 b- C. X6 n8 Z/ a        cin>>a;
    }
$ H1 K/ T  b, O# q- Z2 l    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
7 E) q! X5 x+ @0 G" R5 |8 Q. F6 ^9 D    for(int j=0;j<3;j++)
    {
9 P5 U1 N; G0 R4 g/ v        cin>>b[j];
, O% w3 H+ k, q1 s( I1 k. |    }
- h2 ?  I% i5 T9 F2 z5 ?& ~    for(int k=0;k<9;k++)
    {
4 D2 P$ v+ T7 r: Y- y9 ]        max_num();
    }
   
. _7 d6 ^, P/ h* ^6 C    cout<<"sum="<<sum<<endl;
( s8 |( c) ?, x. l    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
& W1 `$ [3 \0 s% o! k' C) j1 v! `        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
    return 0;
}

厚积薄发

编程代码二：
" _% k$ w( _" E; d, s#include<iostream>
#include<cstring>
#include<ctime>
1 [! k3 n& {! H( z9 ?using namespace std;
class ifo{//矩阵的元素
" M$ m8 d5 B* [    int clerk;//员工号
    int area;//区域号
    int per;//爱好度
public:
    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
. w6 V7 J% P0 i' q, D' V2 `! ?    int getclerk(){return clerk;}
9 @3 n0 U' o/ y    int getarea(){return area;}
- d  M" X/ _, G( a7 H1 w: X; P3 d    int getper(){return per;}
    void setclerk(int i){clerk=i;}
    void setper(int p){per=p;}
6 P0 s" @0 W, u: [( A    void setarea(int a){area=a;}
" G+ d. p7 d( V$ e7 [};
) D  o, I( G! R1 Q* X$ l. `class area;
class clerk{
    int areanum;
3 ^% J0 S' K' D* H4 ^4 c    bool isin;
    int inarea;
! w  _, J( P% o: rpublic:
0 }" ]' H( |0 Y& D. k9 o6 C" p    void set(int num){isin=true;inarea=num;};
4 U+ p& m3 t5 J# j    void setisin(bool b=true){isin=b;}
6 Q% M% A6 P5 P. G    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
( u3 [! m# M4 A1 V# j7 V# A};
: X/ E7 V3 c* cclass area{
    int num;
    int max_num;
7 S8 A% L0 v( A' Q* Dpublic:
7 ^; \& N! w7 b, D- s) {2 Y3 [    friend void set(int);
$ m; F6 a) r% K5 s    int getnum(){return num;}
    void setnum(int number){num=number;}
    int getmax_num(){return max_num;}
    area(int number=0){num=number;}
0 S1 M+ L4 |2 M6 Y# m    int getclerk(){return num;}
% R; ^, s+ V& c* G$ _    void addclerk(int ps){num++;set(ps);}
};
! l8 c* J0 W6 S" d. r+ Wvoid getorderbyper(ifo array[]);
int areanums;
void main(){
) c7 F# D; Q4 O0 y7 }( {    //input
    cout<<"输入区域数：\n";
    int area_num;
% {' T6 t4 g/ W. A, c6 o6 [) @% ~    cin>>area_num;
3 z" h+ @- m# ?    areanums=area_num;
: f6 ^/ n2 Z5 w/ {1 j    cout<<"输入员工数：\n";
$ A. _! @* }. N$ X1 _* U    int c_num;
    cin>>c_num;
# v0 s' `8 K9 Q! }% @1 M! o! G    cout<<"依次输入每个区域能容纳的员工数:\n";
& Z# v. Y( g% _* O    int *max=new int[area_num];
    int nownum=c_num;
6 V: L5 C! E' J, C# F    while(nownum){
+ R7 p0 {! V3 p        for(int i=0;i<area_num;i++)
8 w5 s8 A: i" e        {cin>>max[i];nownum-=max[i];}
        if(nownum>0){
- j0 I) J& K/ p1 X& }            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
" n- _9 U! K9 Z- M            nownum=c_num;
        }
        else nownum=0;
    }
3 H6 M# U. P2 H: r# Q& \    cout<<"按行输入每个员工的偏好：\n";
6 c0 B2 X" l7 g$ Y5 ?5 c- i( l. d    ifo** per=new ifo*[c_num];
    for(int j=0;j<c_num;j++)
        per[j]=new ifo[area_num];
    srand(time(0));
    for(int c=0;c<c_num;c++){
% E& [/ ]# `9 n! E5 p( P        for(int a=0;a<area_num;a++)/*
9 _' Q$ H) \: a' [5 Q9 M! S( q        {    int p;cin>>p;per[c][a].setper(p);
            per[a][c].setarea(a);
            per[a][c].setclerk(c);
  o0 W* f/ q. k' E) s        }
1 D7 {" M2 S2 P/ ~6 c        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
1 e! H9 o9 n; X3 z% M3 E        {    per[c][a].setper((rand()%60)+40);
            cout<<per[c][a].getper()<<'\t';
$ [7 Q9 Z  H) X. y$ _7 }        }//测试时懒得输入，故以60-100的随机数代替。
-    cout<<endl;
* Z! S5 f2 N( K8 D    }
9 n' H% t: U# _    //output
. Q; V3 Z# p  j! ?3 x        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
: l# Q6 P% z" ?- z2 i1 ]0 d        clerk* people=new clerk[c_num];
2 y8 A6 c# m! {. M" O' X# C        area*  areas=new area[area_num];
* t1 s' t; F9 S. I3 N# J        int totalper=0;
: [  Z% Z$ v- ^7 [' {4 y! f        for(i=0;i<c_num;i++){
& e1 c) b' d9 V7 D, T; |            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());
& H2 t8 b3 }: @; A& u0 Z# l                people[i].setisin();
! A% M2 C% N) Y4 a                int number=areas[per[i][j].getarea()].getnum();
# R. V' F# S( `: B! S                areas[per[i][j].getarea()].setnum(number);
                totalper+=per[i][j].getper();
8 q* z4 l  V! z% m. Y                break;
% _% i! |; z% y+ J4 M  o7 |% T" }            }
8 b( x' y4 f( H) F9 j; t1 V        }
: O: U, f- ~; H: J        cout<<"能达到的最大喜好度为："<<totalper<<endl;
. [( J/ |  f; v: S( [/ q7 ~}
void getorderbyper(ifo array[]){
% F, d' K* M6 W+ x    int max=0;
* z* d( Y( V" P' m' d( Y8 _    for(int i=1;i<areanums;i++){
( N: R, B" X5 Y" Z. P        for(int j=0;j<areanums-i;j++){
5 T: `* D9 b; Y+ o- j0 `2 h# q( ~. ?. _        if(array[i].getper()>array[max].getper()){
            max=i;}
+ A  M4 y: g- ?" f9 w0 r; f        }
0 R, g; F7 Y7 Q; }) L' b        ifo temp=array[max];
. O# x8 u) w& v) m) [  Q        array[max]=array[areanums-i];
        array[areanums-i]=temp;
        max=0;
    }
}

厚积薄发

代码3：
, {% a; q8 O( f) x0 y/*
算法思路：
2 t. _; d& l3 s: }. k（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
再加，该人的所有喜好度设为0，
/ B  q! D  V( D# l6 Y. Q( u7 Z（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
7 i" {5 [1 `- W' c! t' `; y(4)最后输出总喜好度。
*/
#include<iostream>
4 W" w: ~# D% y  o  Eusing namespace std;
int b[3][3];//M*N矩阵
  d6 K2 D2 e% V7 e( P& ^int a[3]; //区域人数上限数组
" K2 S3 X  ?0 V# i: _4 }: u; mint c[3];
+ b9 \0 ]1 `! g# q( k& Sint temp[3];
1 c! Y0 `) |% ]" Gint sum=0;
int max_num()
{
    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
+ R' Q! v- Q/ ?: T3 p( t    {
* c, d& n* ~; B) B+ e        if(max<b[i][j]&&b[i][j]>0)
        {
/ f) @# Y2 J' N8 A            max=b[i][j];
/ I: e& Q- k- ?6 W7 u            x=i;
            y=j;

& ]/ R- U# t& q9 {        }
1 @6 U% \$ U& O" d. w; `0 k    }
. e; r  J+ `7 W; S- H( |  M   
& A% m6 R. h. R) t5 c    if(a[y]>0)
& V5 A4 [1 q& a; {2 q) r' j4 @- o    {
        c[x]=y;
# m* S5 d, o6 d# w3 H; G        //cout<<"c["<<x<<"]="<<c[x]<<endl;
# P" ^" _/ a( [* F# `" x$ u, y        sum+=max;//总喜好度加上添加
        temp[x]=max;
        a[y]--;//区域上限人数-1
8 w" K' e4 ^" V$ h3 M  l1 }: ?    }
& R% Q8 n. g0 d  D9 j/ t+ A    for(int k=0;k<3;k++)
- G& r& V5 w' A- \& @# n- V    {
        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
    }
    return sum;
}
' x. y9 q7 i- r: w0 I- Y" Y4 @& }int main()
9 C# L6 U; t' D* D{
6 N# j9 D* F+ R1 H0 H   
$ @1 O% S: R4 d' k3 Q) }" ]: B    cout<<"input 3 zone's limit:"<<endl;
% Q  t$ A% F0 N; a6 H    for(int i=0;i<3;i++)
    {
; n# Y% O" G8 b7 p4 _8 ?4 I        cin>>a[i];
6 O3 z# S6 z' t    }
( K/ @0 {$ `: G% H1 b    cout<<"input 3*3 actangle:"<<endl;
0 P4 [8 n5 @7 w5 Q6 y/ c' N4 x1 I0 k& ^    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
4 N  I0 @% `. Y1 S* F    {
1 }2 f, c9 i! y& v        cin>>b[i][j];
    }
) c3 G3 d  O8 D* l5 N* H    for(int k=0;k<3;k++)
2 v% z: o" N; l: z( z% I3 e    {
        max_num();
    }
3 k% L3 w- ^1 C    //cout<<"sum="<<sum<<endl;
    cout<<"sum=";
1 }5 H) m8 `6 P7 A, t6 X    for(i=0;i<3;i++)
- a4 b' h! q: ?3 Y    {
0 P/ E6 F( _! q/ b; N+ u, ?! D        cout<<temp[i]<<"+";
8 f! u  ]1 N) }- ]; y    }
    cout<<endl;
    cout<<"reslut:"<<endl;
" w' V4 u: N! P# F9 _* i* G    for(i=0;i<3;i++)
    {
7 M) O. f; H. S+ i; L  O6 _- e        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
    }
    return 0;
}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
0 u- E" f) }4 x7 P: W数学中国社区分享快乐！

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！