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

厚积薄发

座位调整
" p/ K5 c8 L' M9 V
/ A8 I' r5 V- h; P3 R题目描述：
) J7 e5 v& H4 W1 K9 A+ C, h
' e3 S2 L) {( e2 D百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。

调整的方法如下：

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

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

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

数据输入：
! y1 X* Y5 Q; D+ s9 l/ M
% E0 O+ @" C$ v' d" R9 s第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。

% x0 ?( u+ L- T* ?" h/ O8 f第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。

紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。
" z! m. c+ b: F1 |' v: W
% @/ v: ]. t: F9 V答案输出：
- z5 g' @+ K/ @+ S9 J9 [# y% R
对于每个测试数据，输出可以达到的最大的喜好程度。

输入样例

! S$ [: C) `4 ^3 |
3 3
1 n8 ~& R: o1 o8 ?
1 1 1
" K; P- Z3 u7 r0 J# y- _
% I) c7 ?2 G, @( p) J0 d100 50 25
2 X9 k' d/ E6 X5 u& N- r4 q- T5 X
100 50 25
! T4 A9 Y' c/ p4 ^' Y
100 50 25
! ]5 |* E1 q: M* }  Y

输出样例

) A7 g6 _1 v/ t! w175

1 e& |2 Q' Q+ Q! @" ]0 @! ^. y9 W% \" I

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

厚积薄发

" l( `' a( s# h, N* q#include<iostream>
& H  h/ B" P4 j( Busing namespace std;
% V; T" u7 U; e' g* Oint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
# X, M8 [& @) Q* e% vint c[3];//记录某人i去的区域j
int sum=0;
int max_num()
{
    int max=-32767;
    int x,y;
, T0 n; x+ @) O# K* l    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
9 R% P7 v$ e( R2 q$ R3 Q5 b        if(max<b[j])
+ s8 Y. T0 v* _        {
+ n4 t( n$ V$ s! w6 Q. o, @# O! v            max=b[j];
            x=i;
+ g" }  k0 ]- l# w            y=j;

2 B) o  b9 G( s, c/ V- B        }
    }
   
    if(a[y]>0)
% L( ]" }, I9 j    {
. }/ F0 L9 |6 h; b, A! ~$ d- l        c[x]=y;
        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
0 X6 w- {3 t: R8 N; `2 x) G    }
    else
2 T& t. {& N! h& c    {
9 Z6 O/ E$ _' a  D. L  h3 @* h        b[x][y]=0;
9 }2 A7 o. B( a" M" b1 q/ t    }
   
& J3 y7 x% y, ]! o& b: _* Y# ~    return sum;
}
int main()
9 {" g4 R5 ^3 z{
   
6 B. Q; k+ C$ O* p    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
& J% I- n3 E! \/ B2 E" g    {
9 e4 E1 O* ^/ q$ s* Y        cin>>a;
1 L+ s8 ~" ]( d) J; n& ?    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
( N. {/ B( D& O. t& I9 ]8 Z& ]$ v; C    for(int j=0;j<3;j++)
    {
0 d) @$ m/ s  }& c        cin>>b[j];
: l4 p4 ^5 r* }- f    }
    for(int k=0;k<9;k++)
, n% B$ \/ j, b# B9 N, O! l0 F% S3 C    {
        max_num();
    }
4 |& _3 }3 T2 t) ~0 v8 O. H   
    cout<<"sum="<<sum<<endl;
    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
: M! Y5 Y; d1 i2 [$ ]        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
    return 0;
+ |& `; X" f2 S9 O0 s- o; F2 L}#include<iostream>
using namespace std;
1 F# ^7 k! v: S9 N9 {& k! ]int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
int sum=0;
int max_num()
, d( e# C8 K( |  E5 x! l0 P) d2 w{
    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
1 Y6 X7 f9 M- U    for(int j=0;j<3;j++)
( k3 B5 S6 s' i% [" h    {
        if(max<b[j])
        {
* e, t0 D# d2 L            max=b[j];
8 A1 _$ H( W* d- h) U) K            x=i;
3 N0 h/ @5 {  J$ l' ^            y=j;
3 U% V& n) ]$ _3 t7 G
        }
+ E, W2 C. q5 b! i. i3 f3 G: U    }
& @1 b. t0 g" i% t- G( k   
    if(a[y]>0)
: a, n$ Q  D8 L- p+ T5 A    {
0 Y# H* @6 T5 O% V' |        c[x]=y;
        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
        {
) K- j- J" s* t8 Z4 e' Q            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
) V6 u+ H2 Y4 Y7 O  u3 y9 x0 l; E    }
2 w9 N" ^( P- F/ Y0 b: M" \    else
    {
4 f0 ~( T0 o2 \1 g* e) y        b[x][y]=0;
' K9 Y9 V8 T3 u4 U5 D; h    }
" m% i7 n, ~" e  Y: G6 L   
4 I& T9 X, P! q    return sum;
}
int main()
) H7 c! L: i8 O9 E! N& \: B{
   
) W5 I& k, Y) Y7 r! [    cout<<"input 3 zone's limit:"<<endl;
3 r0 O8 ?# c& u; W+ |& [: Y    for(int i=0;i<3;i++)
    {
; }8 c, y- `! X( M5 ^        cin>>a;
6 i9 q0 D0 }, H2 {' W3 f    }
    cout<<"input 3*3 actangle:"<<endl;
+ g: J# F" w  V) W* q    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
4 X5 W* Y' U8 C  a7 c# K) V8 M5 A    {
! K  x* M. Q' }! f" ^0 ]9 U5 u        cin>>b[j];
    }
    for(int k=0;k<9;k++)
    {
! h4 G4 l% o3 _        max_num();
    }
$ W) v0 L* W6 G$ u; {# S/ G   
: t5 T) F1 x$ p+ O    cout<<"sum="<<sum<<endl;
    cout<<endl;
    cout<<"reslut:"<<endl;
/ q" W4 H0 d" O+ G$ O" y    for(i=0;i<3;i++)
, U, f8 @# U. }( X5 R. p    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
' |4 w% v7 v: a" a1 c7 |    }
" f; h( R1 W" ^    return 0;
}

厚积薄发

编程代码二：
#include<iostream>
8 o$ t6 {/ s) s) x#include<cstring>
#include<ctime>
using namespace std;
3 t! y$ m) V& u% t5 Z( V: yclass ifo{//矩阵的元素
    int clerk;//员工号
# k8 t' _9 N7 g! M+ ?( l7 i    int area;//区域号
1 I  A9 C+ C3 ~. |# R. I; Q    int per;//爱好度
public:
    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
    int getclerk(){return clerk;}
! |( P7 K7 n9 ]* l( |. h    int getarea(){return area;}
    int getper(){return per;}
    void setclerk(int i){clerk=i;}
    void setper(int p){per=p;}
+ D3 C+ O& A$ j. ^    void setarea(int a){area=a;}
0 k' e0 z+ z: Z};
class area;
% _# ^( Y( i; a2 v) ~" ~* Bclass clerk{
6 A9 P* C8 X1 d: i, Y, F( D1 v    int areanum;
. e2 c" G& Q: g$ c9 ]/ _% I( C' [    bool isin;
    int inarea;
8 Z! a8 ]7 J* V: z$ Fpublic:
    void set(int num){isin=true;inarea=num;};
, P$ }. b' x1 E3 K. y    void setisin(bool b=true){isin=b;}
    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
) S, w" I- Q% [6 a};
( `. G( h8 [! j2 J: s9 R3 c9 i' Z! P  Yclass area{
# {3 [5 W# D: n! ]    int num;
    int max_num;
- L3 K7 o% t) ]9 h% ~6 vpublic:
    friend void set(int);
( G: ~' S) A1 f, x3 X) O    int getnum(){return num;}
* O% Z! s# n7 j; |4 h5 W    void setnum(int number){num=number;}
5 G% e" ^$ c9 r" j# Z" |) N( E    int getmax_num(){return max_num;}
    area(int number=0){num=number;}
7 h. p- g1 ~8 y: Q9 l8 R- y9 f    int getclerk(){return num;}
: {( Q4 i% c# f    void addclerk(int ps){num++;set(ps);}
/ l( L* \/ w$ o) M; _1 ~3 R};
) E2 [, o" l2 k. j  Z# Y; E+ f+ t; zvoid getorderbyper(ifo array[]);
int areanums;
void main(){
; F/ x5 s0 |6 {: e( q3 @- c    //input
    cout<<"输入区域数：\n";
% A& V6 F" u  k7 Q4 e8 |7 F) L0 y    int area_num;
    cin>>area_num;
    areanums=area_num;
    cout<<"输入员工数：\n";
    int c_num;
& p' e% U: q' v) z- X5 M% y5 O    cin>>c_num;
4 {! E+ w  ~) i' T& p" e, r, x: y    cout<<"依次输入每个区域能容纳的员工数:\n";
    int *max=new int[area_num];
    int nownum=c_num;
    while(nownum){
( ]: |3 b* z9 @& l+ {1 i, l6 e2 D        for(int i=0;i<area_num;i++)
        {cin>>max[i];nownum-=max[i];}
        if(nownum>0){
& P5 X' O6 f* r1 Q+ k5 W% R            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
( b, A7 B- ]$ Y3 O- i            nownum=c_num;
        }
        else nownum=0;
9 b6 c4 l' \6 }# W& j" @; w9 j    }
  U2 d9 _  ^3 _    cout<<"按行输入每个员工的偏好：\n";
( b+ _: T' j# q- @( M! U    ifo** per=new ifo*[c_num];
2 ?0 I2 J3 ^4 U/ G    for(int j=0;j<c_num;j++)
3 |" v' k0 Y1 k4 t5 N8 I; f3 X        per[j]=new ifo[area_num];
    srand(time(0));
    for(int c=0;c<c_num;c++){
        for(int a=0;a<area_num;a++)/*
: c, @( A/ [. N4 z        {    int p;cin>>p;per[c][a].setper(p);
" d" H. |. n7 F" N6 X" @5 v7 g            per[a][c].setarea(a);
            per[a][c].setclerk(c);
; C% m( ~+ q3 O& ^+ _7 V; u7 k        }
        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
' ?  A/ M# j0 _; ?* Y        {    per[c][a].setper((rand()%60)+40);
9 V9 _) g+ B8 @" m            cout<<per[c][a].getper()<<'\t';
) E0 L/ l  ^3 ?        }//测试时懒得输入，故以60-100的随机数代替。
# z7 B4 ~' I* i8 w: @-    cout<<endl;
    }
& h' ~, N3 F- }) j    //output
' C6 a5 s6 L2 h" l7 r" a1 C        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
! {( X2 ?# K. k- r. n        clerk* people=new clerk[c_num];
        area*  areas=new area[area_num];
% P* C) e4 p  Z* z( M        int totalper=0;
        for(i=0;i<c_num;i++){
7 O3 \  j5 r8 h0 U7 ?1 M. }6 |            for(j=0;j<area_num;j++){
            if(areas[per[i][j].getarea()].getnum()<areas[per[i][j].getarea()].getmax_num())
2 k7 S2 M, O6 Y8 u$ x" k                people[i].set(per[i][j].getarea());
                people[i].setisin();
+ B4 s8 a" I3 F8 @" x                int number=areas[per[i][j].getarea()].getnum();
                areas[per[i][j].getarea()].setnum(number);
# ]1 o- c4 {  Y" E; @7 q0 ~                totalper+=per[i][j].getper();
8 @( R/ a, }. j6 \4 d, u+ f6 v                break;
            }
        }
& T& i% |* l1 {' {: ~: e        cout<<"能达到的最大喜好度为："<<totalper<<endl;
6 |9 `6 x% b$ G}
7 Y1 \+ Z2 c+ b0 H/ w. s' jvoid getorderbyper(ifo array[]){
    int max=0;
    for(int i=1;i<areanums;i++){
        for(int j=0;j<areanums-i;j++){
        if(array[i].getper()>array[max].getper()){
            max=i;}
        }
. h0 r& v& p+ M        ifo temp=array[max];
* C7 R" z1 j* e; j9 Z' j        array[max]=array[areanums-i];
        array[areanums-i]=temp;
/ ]: B: u4 [! R1 J% j" A0 r5 f6 Y        max=0;
$ j) p, M- v- z& s4 J    }
}

厚积薄发

代码3：
/*
算法思路：
（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
再加，该人的所有喜好度设为0，
! y  t$ m9 {: k% M$ \1 F! q（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
(4)最后输出总喜好度。
, t: |1 Z! {% h8 C3 T. Q8 A*/
- B% R' h: o* f7 y% p#include<iostream>
using namespace std;
! j( _( ~% Z% e( R/ ^; hint b[3][3];//M*N矩阵
5 [' t( I9 i5 H5 C/ G& q6 Wint a[3]; //区域人数上限数组
% B( [5 F+ b8 Q3 [int c[3];
; c* E; i0 A0 f; N* jint temp[3];
int sum=0;
int max_num()
{
4 S" a, U5 J" r8 X    int max=-32767;
7 R. c2 U; C- {+ s+ Y    int x,y;
0 |5 |$ B$ f% x) q$ i3 o    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
; W% [( n! W. L! J2 n% Q' c    {
! z5 |- @3 q7 ~$ l/ W, }2 a- x        if(max<b[i][j]&&b[i][j]>0)
        {
            max=b[i][j];
            x=i;
! g* p4 J7 O. i3 W) S& E            y=j;

/ F. r' S0 A. `3 Y; m! k        }
    }
0 E: u* e+ d1 @6 K6 _# ?2 n   
) h6 P" i, j& @& q$ Z7 u1 A- w9 B- E    if(a[y]>0)
0 r1 r6 q) |  r, u    {
        c[x]=y;
        //cout<<"c["<<x<<"]="<<c[x]<<endl;
        sum+=max;//总喜好度加上添加
4 A& `  n2 C. I7 W        temp[x]=max;
. n. b, O7 D  P  k        a[y]--;//区域上限人数-1
8 d. T0 X/ q6 ^+ I    }
    for(int k=0;k<3;k++)
    {
+ q4 Y% F9 z; d7 R        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
    }
2 ^$ Y* W, P3 ?    return sum;
}
6 Z- Q+ z/ U& U- y( j2 ^5 Fint main()
' Z7 R6 v2 @- Y9 k, ]8 K, R{
   
    cout<<"input 3 zone's limit:"<<endl;
' L0 T! J0 l4 ^$ D/ Z    for(int i=0;i<3;i++)
    {
        cin>>a[i];
* G6 u, Q: c% j' j    }
' t7 E: [/ \9 M    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        cin>>b[i][j];
* O0 q0 o+ |, I: `6 n$ |0 ?    }
    for(int k=0;k<3;k++)
    {
) ^; {1 V2 Q; ~, Q; |3 b        max_num();
& [; n9 v) ]* U3 H4 |+ j- K0 r& K    }
+ \5 k+ c" K( F# S+ W0 r    //cout<<"sum="<<sum<<endl;
8 H/ Y: i3 c$ W2 N, q    cout<<"sum=";
9 w0 s  M8 m: J& u    for(i=0;i<3;i++)
    {
        cout<<temp[i]<<"+";
9 w" b2 h7 f% j    }
+ e) f2 `6 m; }& R& G" p    cout<<endl;
& S' e3 I7 t) T7 C9 Y" e1 T    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
! o0 B& ]3 }; u/ x, _    }
    return 0;
  s5 B+ ]4 c; a9 u6 {! F( H& u}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
数学中国社区分享快乐！
5 m/ N* r. ~+ ~7 X2 t' `

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！