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

厚积薄发

座位调整
7 {/ Z9 a- v0 x$ \8 r9 t) E' a
" ]4 _+ @- i2 s. b7 w题目描述：
" B, R- I4 j0 d# M/ r
百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。
, X! R, f2 Q* L8 U( n! |" @
调整的方法如下：

1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。
: T  n4 ~; _+ d; E6 a4 z6 }. |
5 n; t4 S+ d3 |% O% v0 N2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。
% @3 ~, u- t/ J
3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。

数据输入：
, R% E& z7 x9 A7 {4 R
第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。

第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。
) {9 X! y$ h- \* j0 }2 V
紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。
  W8 _; P" ~; v& N
5 D: v0 P* H, c2 v5 K0 U( t/ t答案输出：
; b, j$ Q/ g% Z# z
对于每个测试数据，输出可以达到的最大的喜好程度。
5 t3 f, I1 @4 a/ @6 r1 \
输入样例

9 l+ c; O' Y( J, M4 R3 u( b3 3
% v% q8 P! I. _7 B- {/ f
  P" h) i# N; A. k1 1 1

2 |2 W! ?. Y& |! ], m100 50 25

100 50 25

9 ~8 G; D- s& P( q3 P  A, N" o0 I100 50 25

$ |3 `2 q; ]$ q2 F' h: w  L
7 G, a+ W& h6 E; ]$ b输出样例

: R! G  j: J  ~
/ [; V5 t5 p8 D4 c; y9 K175
7 V6 h; e$ s# V. Q) k" m: f

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

厚积薄发

) z- D( h$ X  i$ d- R1 x
" ^, }; }9 a0 W* w& U' T! _#include<iostream>
" d' q/ |7 c0 b" j7 Q7 fusing namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
! a+ W8 s' }+ z/ j! Eint c[3];//记录某人i去的区域j
int sum=0;
8 E% l! Y8 D6 T; P4 Nint max_num()
$ I, W( F8 ]; x1 t3 B{
8 x8 O5 Q/ L& o% `) r    int max=-32767;
4 J  T6 Z5 L: r4 ^. _! j; _7 I    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
3 t. t1 Y- C& l$ \& n# H        if(max<b[j])
        {
            max=b[j];
8 P! d3 t/ x! n1 G" W            x=i;
+ M  ?( P9 Q0 E; s0 u# M6 R            y=j;

        }
    }
. a) }& M, H$ C6 Y  Z* Q5 |" d   
; M0 e, s" t) p, K5 N$ \: c    if(a[y]>0)
. H( c! i3 z* n0 h  S$ X8 b    {
. Q+ M5 \2 j1 `% q7 E% D$ ?( \3 U        c[x]=y;
3 @  V/ j8 H0 c. C) B) R" R( [        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
  s" |& a" m& @        {
' p/ R  f2 J0 b0 m! T3 R; x3 V2 _            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
+ n! t7 K# ?  N; j1 V' c3 {        }
' M: X5 K2 X) R" n: k! x    }
* v- e0 m' v, J7 B2 w  m4 B    else
    {
        b[x][y]=0;
! r( H; M( g% g    }
% Y( s3 b2 B, E4 K   
9 ?! t  b, G6 C    return sum;
* m; Z0 x: l0 `( @* _. s}
int main()
{
   
    cout<<"input 3 zone's limit:"<<endl;
$ f5 m# s3 ]( l( d    for(int i=0;i<3;i++)
$ j  o* [( e, d  M    {
        cin>>a;
    }
    cout<<"input 3*3 actangle:"<<endl;
2 r+ v; m! C5 [4 ^    for(i=0;i<3;i++)
8 w0 h' @" s6 h4 z    for(int j=0;j<3;j++)
    {
" P0 u6 }1 z# F% d8 c        cin>>b[j];
- Z# E7 {9 v9 n' a    }
    for(int k=0;k<9;k++)
+ |1 |# ^2 G- Q7 E/ G    {
        max_num();
# q! U- D5 h, c2 s; t2 C8 F7 q    }
: a& S* \! p: J/ M) r" V5 E$ o   
    cout<<"sum="<<sum<<endl;
) U- i7 X+ M6 C. b, T6 H$ x' W    cout<<endl;
$ R$ Y' _* t0 ^3 s. r2 s    cout<<"reslut:"<<endl;
' q$ Z, k. v  R$ N# m    for(i=0;i<3;i++)
    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
9 Q* Z( u' x4 B( H  H/ T    }
    return 0;
* P1 _( c/ C/ a- X}#include<iostream>
  u2 L- \, {, d& z, lusing namespace std;
int b[3][3];//M*N矩阵
" H( j) |4 m! zint a[3]; //区域人数上限数组
$ p  j2 v! w9 t9 bint c[3];//记录某人i去的区域j
4 N7 b; C: s% \int sum=0;
int max_num()
: n' U- H) F" L  q{
    int max=-32767;
1 B0 C  c/ j' ^! J; _1 Q    int x,y;
+ W4 I+ c/ {6 s1 u5 X% {. A1 p, K    for(int i=0;i<3;i++)
/ h6 I0 U. z. p2 B& F- i    for(int j=0;j<3;j++)
9 h5 _5 _' l5 W- }  @. u/ C    {
1 P* v8 O3 N( p        if(max<b[j])
        {
            max=b[j];
+ M4 R9 z% A! v; e7 [0 `            x=i;
            y=j;

3 u" L% _$ l1 G2 |1 x3 {, ~% C' e        }
) p- G6 e' ^# I8 _- Z    }
: p9 @) C/ m0 B+ l7 C; ^   
  t* ^) X3 l/ X    if(a[y]>0)
    {
        c[x]=y;
        sum+=max;//总喜好度加上添加
+ J- O5 G! U7 ~! y- {/ o        a[y]--;//区域上限人数-1
" l$ j  R) W- w, C8 O        for(int k=0;k<3;k++)
        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
    }
    else
    {
        b[x][y]=0;
    }
- }+ {( V; \' G9 k% _- z   
    return sum;
; E* V! ^( K" E' c}
1 b9 F! J8 W9 D# e0 d( Eint main()
4 c+ K' X6 U2 ~! [{
   
/ n: n' f9 @* Q+ p( [) |# S    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++)
5 t: I# F9 W& ~3 X    {
4 B" q, @" x$ Y3 \        cin>>b[j];
    }
    for(int k=0;k<9;k++)
9 ?# P  m& X# q/ b8 I8 _0 r    {
        max_num();
: C! x# `% _) ^    }
# x  u  P9 j0 x7 m   
    cout<<"sum="<<sum<<endl;
; Y* V7 M- [+ L2 N    cout<<endl;
  b+ A  e  C* R% X9 @    cout<<"reslut:"<<endl;
" [1 `* F6 ^: s$ g$ E" T    for(i=0;i<3;i++)
, ]. {) z4 H3 g    {
; x* y9 R$ ]* p4 m( O$ y        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
5 Q  G4 `" N# p  z( x, }( ~) I! V9 Y    return 0;
}

厚积薄发

编程代码二：
$ X1 n& ?. n4 `  @: l$ l#include<iostream>
8 w% a# @* _7 N2 d5 C0 B#include<cstring>
#include<ctime>
0 _1 k9 o) ?. j$ G! l6 Q- }6 yusing namespace std;
class ifo{//矩阵的元素
    int clerk;//员工号
, w1 E3 ]5 e  |& G    int area;//区域号
    int per;//爱好度
public:
9 _0 x& \5 z9 h! c& d' z    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
    int getclerk(){return clerk;}
( q% P% W0 }2 c6 b0 J    int getarea(){return area;}
% q, k5 R/ i: [+ h" _1 O1 m    int getper(){return per;}
; U; r4 l7 t8 f: u    void setclerk(int i){clerk=i;}
- Y# ~) W! Y& j# v    void setper(int p){per=p;}
2 u# W! }1 G$ K% R. P- k" p' |    void setarea(int a){area=a;}
};
class area;
class clerk{
    int areanum;
( C" O/ ~2 |2 A    bool isin;
! F* E( V/ M/ Y6 H    int inarea;
# ~/ b! J/ s3 J$ O8 P/ h/ g9 d% |public:
6 {6 @$ M4 X& W4 @- f( ^% X: P. s    void set(int num){isin=true;inarea=num;};
    void setisin(bool b=true){isin=b;}
    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
# U) ]& h5 s" T/ m) ]2 Z$ z, i9 u};
/ C0 g3 @' i6 ?* r1 {) Kclass area{
    int num;
' _0 c+ j# w, F. \- A, _) u    int max_num;
public:
    friend void set(int);
  F& `- s8 z, ?/ r    int getnum(){return num;}
1 T7 p% a" s# X3 d5 ~( ]. @, J) F    void setnum(int number){num=number;}
    int getmax_num(){return max_num;}
$ `4 w5 t  [) ~6 B5 Z8 h    area(int number=0){num=number;}
3 p5 E$ |8 _1 P  b3 ]+ L$ x; T    int getclerk(){return num;}
% l% a% B9 B+ V+ l3 h2 O    void addclerk(int ps){num++;set(ps);}
};
void getorderbyper(ifo array[]);
int areanums;
0 G* ~6 e& O1 E, [& X3 ]void main(){
" R. ^& x% {; X8 Y* H9 y8 j8 z9 L    //input
    cout<<"输入区域数：\n";
7 _2 c+ s1 }* v+ C6 o8 X& F9 {    int area_num;
3 i" Y) p0 }  R    cin>>area_num;
! _  D, a( T- z    areanums=area_num;
, s+ ^2 D9 Y' B, V' z) E% Z7 A7 ?    cout<<"输入员工数：\n";
    int c_num;
- N2 X) d* n  a$ J3 H! q7 G    cin>>c_num;
, G( A# G% H* T3 X. e    cout<<"依次输入每个区域能容纳的员工数:\n";
    int *max=new int[area_num];
    int nownum=c_num;
1 V: X9 P& W4 s% ?    while(nownum){
# n, H2 \" Q$ E" y% M0 Y        for(int i=0;i<area_num;i++)
        {cin>>max[i];nownum-=max[i];}
        if(nownum>0){
+ i: ]  ~$ I7 \            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
            nownum=c_num;
        }
2 E. o# |7 H2 R3 {. X8 X5 Z3 C        else nownum=0;
    }
) m$ S' W+ r  o' L# y1 m( i( M' [    cout<<"按行输入每个员工的偏好：\n";
    ifo** per=new ifo*[c_num];
    for(int j=0;j<c_num;j++)
) G7 D" D: z  S: D- D; d- M        per[j]=new ifo[area_num];
    srand(time(0));
& q7 P, }6 B! \) `5 }    for(int c=0;c<c_num;c++){
        for(int a=0;a<area_num;a++)/*
        {    int p;cin>>p;per[c][a].setper(p);
            per[a][c].setarea(a);
            per[a][c].setclerk(c);
        }
5 X  q: \5 U/ k+ L8 w        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
, k3 m+ E+ f4 }" U0 N0 W        {    per[c][a].setper((rand()%60)+40);
            cout<<per[c][a].getper()<<'\t';
- D6 `, I) Y' J  q' H5 ~        }//测试时懒得输入，故以60-100的随机数代替。
- e% e, B! b9 P4 A, m3 O-    cout<<endl;
    }
7 f9 m$ T; X5 B) Z% @9 s* ^8 \  G    //output
        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
+ n, I7 M5 S8 y! w/ e& g        clerk* people=new clerk[c_num];
/ c5 f/ E) c$ ^6 V+ s1 E        area*  areas=new area[area_num];
, l& m' d1 O# p. B1 P( x        int totalper=0;
        for(i=0;i<c_num;i++){
& r( K* g8 G: a3 o; g            for(j=0;j<area_num;j++){
            if(areas[per[i][j].getarea()].getnum()<areas[per[i][j].getarea()].getmax_num())
2 Y* n4 n3 z5 E; p7 {5 R                people[i].set(per[i][j].getarea());
                people[i].setisin();
4 \4 L2 V0 L4 p8 m                int number=areas[per[i][j].getarea()].getnum();
                areas[per[i][j].getarea()].setnum(number);
                totalper+=per[i][j].getper();
! q1 }4 j* @# v3 _+ X                break;
            }
        }
3 W; }! f5 D3 E        cout<<"能达到的最大喜好度为："<<totalper<<endl;
8 C. x4 U8 L7 }, M}
void getorderbyper(ifo array[]){
# t3 A7 `3 \1 h, T6 }( Z) m) y0 K9 V: B    int max=0;
  v: A3 k- z+ O. w% L* B/ E- h    for(int i=1;i<areanums;i++){
* g5 K) g6 n/ I, x& g  Q        for(int j=0;j<areanums-i;j++){
& l7 t: {  h7 g) v! Z- P( R6 Y        if(array[i].getper()>array[max].getper()){
3 A5 P! L7 |8 H' H6 v, E9 }+ C, C/ r            max=i;}
        }
        ifo temp=array[max];
, b: ^+ U4 m2 I4 h        array[max]=array[areanums-i];
+ s0 e3 h& F6 f" D        array[areanums-i]=temp;
        max=0;
# w" _9 L  U7 d) o    }
}

厚积薄发

代码3：
/*
算法思路：
（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
4 d7 r7 ?1 ]' O2 z- a' `再加，该人的所有喜好度设为0，
$ @7 f2 g' p' I% w8 T+ p（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
8 E5 v/ {5 l9 v(4)最后输出总喜好度。
*/
#include<iostream>
, w! w" q# y: i! Wusing namespace std;
8 p/ h  ?: ?& K, ?6 E1 p0 F+ [int b[3][3];//M*N矩阵
1 `' Z9 D# \+ eint a[3]; //区域人数上限数组
" `4 D  K1 W' ^int c[3];
0 Z- I& `3 y  j* lint temp[3];
int sum=0;
: S. |0 x* \8 I; h# Vint max_num()
{
    int max=-32767;
1 p" Q2 t2 M; V3 e3 K* [& O# V    int x,y;
    for(int i=0;i<3;i++)
, \' ^/ j8 j, Y2 |    for(int j=0;j<3;j++)
    {
        if(max<b[i][j]&&b[i][j]>0)
        {
            max=b[i][j];
            x=i;
4 T3 }0 Y+ E6 N1 Y4 R            y=j;
$ Q9 M) @: K, M2 f7 }) S. h
, k0 T$ d; v/ f# J5 K- \: P0 o3 v  K        }
    }
   
- I6 `$ F3 m/ F    if(a[y]>0)
    {
        c[x]=y;
, t6 ^5 i( ^8 ~$ s        //cout<<"c["<<x<<"]="<<c[x]<<endl;
        sum+=max;//总喜好度加上添加
# C& f5 C) \' ]# j: z- {        temp[x]=max;
        a[y]--;//区域上限人数-1
% b; X+ e/ b% {! p0 U& X* v( Z    }
    for(int k=0;k<3;k++)
    {
        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
. x- X& }' j& a7 T7 m, f( T- D9 i$ x    }
    return sum;
  X! V! N8 J1 ?4 F3 p% c1 Y/ I0 J+ y}
, A& |& g$ r  A5 Kint main()
{
   
# i! e9 m/ t7 ]4 \3 z3 Y% E% G3 `* K    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
0 ?# q* U" z- g5 o    {
2 q- `* O4 F: J& B        cin>>a[i];
0 ?2 T0 i( l; p$ L. d7 Z    }
; D( l# _3 G. s. V" z( Y    cout<<"input 3*3 actangle:"<<endl;
2 A) b; l* m+ }    for(i=0;i<3;i++)
1 k$ t  u8 L+ _- T    for(int j=0;j<3;j++)
, [) q* }+ N* u    {
        cin>>b[i][j];
    }
    for(int k=0;k<3;k++)
) ~6 w5 a, W. X+ |) C* A1 P    {
        max_num();
    }
    //cout<<"sum="<<sum<<endl;
    cout<<"sum=";
1 p7 h- ~3 a& x1 F    for(i=0;i<3;i++)
. y7 r0 @" q3 C* Z    {
        cout<<temp[i]<<"+";
    }
    cout<<endl;
9 g2 p; j. c& e2 L% J$ r    cout<<"reslut:"<<endl;
) H8 `$ N& Q0 |7 S    for(i=0;i<3;i++)
( a3 K( [7 i  X8 `( J& z0 ?    {
' |/ S+ s$ K5 n        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
    }
    return 0;
5 s8 s/ J  q# b9 J/ W7 A}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
7 d2 l6 q/ f6 l* N; j0 Z4 H数学中国社区分享快乐！

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.
1 Y6 p0 H* Q( ?0 g0 j0 E9 c# G

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！