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

厚积薄发

座位调整

题目描述：
) }; ^& ~, o5 E
百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。

调整的方法如下：

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

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

/ S2 S9 p: T7 n- j/ y5 J. L- o3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。
/ d8 k5 ]4 L6 l8 A+ A; L
# y0 }1 b+ Q0 i数据输入：

' S' _! Q, t+ Z% ~# D第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。

8 s8 B: y7 V* K3 K第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。
5 \* ?# c; j# w0 M* n" D% n
& q! d. m0 Y$ K紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。
0 ]0 y8 `; U  \4 K5 m
8 w" D. z6 M1 l9 [5 N# M# |答案输出：

1 M% a1 g) W1 S7 ?1 D0 K6 N! i对于每个测试数据，输出可以达到的最大的喜好程度。
( g. r  b0 }8 ^7 o8 }- ^& l0 B! c) K
* ^- [5 l* b7 R' Z( a" B输入样例

" ]6 l2 O3 X) H! h2 q, u4 D
) h# D" ?- m+ S2 j1 h- t* L/ _5 P3 3
' ?+ a+ m$ y7 h, k% t# E
1 1 1

100 50 25
2 u" V0 Q3 A" Q) \' i
100 50 25
  H4 L' @/ v7 J/ U" h7 \0 y* A; V
100 50 25
7 ?3 x0 @6 ^1 _0 K

% X$ ~& h9 _& _- w输出样例

/ D2 c- e& u" q. m7 i3 p175
, n- U8 I0 r  K( c) y3 ~! |
1 N8 |1 O# T; H* c! L* v* }$ x7 J

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

厚积薄发

. N" H: h- h+ V) p3 ^# s! F" v
#include<iostream>
& s( M6 u8 z( Cusing namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
* z; T' n/ r) G! Tint c[3];//记录某人i去的区域j
int sum=0;
- k- B+ R' `! J2 eint max_num()
0 |1 v( d$ D0 F: a4 `, Z5 ~" b% n" z{
8 s0 A4 Q7 d/ I    int max=-32767;
    int x,y;
3 a# B5 ~( d5 }2 u    for(int i=0;i<3;i++)
* }6 v! y( o( X/ o, ^  O8 ^" ^; _    for(int j=0;j<3;j++)
    {
0 m; y9 j1 j3 ?+ j5 o        if(max<b[j])
" U, `9 _% E! Z7 W) H+ ?        {
7 l) _9 C! r% `; P3 N4 i2 {# d            max=b[j];
            x=i;
            y=j;

% @+ |2 E( l( Z9 m: F        }
    }
   
    if(a[y]>0)
) C7 _. E6 {# n6 H8 F3 n    {
        c[x]=y;
        sum+=max;//总喜好度加上添加
( v( ]$ b8 q( @- ?! ?7 K( @        a[y]--;//区域上限人数-1
+ v3 l3 Q! H, S9 Y        for(int k=0;k<3;k++)
        {
% d! A& s4 X: A- P  Z8 E            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
  g" O& p0 C0 h    }
6 h: m) \4 k/ m. ]( c    else
0 N' F9 A" M& U2 D! \( G    {
9 Y: O0 n$ J# H5 E$ y& J        b[x][y]=0;
    }
   
9 F7 g0 m8 A5 X7 T* y) M    return sum;
}
int main()
{
   
2 Y: n+ f2 _$ u! j4 v    cout<<"input 3 zone's limit:"<<endl;
( ~: u$ i5 @9 [7 S' U0 V2 \' @4 T    for(int i=0;i<3;i++)
    {
        cin>>a;
    }
0 |! w! F+ R- \& O$ J$ e! [7 O- M    cout<<"input 3*3 actangle:"<<endl;
' k  ~9 n1 u6 _$ {- z    for(i=0;i<3;i++)
# Z  ], I- t6 m" k    for(int j=0;j<3;j++)
    {
        cin>>b[j];
    }
5 H; P) g$ e, D! o    for(int k=0;k<9;k++)
5 `7 \* K( r# s0 y: }/ G    {
        max_num();
    }
. ], A" u$ n$ \; ]; w9 _% ^' V   
    cout<<"sum="<<sum<<endl;
- d2 s) P! H) P* P    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
; }( m, x# g& N1 N% Z    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
1 Z3 J+ S+ D9 `( }    return 0;
7 s1 K* n/ T$ K) N' N: b}#include<iostream>
using namespace std;
% H: Y+ M% \) s, a2 z& V7 w( Oint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
int sum=0;
int max_num()
{
& \% w/ v0 `% k6 V9 [    int max=-32767;
8 f" f% b5 k5 e( q& l9 [9 H    int x,y;
* A/ ?' H2 q9 a- y6 _    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
' n" y% R# Z' H, L& L    {
        if(max<b[j])
3 V  n- J; n1 d- Z        {
            max=b[j];
' o# j9 ~4 o+ H3 x9 s$ v            x=i;
% `" u/ g; O* O  |1 {% W            y=j;
$ H" T1 F$ |( r/ K5 J
        }
    }
& U) f0 c# w9 M   
    if(a[y]>0)
3 G. {5 U- \8 m    {
' W( r9 n% E# v3 e" i- Q        c[x]=y;
0 g0 b+ K& o# e! P5 L! L* Z7 T        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
# {4 G) W: m7 U0 G6 O  a$ R        for(int k=0;k<3;k++)
$ u1 ?& X7 C! b7 y+ D        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
" [- R) K$ w1 U' O% u  ~4 Y$ O4 g- a    }
  P) q, [: ]; O4 q1 A- }+ A    else
    {
; h$ Y3 y6 I& v        b[x][y]=0;
/ [3 k3 j& F5 t) a    }
   
! O: o) w. [5 B5 M    return sum;
}
int main()
7 {- A' ?4 l! g{
: e) W7 E8 ]3 h! {8 d* T   
" p$ c/ h0 s1 l8 K0 |    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++)
( A! D% I# N0 f    {
4 Z  N6 G' p* [5 M        cin>>b[j];
    }
    for(int k=0;k<9;k++)
    {
$ @: d% l0 e$ n        max_num();
4 k; j, ]3 u# l0 z$ f* V    }
   
    cout<<"sum="<<sum<<endl;
    cout<<endl;
- w! k" f9 Q. e! n3 e) t    cout<<"reslut:"<<endl;
! ?  w% i8 i* m  e0 M    for(i=0;i<3;i++)
7 N6 {. @7 h7 _: a- K1 ?0 }    {
$ M( z' j  ]6 E/ \/ t6 h        cout<<"people "<<i<<" go to zone "<<c<<endl;
/ ]( }; [4 x# l: S& e    }
    return 0;
8 j! N1 f0 ~  E1 K}

厚积薄发

编程代码二：
% ?' ^  v" a2 ^- A#include<iostream>
# t8 }/ ?8 W- R% n#include<cstring>
  X7 y! F, E; M$ C7 o9 {3 _#include<ctime>
using namespace std;
' |5 l& T+ _2 D& {1 ]" c6 K/ E/ pclass ifo{//矩阵的元素
    int clerk;//员工号
) ], U9 i) Z- d9 R( }) ?    int area;//区域号
; I+ `" W/ [- _( w# B% M- R2 \    int per;//爱好度
public:
    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
# J1 P+ O; P# \* G( h+ M* z    int getclerk(){return clerk;}
; }! `, ?# p7 ?5 W# D    int getarea(){return area;}
/ v/ w5 @3 N+ C' s# k1 ^    int getper(){return per;}
    void setclerk(int i){clerk=i;}
& p6 u9 |- X4 [, N: N% Y, A    void setper(int p){per=p;}
    void setarea(int a){area=a;}
/ C& X! q4 B: B6 R, T+ i};
9 {, D( h/ h. z4 o8 D$ gclass area;
class clerk{
    int areanum;
    bool isin;
+ D1 `' h/ r9 O0 f. j( o    int inarea;
2 X( S& F) H8 K/ {2 Y1 e  Cpublic:
% w6 B: l2 I7 ^    void set(int num){isin=true;inarea=num;};
' U' J' r. U* f' a    void setisin(bool b=true){isin=b;}
' P8 e1 E! `; k6 O    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
' V9 I- P9 @! U};
class area{
    int num;
    int max_num;
public:
    friend void set(int);
    int getnum(){return num;}
    void setnum(int number){num=number;}
    int getmax_num(){return max_num;}
    area(int number=0){num=number;}
    int getclerk(){return num;}
    void addclerk(int ps){num++;set(ps);}
$ k8 E0 V4 r% B  h3 [* z};
void getorderbyper(ifo array[]);
9 M( X8 N% T; m9 w5 Jint areanums;
void main(){
, O5 r6 Y  G! j1 e- ]+ u    //input
. [5 n/ V) m9 }    cout<<"输入区域数：\n";
% |* t2 L8 q8 g9 E* h8 ~    int area_num;
    cin>>area_num;
2 L$ `( z; W; M8 G8 R( I  U    areanums=area_num;
    cout<<"输入员工数：\n";
    int c_num;
    cin>>c_num;
- ]* e  {. L- \. V    cout<<"依次输入每个区域能容纳的员工数:\n";
' `/ H6 |5 E/ e' Q# R' [6 ]    int *max=new int[area_num];
* E5 P# M, c6 w# s1 t# j    int nownum=c_num;
5 `* L1 a# X- G% r: s+ k+ j    while(nownum){
        for(int i=0;i<area_num;i++)
& G" S3 P# i7 }2 u        {cin>>max[i];nownum-=max[i];}
+ o- Z- ~, t9 n4 v        if(nownum>0){
            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
            nownum=c_num;
8 t5 f8 i! U4 m7 _: E. t3 Q; g+ \8 S        }
; ~' t4 T9 G: \' y& L  U1 f        else nownum=0;
& j. q' v3 |/ Q. e( h6 b9 B; c5 W    }
, j4 t1 [3 C) Q/ N! j2 H9 U7 g    cout<<"按行输入每个员工的偏好：\n";
    ifo** per=new ifo*[c_num];
- [  G# }( G% Y) N$ {: v8 n    for(int j=0;j<c_num;j++)
" |; }6 E+ O5 Z6 F4 Z& W8 w! p        per[j]=new ifo[area_num];
" o' t1 U& @* j7 V) v6 A    srand(time(0));
    for(int c=0;c<c_num;c++){
2 j9 I* f6 P( w8 c3 }: J$ C8 G        for(int a=0;a<area_num;a++)/*
        {    int p;cin>>p;per[c][a].setper(p);
3 f0 d" v  R) L            per[a][c].setarea(a);
; k0 Z, I  q$ d3 [            per[a][c].setclerk(c);
" E: U+ H' T& z" e$ A5 p2 s' x        }
        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
7 T, V' `3 B4 {9 E+ D. a7 c        {    per[c][a].setper((rand()%60)+40);
" Q' \' ~6 a0 t            cout<<per[c][a].getper()<<'\t';
        }//测试时懒得输入，故以60-100的随机数代替。
-    cout<<endl;
* M. G# |. D) V6 ?7 Y    }
8 c" B) N( ~7 _) Z" x5 p- c    //output
        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
        clerk* people=new clerk[c_num];
$ m3 O; N/ ^: N* V        area*  areas=new area[area_num];
        int totalper=0;
        for(i=0;i<c_num;i++){
            for(j=0;j<area_num;j++){
: r* J' Y2 p4 @( M* p" x4 \            if(areas[per[i][j].getarea()].getnum()<areas[per[i][j].getarea()].getmax_num())
, d. Q/ `5 K$ J, }+ |& {& S, X/ s/ W                people[i].set(per[i][j].getarea());
                people[i].setisin();
4 Q' U" e4 _' [, c; |0 D, x                int number=areas[per[i][j].getarea()].getnum();
                areas[per[i][j].getarea()].setnum(number);
                totalper+=per[i][j].getper();
8 v4 H8 J0 ~' \+ j* K0 L                break;
/ ~# A  a# @9 ?* [& a$ G% G+ h            }
& T3 D  H9 {) k* n9 n, N4 d        }
. H% f" O( M7 M3 R        cout<<"能达到的最大喜好度为："<<totalper<<endl;
0 ^+ I" `/ R& w: @8 N1 {( e}
void getorderbyper(ifo array[]){
2 U( x1 o2 ~) R% M) q$ g7 n    int max=0;
0 m& W: e  K: O  `    for(int i=1;i<areanums;i++){
        for(int j=0;j<areanums-i;j++){
        if(array[i].getper()>array[max].getper()){
            max=i;}
        }
- N+ \2 G  g# q0 x6 M& v" G        ifo temp=array[max];
        array[max]=array[areanums-i];
        array[areanums-i]=temp;
9 r, z  j( y2 l3 X: ?4 D3 t        max=0;
* }3 u2 l+ ~% G2 Y% M    }
: l' B3 ]% V0 G- |, a' i}

厚积薄发

代码3：
/*
8 Q) v  e- k. _9 g6 n0 z+ @算法思路：
. w& G8 C" v& Q8 i$ u8 I9 F（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
再加，该人的所有喜好度设为0，
' ?5 e  K0 f5 Z' t! [$ Q0 Z  v（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
$ X$ r; g# x7 h; j4 u(4)最后输出总喜好度。
2 m# ?; x- {! _7 o  C3 {*/
#include<iostream>
+ t7 ^) I: u  cusing namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
& M# j+ y1 o. A; I/ Gint c[3];
int temp[3];
% C0 k7 _& |" y8 ^4 Hint sum=0;
int max_num()
{
    int max=-32767;
* J" G9 l$ w6 p8 l; b1 N2 b" K    int x,y;
0 ], a( _, q% Y& e    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
3 S. Y" M" A' O        if(max<b[i][j]&&b[i][j]>0)
6 Y) K/ q) O+ {4 C% N4 }, C. n        {
            max=b[i][j];
7 u, u0 \6 g) D, g            x=i;
            y=j;
' j1 Q# R9 B9 W6 [9 r7 A7 ]
, I8 t. s( `4 }, n" r        }
    }
   
5 T& c+ l, g% I" z4 G# G  T1 e    if(a[y]>0)
" b2 S0 ~8 S- }% L    {
        c[x]=y;
        //cout<<"c["<<x<<"]="<<c[x]<<endl;
        sum+=max;//总喜好度加上添加
        temp[x]=max;
        a[y]--;//区域上限人数-1
    }
; |6 k) @. U" p6 O3 u, e+ h    for(int k=0;k<3;k++)
    {
        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
    }
    return sum;
( N/ k! y  d( H; t}
3 `" \: S7 Y* tint main()
4 U5 }& i2 R3 K; d5 y{
   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
    {
        cin>>a[i];
    }
    cout<<"input 3*3 actangle:"<<endl;
. j. g; }1 [5 F6 h( _4 v8 Q/ I    for(i=0;i<3;i++)
* U0 U2 H. H3 F9 x, k6 A/ X: s    for(int j=0;j<3;j++)
    {
5 g' N  ^5 }/ z; n/ Z3 c        cin>>b[i][j];
    }
    for(int k=0;k<3;k++)
    {
        max_num();
    }
    //cout<<"sum="<<sum<<endl;
0 B9 O. o* Q, J/ t    cout<<"sum=";
    for(i=0;i<3;i++)
8 W! o8 s7 d- }* E4 C% d) n" t    {
0 V2 r. p* q' h* X! N# r& ~        cout<<temp[i]<<"+";
/ Q/ F# s1 O8 ~- T    }
1 y+ S. H3 C: K% y2 ^+ [    cout<<endl;
* _( F$ g9 P9 S( c) x) t    cout<<"reslut:"<<endl;
" U2 X4 |* \8 u7 `: b) M( L    for(i=0;i<3;i++)
    {
        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
. E" o, {3 i, w$ d; S    }
# l9 K0 j: g$ G* X" i0 c" t( P( F% k    return 0;
}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
$ q$ D% `  A. d& ^6 O+ }数学中国社区分享快乐！

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.
1 _" G. F; G9 u' V2 K

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！