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

厚积薄发

座位调整

题目描述：

/ Q; `% `9 |& F0 }6 L% E百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。
' P! ]" `. r; ?9 k, F$ I/ v
8 b. p3 R& p, a4 v4 c4 B' J7 Z; P$ p调整的方法如下：

! L2 R6 A$ |* v8 t1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。

2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。
9 Y$ p6 H  \! S0 w' W
! k6 N- M1 M( r2 O3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。

数据输入：

第一行包含两个整数 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 个区域的喜好度。

答案输出：
, {4 a, k) m6 O2 ^
  R! Q* k6 h' O! a, Y+ `对于每个测试数据，输出可以达到的最大的喜好程度。
! c1 e) B0 z6 ]
7 s9 q7 x6 r& `4 q4 L5 w输入样例

& I# o1 T  m, J: \3 3
, W: B$ l& ~0 _0 \0 H1 f* Z
1 1 1

100 50 25

7 d( R8 A" R3 Y. Z2 V100 50 25

100 50 25

5 ^6 p; ~  t! V- X* H( K- Q' L# E输出样例

3 f; g/ O6 l' E1 {  I' m! U175

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

厚积薄发

#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
5 L5 S# P( {7 L* @) A, b/ Jint c[3];//记录某人i去的区域j
9 J* i3 b  |8 ~* tint sum=0;
9 y8 q& H+ o$ o, R+ nint max_num()
{
" ^6 E2 _* a! a$ d) Q, Q6 v    int max=-32767;
. ]$ s, t9 |" h0 a9 a    int x,y;
    for(int i=0;i<3;i++)
6 `! l/ h8 B# v+ O; J5 x2 P    for(int j=0;j<3;j++)
    {
& j1 o6 Z8 ~' ~/ l) ^$ T) Z        if(max<b[j])
: t, j5 F; e; W$ H+ K5 b0 B7 x1 T        {
3 a  W0 `. r+ v+ ?9 e% N            max=b[j];
            x=i;
  B' I' L; Z: ?' y            y=j;
% V" y# x% c9 `
5 E" N+ w4 T9 h        }
0 {: |) U# X( L1 ^9 ^" n. N* z    }
( C' e9 H+ z4 g   
    if(a[y]>0)
    {
        c[x]=y;
/ y! l( Y9 P" P5 ^* r        sum+=max;//总喜好度加上添加
4 n) q! R" @4 ^2 m: Y1 Y. G        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
! O0 I; G5 a5 L3 y% G3 D        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
) O, x" o" B& i/ p7 b- b6 j        }
* g+ S$ ?3 ?# R* D4 G    }
6 [8 b- T9 P7 x. }3 N    else
" B$ {+ A2 K. C- j4 x    {
0 S' z8 D0 p( g2 T3 \/ q$ k- l9 ?        b[x][y]=0;
) A4 A& ~4 Q' t, V6 T: k    }
   
9 p5 v' I9 H5 T    return sum;
0 Y, {1 i9 Y; t0 d}
5 Y0 N  f! s9 g4 x: Fint main()
{
   
; l4 c+ `9 R+ t" ^. G% b, ^    cout<<"input 3 zone's limit:"<<endl;
! j# Q$ `* G# \6 b9 P; c+ d/ m    for(int i=0;i<3;i++)
/ N, b( w* q! j4 q9 g9 A    {
        cin>>a;
8 Z) {2 j  B! X* C5 W/ K( |/ p$ r% E    }
    cout<<"input 3*3 actangle:"<<endl;
1 o" s" f! ?, W# w  e3 q% K    for(i=0;i<3;i++)
9 I6 q" O" C2 F8 S/ a' m    for(int j=0;j<3;j++)
' ^/ L5 r2 c: g- R    {
        cin>>b[j];
    }
    for(int k=0;k<9;k++)
# z% ?* n( K; u; T    {
        max_num();
    }
, I# y' e7 W$ p! s+ M! {8 k   
" r7 E$ @( L8 _" b+ B    cout<<"sum="<<sum<<endl;
( ~9 ~2 |: C5 P, a- O, n: z    cout<<endl;
; v  ]/ B/ H( O2 I% C    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
. |6 ~: l- x0 e9 @  Q7 s3 c        cout<<"people "<<i<<" go to zone "<<c<<endl;
& a& f( n# |& w4 U+ `- N" F9 p    }
! z# I5 o  ?) R, t9 B; R  r( s1 P    return 0;
}#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
5 Z; R7 X! s# O% X" b+ \* kint a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
* B: y* }8 |& j5 cint sum=0;
int max_num()
{
    int max=-32767;
+ b* u9 m% n: }+ U& |; W    int x,y;
  t4 M, u: D) @$ X( ?    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
4 @2 r! E( i* K( O  U' M        if(max<b[j])
) R5 [9 B0 y+ w* G        {
: z4 C' z% i7 e4 ?7 T1 k; v( X9 {            max=b[j];
0 A9 t' G% ^8 r            x=i;
            y=j;
3 C: Q6 i- `6 V  f, `- H' Z" E) k
$ U( }8 b0 t- P4 }        }
6 |. N& r/ y& K3 W; N' K3 y    }
- |6 ?. k* z3 m* O$ n   
/ r% ?+ a) u) j    if(a[y]>0)
    {
        c[x]=y;
        sum+=max;//总喜好度加上添加
  Q% ?( m0 F/ y" G        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
1 C6 a3 A$ E- [$ i# U/ V# L' N2 w        {
4 @0 N3 n# \+ |: ], _/ R6 Y            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
    }
    else
    {
: {0 n- M- \3 ~2 i        b[x][y]=0;
: a! B1 k- m0 ]" W4 Z  c6 `    }
) S/ S) l" a4 Q& F/ X8 y5 P1 z   
    return sum;
1 m# E4 J) C( g1 n6 p5 B  @- t) z}
6 M% ^! c9 \5 Q  j0 E) gint main()
; Y9 V) j  x) T: J5 a6 z- t{
- T8 S% o6 [% C$ }% B4 R# j   
( F+ q' a5 ]7 Q# s6 O4 s, q    cout<<"input 3 zone's limit:"<<endl;
# H+ C1 |2 r, f    for(int i=0;i<3;i++)
    {
- m4 w- m' C- B0 R        cin>>a;
: y# \8 A: D0 Q2 A/ z& k1 ~; Z: P    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
& i& h% N5 {8 v/ }    {
        cin>>b[j];
    }
3 ?" _! ]8 V- a: l    for(int k=0;k<9;k++)
2 V$ t) o& |7 c0 j' r9 E5 h( X    {
        max_num();
    }
   
6 V+ P- }/ @1 A" f( W4 ?    cout<<"sum="<<sum<<endl;
7 n9 e; Z  b9 r- L    cout<<endl;
    cout<<"reslut:"<<endl;
9 P5 ~4 W) F" n2 z2 B# `1 y    for(i=0;i<3;i++)
( t% X9 ~  \5 a    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
; z) w4 ^  z3 d" k    }
& u, ^- Q3 u8 v& ?' e    return 0;
}

厚积薄发

编程代码二：
# `$ j! p# O; r" D4 Q! g#include<iostream>
6 {3 v+ D& q6 e. `$ s9 W( \/ d#include<cstring>
#include<ctime>
! a# C1 S. V2 c5 \" M. R9 Eusing namespace std;
0 p6 H+ y% K# K; ^( Y+ @1 iclass ifo{//矩阵的元素
    int clerk;//员工号
    int area;//区域号
    int per;//爱好度
5 N3 J9 _9 Z+ E' o  D- Ipublic:
    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
    int getclerk(){return clerk;}
    int getarea(){return area;}
- {0 ?7 H! l$ {! o3 F' {    int getper(){return per;}
- N4 @. Y# K) ~( L5 T+ S: n    void setclerk(int i){clerk=i;}
    void setper(int p){per=p;}
0 c3 n6 ]; `4 Y. X    void setarea(int a){area=a;}
& R5 S" r! ^; u7 C" R};
class area;
class clerk{
$ O1 }8 Y( c  ^5 `9 R    int areanum;
    bool isin;
    int inarea;
' m; Z, H6 V* S; n6 c9 p* k2 ^public:
& }2 K  V. B6 ]4 n7 j, X0 p    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;}
};
class area{
. p4 A, K. I- @    int num;
2 |+ W" d6 X1 X" T- V' D    int max_num;
! K5 N' i) v8 ~! e+ w& @public:
2 E. g- G$ [) ^& F+ K    friend void set(int);
    int getnum(){return num;}
# W6 m+ ?4 ~$ J# r7 |% d& P    void setnum(int number){num=number;}
    int getmax_num(){return max_num;}
; l! f3 W+ j( V" a. `$ W% C) Q    area(int number=0){num=number;}
- H' u+ Q: o/ ~* I    int getclerk(){return num;}
    void addclerk(int ps){num++;set(ps);}
+ s5 ]" |/ N- B, Y2 Q, G8 \};
void getorderbyper(ifo array[]);
int areanums;
void main(){
    //input
    cout<<"输入区域数：\n";
" [9 u3 d; R! T; D    int area_num;
1 R9 V+ i1 S. e, r    cin>>area_num;
    areanums=area_num;
& D/ E& @/ Z& g' Z$ W  u# n    cout<<"输入员工数：\n";
    int c_num;
    cin>>c_num;
    cout<<"依次输入每个区域能容纳的员工数:\n";
    int *max=new int[area_num];
" U5 [. K# E( t5 X    int nownum=c_num;
  ~3 J( W9 x6 }/ c# F: N, k    while(nownum){
0 q$ O, e* C- T+ d0 P: T/ f  g        for(int i=0;i<area_num;i++)
. g/ X! e! k+ f! I        {cin>>max[i];nownum-=max[i];}
* x2 {0 g* }! H/ g, p0 V        if(nownum>0){
            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
            nownum=c_num;
        }
2 T! M1 D# G' D" L  v8 I        else nownum=0;
    }
$ d0 o9 J! X) p! @0 b3 X6 Y    cout<<"按行输入每个员工的偏好：\n";
    ifo** per=new ifo*[c_num];
    for(int j=0;j<c_num;j++)
        per[j]=new ifo[area_num];
4 b) m# F0 L: b) s% R5 o    srand(time(0));
5 u! ]& d) ]6 d+ @- K    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);
4 `" e& M4 e; y2 d            per[a][c].setarea(a);
% f9 G9 c9 W% t1 `            per[a][c].setclerk(c);
. L; ^4 P' B* I& E        }
: v7 v+ ^7 u) \* p        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
" q. Y; V8 v' v  K0 H8 p- V! M        {    per[c][a].setper((rand()%60)+40);
( o. u# g9 y: N6 f5 M5 x* b1 G# s5 F            cout<<per[c][a].getper()<<'\t';
% H0 n; p5 b( T$ z& O7 k. W& N        }//测试时懒得输入，故以60-100的随机数代替。
-    cout<<endl;
+ i1 o9 [1 t4 Z% v    }
    //output
        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
        clerk* people=new clerk[c_num];
/ k& ]- u4 k/ I' j: d2 Q. ~! ]        area*  areas=new area[area_num];
        int totalper=0;
8 x6 s8 K, [6 |. Q# k- C0 ~7 T, c0 O        for(i=0;i<c_num;i++){
5 k5 Q/ [2 `, y% h; c            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());
                people[i].setisin();
                int number=areas[per[i][j].getarea()].getnum();
) Z9 t4 O; l9 X8 m# Y+ L                areas[per[i][j].getarea()].setnum(number);
                totalper+=per[i][j].getper();
: P- v7 T1 j+ J  Z9 C2 F                break;
            }
# Q7 }# A- Q/ B# J        }
9 D' t4 h) T0 ^$ R! ~3 q        cout<<"能达到的最大喜好度为："<<totalper<<endl;
}
void getorderbyper(ifo array[]){
    int max=0;
    for(int i=1;i<areanums;i++){
) e. J' ~5 P; v8 r4 Y) \        for(int j=0;j<areanums-i;j++){
: H+ t% @4 q" L+ u) g7 B" g8 t0 I9 `        if(array[i].getper()>array[max].getper()){
            max=i;}
        }
; R( [; [; l& J+ Q        ifo temp=array[max];
6 W. m, @1 v: C4 x5 `        array[max]=array[areanums-i];
        array[areanums-i]=temp;
        max=0;
/ r: A8 n4 _9 Q. s    }
}

厚积薄发

代码3：
* e3 ^0 t" ?8 k8 X* R6 }" I/*
" `5 Y& x: _2 ~/ H) r- L算法思路：
（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
再加，该人的所有喜好度设为0，
  M' {# J8 P0 u% Y, z% W（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
/ Q* `4 V! F0 |- B5 H1 c6 h# v* i1 Y（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
(4)最后输出总喜好度。
+ L" v3 B# ^/ d- A*/
#include<iostream>
- S& C* g; @' G2 cusing namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
+ ~3 I8 C9 h' K: x7 J; }, }int c[3];
' z, q0 Q% T& \" s- y- T  S4 Z  cint temp[3];
int sum=0;
int max_num()
9 x3 R: c8 G2 z/ B8 j- |8 V& ]{
/ O* U* G$ g2 _8 ~  U' \, w    int max=-32767;
  n" g0 @$ j$ P    int x,y;
    for(int i=0;i<3;i++)
$ G0 @2 Y% ^8 G8 [    for(int j=0;j<3;j++)
1 \, n! q  }0 U/ u    {
        if(max<b[i][j]&&b[i][j]>0)
& ]" M2 N0 Z0 Q) `1 Q9 i+ O        {
2 n  L5 l! O$ }1 p            max=b[i][j];
8 I8 v3 S" |5 e& b5 b            x=i;
            y=j;
/ V* g: r6 X" _
3 s% W7 {' V' \; `        }
    }
; \2 T2 R( B; X; v5 T: t' K/ c   
    if(a[y]>0)
# M2 g, L  I) D5 q' Y    {
        c[x]=y;
2 w7 j/ d; A9 `1 _! k) \        //cout<<"c["<<x<<"]="<<c[x]<<endl;
        sum+=max;//总喜好度加上添加
        temp[x]=max;
        a[y]--;//区域上限人数-1
    }
7 F3 q) x! H- R; o! l5 f    for(int k=0;k<3;k++)
0 L' Y% k9 G6 D9 v9 l1 B6 b/ e* R" r    {
! b% D3 I6 q* h( B* a6 n& O  [. u        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
    }
: Q: `1 z, N8 d! w    return sum;
}
int main()
  U5 h% J# U" E' n" y$ v; e{
7 K- v8 z* A  `3 C9 X7 d   
    cout<<"input 3 zone's limit:"<<endl;
2 k' n5 [9 Z0 B% i& A, }' O3 J+ |    for(int i=0;i<3;i++)
    {
        cin>>a[i];
4 q0 X; q% V% m    }
    cout<<"input 3*3 actangle:"<<endl;
, A0 `* a! }: {+ p+ X    for(i=0;i<3;i++)
5 P: v3 `2 |- q& `2 ]    for(int j=0;j<3;j++)
5 ~2 t2 i% m. N" q; S    {
. C+ e4 O$ v" n- |3 |, d        cin>>b[i][j];
! \* C" J7 Z' ]% p6 [, Q    }
) e+ d0 q3 A5 m+ {& W    for(int k=0;k<3;k++)
    {
        max_num();
    }
    //cout<<"sum="<<sum<<endl;
    cout<<"sum=";
& {6 f7 w% N% Q0 u6 u    for(i=0;i<3;i++)
    {
0 {* j  y" p7 }$ q        cout<<temp[i]<<"+";
    }
7 h: s2 U) e% g- \% t+ `, j  F    cout<<endl;
* \+ }* S; a# h    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
* P0 G3 b0 }9 x  j        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
, N  Y  ]2 j; a    }
    return 0;
}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
8 o1 b$ ^4 H. [% r数学中国社区分享快乐！
' W' k+ Y$ d! y+ H

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！