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

厚积薄发

座位调整
0 S4 W# ^% ^2 E" B' y1 j
3 Y; J+ T! d  r5 ~# V题目描述：

* {) S/ y+ n6 Q2 q# L- y百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。

调整的方法如下：
( E0 L+ [7 p9 i; o- W$ Y
1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。

2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。

3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。

9 y5 z5 c/ r4 _9 s3 e6 b% I9 V数据输入：
' V! M6 I% }$ ?) a5 ?
第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。

第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。
2 d6 T* R3 ^2 B1 O. j
  I+ E9 e4 d6 c# m2 Q/ w紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。
0 n& R0 K" m$ d/ I
/ a: f5 }/ y, L$ D- W/ q8 p' S; x& y3 b答案输出：
% L- r$ j9 m5 v# [$ u  X1 B
; p, F0 _  R# ?( x& F# w* R0 F对于每个测试数据，输出可以达到的最大的喜好程度。

输入样例

2 a4 j; a' |9 e" ~9 q3 3

  D4 A; j9 H9 t2 `1 1 1

100 50 25

2 O5 R' p& {7 w# `100 50 25

; z& c8 e0 C$ p" Q0 q100 50 25
0 T7 d/ u$ u5 N  s( N9 f

& ~. D- U( S7 Q& H: G
, F' a+ s3 Y( d输出样例

  y* ^3 ^6 D! p  Q
& B3 e2 j" Z/ D* I- {9 t175

" h* S+ P5 Z) [' {9 V

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

厚积薄发

9 s- h4 N: G  a#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
5 x1 K& b5 i1 e  @, e' ~" Yint sum=0;
! V5 D3 ?5 ~4 Jint max_num()
# Y: X4 x) p9 B{
& m" \7 Y' g: ?: m    int max=-32767;
; S& _' e- Z) M8 o9 {    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
# Y$ {1 m) N0 t- Z! A8 ?    {
/ r5 O2 t" C% Q        if(max<b[j])
0 S& s1 P% ~6 G- o1 ~$ G        {
            max=b[j];
            x=i;
% \& J2 g+ Y$ @/ I            y=j;
+ b- C: M& V* s; e. N9 H- }4 _
        }
5 p6 |2 d! |5 k* J4 f" Z" N    }
  K. j. ]$ Z5 o% g/ B/ ?   
) U5 P/ T# j: y2 i    if(a[y]>0)
( t/ D# v. _8 y; c, O    {
! N6 s  D& M, B* Z7 O- Z        c[x]=y;
5 F( ~+ v! Q- p5 g) C        sum+=max;//总喜好度加上添加
5 T! K. v1 n% e        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
, e- ?" g: b/ u0 J( g        }
2 C( j$ y2 d/ x1 j" m    }
1 O) }2 t' ?) S+ \: Y9 z' P    else
7 I6 f# S7 D7 ^+ \    {
        b[x][y]=0;
+ x: x6 }; i! m: |: O& {    }
   
" {* i; p2 ^! o* N    return sum;
}
int main()
' y5 h: S1 i2 h' H/ H{
( g- F1 _% _0 R2 R, }" ]& a" K1 o  p5 K   
    cout<<"input 3 zone's limit:"<<endl;
# `" [3 ]$ b; e5 G$ I0 F    for(int i=0;i<3;i++)
4 g4 g- h! \( x# P2 W" ]- x/ B    {
        cin>>a;
    }
% W) [: e+ d# K9 Z/ ]- Y    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
: D6 `# e' E; T* A, d/ C- O, v& [* c    {
1 `) U# N  E* J$ G5 B  X        cin>>b[j];
    }
& L9 E  u) B3 q9 G/ b  `    for(int k=0;k<9;k++)
    {
, l/ [9 _5 i4 G) H$ B        max_num();
    }
   
    cout<<"sum="<<sum<<endl;
- G8 N2 Q- j  F, f    cout<<endl;
    cout<<"reslut:"<<endl;
# T) n; v3 Q/ S4 G% D    for(i=0;i<3;i++)
    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
% Q4 j0 p' M' B0 f9 {. P, K    }
    return 0;
$ _6 B3 r6 i. S}#include<iostream>
# t  [1 ?/ L$ y8 susing namespace std;
int b[3][3];//M*N矩阵
1 N- a# z) p+ iint a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
int sum=0;
int max_num()
0 B2 e7 k" m4 O9 h. L{
. p2 h$ V- [  c" {3 z    int max=-32767;
    int x,y;
4 ^+ i0 M( P6 N    for(int i=0;i<3;i++)
0 e% @: M* V4 `0 @! B" `, y    for(int j=0;j<3;j++)
, x! i8 X9 }, Q& n/ r4 z    {
        if(max<b[j])
7 M; T& Y1 _2 T8 k5 _* I% d        {
            max=b[j];
            x=i;
! Y' \. Z$ K2 f' i, e            y=j;

        }
" X6 k3 K( h4 n1 }& q. Z0 L7 ]    }
  _" I4 h; g/ H, p; g+ A   
9 |, r. |( G1 m9 c- u    if(a[y]>0)
    {
# d& o( e; n2 @; K        c[x]=y;
& P: e) |- y  U5 }        sum+=max;//总喜好度加上添加
! q. {& i6 }3 a( `0 d        a[y]--;//区域上限人数-1
% l+ l2 z+ \4 K! t$ J7 D        for(int k=0;k<3;k++)
7 l8 q) _5 m3 l( b; \8 G  L; y( _        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
    }
' M& C1 T8 r  C, `. v0 J) q    else
( Q+ x% H) C5 E6 T1 }3 K    {
  M& X: E, W; ~3 U; H& l9 M        b[x][y]=0;
    }
1 M4 }% h/ W6 l7 l0 y" ~   
    return sum;
5 P9 R; w9 {  J; S5 C1 R% y3 {}
6 z& y4 J. M) p6 N$ O; Bint main()
4 w. R& ?9 G: Y{
3 i2 F5 j6 G9 p$ U* G- u5 r   
0 W/ h* ], t2 Q9 x& c2 u" a! y    cout<<"input 3 zone's limit:"<<endl;
- b! h7 y, `  V1 i- S  F    for(int i=0;i<3;i++)
9 `; p) a0 n( P0 e+ |0 D    {
$ \# g. R6 S3 o) n* F1 R" F* b        cin>>a;
    }
# E& \4 \% I: x9 t+ K7 w$ F* d    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
4 v( F) u8 k  y# I7 u        cin>>b[j];
5 w6 U5 g( z" n    }
    for(int k=0;k<9;k++)
    {
- g2 O! ]. J4 ~# _( @        max_num();
" q$ v! _, l. @# W    }
   
  K* k+ }9 ]* i5 b- J1 b5 H    cout<<"sum="<<sum<<endl;
    cout<<endl;
$ O! x) O7 h) v* v5 w/ I  `    cout<<"reslut:"<<endl;
$ g& z4 H! V9 w7 b$ B3 ]7 @! U    for(i=0;i<3;i++)
: H& ]; ^( c: z& g* f3 y  ^    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
    return 0;
3 K: o3 Q6 ~% _7 |4 G}

厚积薄发

编程代码二：
#include<iostream>
9 ^# i  k- Q" D  G4 s) x#include<cstring>
#include<ctime>
using namespace std;
) A: m% I/ N( t; _6 I2 |( Zclass ifo{//矩阵的元素
    int clerk;//员工号
    int area;//区域号
4 H: q% T! Y% w. T$ K2 t8 {6 \    int per;//爱好度
2 B# b. {5 O, V8 I5 n# lpublic:
' [$ t5 b- f% L2 B    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
6 B5 d  k4 K8 C" ~    int getclerk(){return clerk;}
% a3 ^3 M/ x4 `$ R$ ^    int getarea(){return area;}
    int getper(){return per;}
    void setclerk(int i){clerk=i;}
$ f; _1 j7 T- d+ f6 J+ B    void setper(int p){per=p;}
. j7 ]+ f. y. X  L" N    void setarea(int a){area=a;}
};
class area;
class clerk{
    int areanum;
( N$ x9 d) r* g7 y    bool isin;
) o7 J! ^9 f8 J- Y. z    int inarea;
public:
    void set(int num){isin=true;inarea=num;};
    void setisin(bool b=true){isin=b;}
9 y& o0 T! k( M+ ]9 E8 A1 [    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
1 h  j$ [# J* P  E6 u2 c};
class area{
    int num;
    int max_num;
7 L+ m& B5 F  i  _, R5 j; Npublic:
1 V" g! @# z/ Q; o  m' q" C# k; `  o    friend void set(int);
. @+ B0 R- D9 S" e. \, x1 k1 c    int getnum(){return num;}
    void setnum(int number){num=number;}
    int getmax_num(){return max_num;}
# _+ S- [: ^- v4 q, {1 ^# I    area(int number=0){num=number;}
2 _" p/ v2 x: w( L. V. p    int getclerk(){return num;}
    void addclerk(int ps){num++;set(ps);}
" i; [" N- [! p5 ^' A};
- [; b% a( G/ b: D! h! k( svoid getorderbyper(ifo array[]);
int areanums;
void main(){
    //input
; C! f* t% U/ U# t4 \    cout<<"输入区域数：\n";
    int area_num;
" e. v2 M, e! c8 _4 ]    cin>>area_num;
" t6 f3 Q( N; m' e, X    areanums=area_num;
    cout<<"输入员工数：\n";
    int c_num;
    cin>>c_num;
    cout<<"依次输入每个区域能容纳的员工数:\n";
+ f. @% c0 x! s    int *max=new int[area_num];
  l! }/ W5 l5 d, E    int nownum=c_num;
    while(nownum){
        for(int i=0;i<area_num;i++)
        {cin>>max[i];nownum-=max[i];}
4 }$ z. K  K: ^$ j1 r        if(nownum>0){
# G; R' c# [* m0 H5 r5 ?& k, W: A            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
            nownum=c_num;
  m& h) L( |  _& @  n7 F2 Z1 E        }
) m" Y3 P) Q) S3 m0 q( S8 ~        else nownum=0;
    }
* ]1 U) A  U, x6 u# k    cout<<"按行输入每个员工的偏好：\n";
    ifo** per=new ifo*[c_num];
; I* y2 O, N% C2 [+ m0 N9 r    for(int j=0;j<c_num;j++)
% \9 m% F; o' v8 h5 A6 ]4 k$ r        per[j]=new ifo[area_num];
    srand(time(0));
8 x: I/ q/ b3 B    for(int c=0;c<c_num;c++){
9 [# d9 `! s7 X& \" c! q1 f, d        for(int a=0;a<area_num;a++)/*
. f: x/ n6 ]* W" I% p4 ?        {    int p;cin>>p;per[c][a].setper(p);
& r# n( H% Q8 A8 I) j! \& K            per[a][c].setarea(a);
9 ^3 V: n+ d1 o$ {9 k8 s            per[a][c].setclerk(c);
        }
. h, s. E2 A2 b3 Y        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
- _" C: z& V2 O8 o; \$ f        {    per[c][a].setper((rand()%60)+40);
            cout<<per[c][a].getper()<<'\t';
, Y& `4 L: l. G( Z( O5 V& z        }//测试时懒得输入，故以60-100的随机数代替。
-    cout<<endl;
9 K+ p3 z2 r& P" o9 U    }
3 D& F, c+ C3 S% H    //output
        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
$ \2 x& k3 l& p        clerk* people=new clerk[c_num];
, x4 ~7 u0 X' H- y  ~; c        area*  areas=new area[area_num];
' t5 M; z, T, v- f1 P. m4 e; D        int totalper=0;
' {2 i1 q; Z$ w. n  t3 h        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())
                people[i].set(per[i][j].getarea());
3 A& h5 G1 L' G/ Q* t                people[i].setisin();
                int number=areas[per[i][j].getarea()].getnum();
3 C, _3 A4 R) |0 c                areas[per[i][j].getarea()].setnum(number);
) Y1 i; a  N5 t                totalper+=per[i][j].getper();
                break;
            }
5 X, O, \( i! c- y# Q        }
        cout<<"能达到的最大喜好度为："<<totalper<<endl;
}
! }" Q( Q4 Q- T" H4 Cvoid getorderbyper(ifo array[]){
7 k0 v! X& v  D/ i( v1 N! ?4 y" l    int max=0;
    for(int i=1;i<areanums;i++){
9 m9 D8 I+ @3 ~/ f0 w        for(int j=0;j<areanums-i;j++){
" {& r) l$ u; u7 f        if(array[i].getper()>array[max].getper()){
            max=i;}
        }
        ifo temp=array[max];
        array[max]=array[areanums-i];
* |8 s& w6 D" W# E2 r; J        array[areanums-i]=temp;
9 z" D; d% `. t% ?* l2 K        max=0;
1 A6 Z( p4 l- ]7 Y2 N& k: p    }
}

厚积薄发

代码3：
/*
4 F9 i) p" Y3 q4 T算法思路：
（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
0 N* h. j4 v- a8 Q( ?7 \再加，该人的所有喜好度设为0，
7 e; T" g) Y% I. L- o（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
(4)最后输出总喜好度。
: k# L1 S; ?1 R, O8 T*/
#include<iostream>
9 J7 ~3 Z5 r( T3 j* f4 pusing namespace std;
# g( v, r' k" b% Pint b[3][3];//M*N矩阵
4 r6 J7 E9 k  S* ^int a[3]; //区域人数上限数组
int c[3];
# x; ]" \- i- @2 P8 Dint temp[3];
2 X  `9 g  n3 W: a# O1 y# d4 tint sum=0;
0 D$ y# N4 v/ N6 W9 p1 j( Rint max_num()
2 t: p9 i( l7 J! a7 _{
  D% S7 a0 |. T( J3 Y6 Y    int max=-32767;
- _$ W) [8 \  M0 G; @; K    int x,y;
/ `; C7 `' r. p* j' ?+ Z* x    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        if(max<b[i][j]&&b[i][j]>0)
6 {& b# }  U  c2 l: f        {
            max=b[i][j];
            x=i;
' F( g! D9 f5 V            y=j;
  |% u! U$ D+ j; n3 z
        }
    }
) U) R! n" F: S7 z   
" p4 t7 }1 H% u. O, b3 a8 ]    if(a[y]>0)
    {
( e3 J& y8 i- S0 f1 M) n        c[x]=y;
        //cout<<"c["<<x<<"]="<<c[x]<<endl;
        sum+=max;//总喜好度加上添加
6 g2 K' U0 J1 ]  V/ H# a' U2 S6 M        temp[x]=max;
        a[y]--;//区域上限人数-1
    }
    for(int k=0;k<3;k++)
8 x; q0 v) z; p& T. j/ F" P- T    {
        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
    }
    return sum;
; K/ J1 y; _5 ^}
int main()
{
   
    cout<<"input 3 zone's limit:"<<endl;
! c; W, R; ]$ c- T3 u; J    for(int i=0;i<3;i++)
8 ?1 k- k' T, y  U0 {    {
2 `) @3 D6 P* d/ _! }8 I( y. ]        cin>>a[i];
/ ]! w/ J. ]& ?' V    }
  l7 @. E! W9 f  h) I    cout<<"input 3*3 actangle:"<<endl;
7 h/ ?/ Z- H! q  t9 L$ Q  \6 W8 n9 X    for(i=0;i<3;i++)
2 A* }0 s0 _1 O' ?% x' k6 u# X    for(int j=0;j<3;j++)
    {
        cin>>b[i][j];
" C0 E4 G/ G, G" d) ?5 A    }
    for(int k=0;k<3;k++)
    {
        max_num();
' N6 O, f) g+ H0 z- _) W& I( ^! m8 p    }
    //cout<<"sum="<<sum<<endl;
    cout<<"sum=";
% q- o3 K$ R4 M8 r2 ]1 @2 {    for(i=0;i<3;i++)
    {
        cout<<temp[i]<<"+";
    }
    cout<<endl;
    cout<<"reslut:"<<endl;
7 h5 A0 b7 M& S% Y- B2 T    for(i=0;i<3;i++)
    {
' k- `# V+ b# j8 N6 d# c6 V7 G        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
    }
    return 0;
}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
0 y: a8 y$ v! p0 Y: L  ~/ H数学中国社区分享快乐！
( u$ {9 \) N+ I: a- R

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.
( f: F3 {5 O$ a5 v& W. e& f

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！