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

厚积薄发

座位调整
' H; K8 `& S, U1 x
' G) B4 N6 k: q: `2 ?" @题目描述：

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

+ `9 T% f$ _8 e& k& Q, `1 d调整的方法如下：
* l" N7 y( O& D7 n) R( p  n0 }
/ q( R3 Q9 p  E3 W' l1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。

4 p8 [9 D7 V# y, Z( i( E2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。
8 }; Z+ A  k3 F
3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。
* H2 @& D5 ]9 t( p
! _, [: V: j9 l4 Z: x数据输入：

( h  B0 H8 R- n& t5 U8 a5 S- @; Y0 I' c, W第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。

. y9 c+ u0 r* T1 x& Q  J第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。

紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。
- C0 L7 S+ S( K3 U* h1 |7 q( x# I
* @0 |1 Q% R: B, ]答案输出：
/ ]: v4 q! G3 v) C. m/ G' z. o
对于每个测试数据，输出可以达到的最大的喜好程度。

% b# E2 h: h) I( |. v# [输入样例

3 3
5 j$ v6 [3 w& \- {0 s! U
5 S! H: U* Z4 D$ |, ~! }1 1 1
1 N) K1 g3 b5 k* ^  G' B( D. B
100 50 25
7 i& d/ D2 k& {- H
, S8 z, y+ T9 u100 50 25

100 50 25
" g) K+ {8 Q3 S# |! M0 E& R

输出样例

175

) z7 H& U! y& h7 T9 f

6 Y0 |1 }& J% X; T
数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175

厚积薄发

+ S6 u( Z0 b0 H' V0 r- ?3 _
0 f! }- d( q+ L! d& n. I- k8 z5 g#include<iostream>
using namespace std;
7 g& N5 b- i7 b- oint b[3][3];//M*N矩阵
! }& p# x% M9 ^0 R  D$ Fint a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
int sum=0;
int max_num()
{
    int max=-32767;
. ?- ~, k2 T$ N8 S) n    int x,y;
" n' X" U' c; B6 e' \$ i! @: P- O, `    for(int i=0;i<3;i++)
) t3 ?" a3 Z3 M8 d1 x    for(int j=0;j<3;j++)
0 j4 [8 P" ^+ x! L& E. r) j    {
% w+ Q) U% r2 F0 M        if(max<b[j])
' _6 c% ?: `$ d9 c  U: d        {
2 g! o9 R' F0 b/ D. h* ]: q2 j            max=b[j];
; w! r! U6 F! p2 ]! T, j8 Y            x=i;
            y=j;
- k+ [/ L- f+ v
7 C3 _4 i5 J! \- ]/ W5 P4 G% H, k$ ~4 {        }
7 v/ t, V' m, T3 U    }
# Z  N5 S, c2 Z; `0 X   
- P& d- x) \1 G* Q    if(a[y]>0)
    {
        c[x]=y;
        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
# b/ ]; d/ _5 d' Y2 }" i        {
5 P0 s: ~* }- ?* F2 n            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
    }
% I$ \- @$ x6 Z, j) @" a    else
    {
( F5 ?9 P5 h0 J* m  B: Z        b[x][y]=0;
/ T+ r8 R7 V, P+ w    }
+ G% o: Z' Q2 D0 {. J( X   
" ]# C8 m$ E2 N& y' T    return sum;
}
int main()
1 D% }2 w/ u) a2 M# ~{
* w2 B9 ~/ E4 }) a# T* R   
9 ?: B7 `' Y' u9 Y1 l' W& i( A    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
  T: e- S8 o( [5 C7 }    {
        cin>>a;
( V0 a8 a) X+ @6 [/ a5 B8 x' w8 E) w    }
    cout<<"input 3*3 actangle:"<<endl;
/ d* u, u+ @7 W' ^7 K% ]) ]    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
; D; h/ ^0 E5 `4 K    {
5 E$ {! B( k6 n* K        cin>>b[j];
: i: G8 \$ ?/ _5 @# c. c    }
    for(int k=0;k<9;k++)
    {
        max_num();
    }
   
    cout<<"sum="<<sum<<endl;
    cout<<endl;
9 S# @4 [9 ?2 g8 e% r9 b    cout<<"reslut:"<<endl;
! @: g5 b7 z) |. u% a0 Q& f1 w    for(i=0;i<3;i++)
: k" \# q( `, S: t/ G/ v  X5 k* h    {
0 j( w9 \' X* R7 F        cout<<"people "<<i<<" go to zone "<<c<<endl;
: m& L' ?$ s$ T1 i7 |: j7 e- M  M4 r    }
6 p8 ~4 c. g8 ?% r    return 0;
' B# t9 w- Y$ O* F* Z( H}#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
, O( c5 M8 D/ Pint sum=0;
$ b4 ~9 q' A0 M3 `int max_num()
. x! y* r: \! i% w{
    int max=-32767;
( x7 S6 L, R$ w    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
. {: Z; D3 W" N; d! ~, U* I# S" I$ T    {
        if(max<b[j])
2 c' t( |; z) h. _; B# `$ h; R) S        {
            max=b[j];
( U3 [5 f  t2 m9 t  T            x=i;
5 ?( h, T6 b1 u# [: V( M. {. k) w! A            y=j;

        }
    }
   
    if(a[y]>0)
. b4 w6 M+ S# T" Y7 m    {
        c[x]=y;
        sum+=max;//总喜好度加上添加
! X5 J. E/ T* [' r6 ]: u) H+ ?) F        a[y]--;//区域上限人数-1
. O6 W! y: p& A3 j( s# f$ @- ~. }        for(int k=0;k<3;k++)
        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
* j2 i7 T% z5 A8 e6 A        }
$ ^: p! B9 F7 r    }
    else
$ T  V9 v) h' E: S' j, R# J    {
        b[x][y]=0;
! g3 ^* w& R9 a  e) C: N/ Z- b    }
" L; N% T, H3 q9 B: _   
4 [1 S9 f2 K9 F# |7 `( E    return sum;
}
int main()
{
1 Y( r6 P" l% Y% [8 ^3 U   
    cout<<"input 3 zone's limit:"<<endl;
  p4 S! o( F% R& N: O) A8 d0 S3 ^1 b    for(int i=0;i<3;i++)
( r. P) f5 k  Z4 }: W  N    {
        cin>>a;
  b& C) y6 ?0 T  [' P9 I* r" b; I    }
    cout<<"input 3*3 actangle:"<<endl;
9 y, }0 J' \7 z) u9 r2 Y- T% g- {. U    for(i=0;i<3;i++)
# R' M$ o4 A5 G' l2 q$ v$ W9 R3 f' C    for(int j=0;j<3;j++)
    {
  _1 n$ _  h; W- @        cin>>b[j];
    }
    for(int k=0;k<9;k++)
4 ?7 `8 _; H. O    {
% u7 @; L; ?! K0 ?4 ?) U! P. A        max_num();
    }
) c2 m1 t' }- R. `   
" ^+ q) r+ ^$ H6 S6 f- b# E    cout<<"sum="<<sum<<endl;
" B  I/ t4 q* l& d    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
0 ~' e2 T& |0 V0 d9 ~, E        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
    return 0;
0 F6 m9 l3 s$ W% j}

厚积薄发

编程代码二：
  f" r2 ~/ ^2 g: i9 d1 d5 Y5 M/ y#include<iostream>
4 S8 p8 k' w! \; H# r# U& w#include<cstring>
+ m$ s+ B* d# p3 B& `$ t#include<ctime>
- P/ e. s/ r+ ~, \8 uusing namespace std;
class ifo{//矩阵的元素
; F+ B1 W: u' i  T! j+ T    int clerk;//员工号
9 |% i* }( E% T: ?7 z    int area;//区域号
& g# w% h2 V% l  l" b3 b* W- ]. x    int per;//爱好度
public:
    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
, A1 b; H$ E( N2 o) a( s$ I) d# i    int getclerk(){return clerk;}
    int getarea(){return area;}
0 |0 Y) P5 [2 a/ y& R( F; d3 R    int getper(){return per;}
; i' h9 A: K* b% h6 D/ E. [    void setclerk(int i){clerk=i;}
    void setper(int p){per=p;}
) p( c/ f& R9 e/ Z    void setarea(int a){area=a;}
  ^; }- }9 v7 v};
) Z7 l# j  g. R9 J. ?class area;
" w6 v! F4 y# g( oclass clerk{
    int areanum;
: N1 F" P  T0 n- ]5 N    bool isin;
$ R$ U: a" U6 e    int inarea;
5 W5 _$ r- c- {6 Kpublic:
& W" x& Q' p5 G    void set(int num){isin=true;inarea=num;};
    void setisin(bool b=true){isin=b;}
; L) r5 Z# k: B5 P7 ^    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
};
& T# f% c' w7 R/ T' x0 _3 i. @class area{
2 T0 W0 r" L+ v! ]    int num;
' v1 P' S. P% `9 @: _6 a( o    int max_num;
public:
    friend void set(int);
8 B# u2 _% F4 y& n8 Q: l! k5 `    int getnum(){return num;}
8 W* V) G' R4 B+ S  C6 x; f' D    void setnum(int number){num=number;}
    int getmax_num(){return max_num;}
6 @4 C5 {# p- |8 y& M    area(int number=0){num=number;}
    int getclerk(){return num;}
    void addclerk(int ps){num++;set(ps);}
};
" ?: W% i; ]& u7 {) tvoid getorderbyper(ifo array[]);
5 y2 z; P; Z4 G* T4 oint areanums;
void main(){
8 \3 [: W5 u* _/ S9 h. y$ B    //input
    cout<<"输入区域数：\n";
    int area_num;
    cin>>area_num;
    areanums=area_num;
    cout<<"输入员工数：\n";
    int c_num;
    cin>>c_num;
2 E7 E" T! u# E7 A5 P5 A8 R& e    cout<<"依次输入每个区域能容纳的员工数:\n";
! F- [. W4 F9 w% ^/ a    int *max=new int[area_num];
    int nownum=c_num;
    while(nownum){
        for(int i=0;i<area_num;i++)
  g" W/ p5 m8 H% q$ O4 W: E% V        {cin>>max[i];nownum-=max[i];}
( z) J) E7 s- L+ \        if(nownum>0){
            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
8 h1 a- B  o) U0 b6 Y/ H1 Y            nownum=c_num;
4 u# t3 l' q$ w. Y        }
        else nownum=0;
6 N0 B& Q. m1 A) T, k+ S- h7 B3 |    }
    cout<<"按行输入每个员工的偏好：\n";
    ifo** per=new ifo*[c_num];
" t( N) N# A, W0 W    for(int j=0;j<c_num;j++)
+ }) _$ S! h5 X        per[j]=new ifo[area_num];
    srand(time(0));
* F) Y$ W8 e9 g' t9 _0 ]6 y- Q    for(int c=0;c<c_num;c++){
        for(int a=0;a<area_num;a++)/*
. c/ |2 V9 {! r5 Z2 p+ j7 s; M        {    int p;cin>>p;per[c][a].setper(p);
6 z2 p0 z) |# J9 l! G: }7 t            per[a][c].setarea(a);
" d/ \5 h2 E! `+ ]            per[a][c].setclerk(c);
        }
        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
        {    per[c][a].setper((rand()%60)+40);
0 l8 C0 O; i' j" [            cout<<per[c][a].getper()<<'\t';
        }//测试时懒得输入，故以60-100的随机数代替。
* K5 t: k2 P" L* F- X5 h-    cout<<endl;
    }
' v& J) x2 h$ ]5 \6 V) p    //output
+ c  T- W* h* q7 O0 t1 f        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
) ~. T- Q9 P; y2 J/ m6 t5 C        clerk* people=new clerk[c_num];
        area*  areas=new area[area_num];
        int totalper=0;
        for(i=0;i<c_num;i++){
# c) `( q$ r; u            for(j=0;j<area_num;j++){
4 e3 y% W& Q& `2 R( j  m            if(areas[per[i][j].getarea()].getnum()<areas[per[i][j].getarea()].getmax_num())
: R! l2 M/ x% l; S- c* }/ S                people[i].set(per[i][j].getarea());
                people[i].setisin();
: b/ A: h) r! g; k! O6 }" G, ~                int number=areas[per[i][j].getarea()].getnum();
$ o& y0 b+ V+ `$ J                areas[per[i][j].getarea()].setnum(number);
                totalper+=per[i][j].getper();
                break;
            }
0 x3 _. q7 B! h        }
! `. F. |6 ?- \/ f% H        cout<<"能达到的最大喜好度为："<<totalper<<endl;
}
void getorderbyper(ifo array[]){
    int max=0;
    for(int i=1;i<areanums;i++){
        for(int j=0;j<areanums-i;j++){
# ^% R2 e& f3 L4 g* ]( `/ r        if(array[i].getper()>array[max].getper()){
            max=i;}
: ^$ j2 j8 ^& H/ O        }
8 x4 [0 c. E* \        ifo temp=array[max];
  q0 y. q# w9 S8 U) Q        array[max]=array[areanums-i];
        array[areanums-i]=temp;
$ V6 G/ F' h  W5 p( a) A1 H7 K) I( I        max=0;
$ f" u2 b6 g, J1 l+ F+ j, d1 M3 x" ?    }
4 B6 a; i: p2 g* ^3 j}

厚积薄发

代码3：
/*
算法思路：
0 _5 Q1 e# a- i+ ^/ m（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
再加，该人的所有喜好度设为0，
（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
/ P- G' T, g8 I( U（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
5 B; B4 [7 t1 ]$ n; |(4)最后输出总喜好度。
7 r( w  R! D: [8 e*/
#include<iostream>
. S9 N: K* q" G6 ~: ^using namespace std;
. I# C; ?" B  }& v! Q& ~# pint b[3][3];//M*N矩阵
7 J: z4 k! E: }% _int a[3]; //区域人数上限数组
6 `1 v2 `1 u, }, G& rint c[3];
) F* Q+ _, L1 E! ]int temp[3];
% j$ ~$ n2 y) J5 m- @int sum=0;
! k) H' Q6 ~& R) g: Fint max_num()
2 `: W4 f3 P3 x. ^8 |$ m9 L& F+ V{
5 t5 s/ M5 L- l& h    int max=-32767;
9 O' z: G7 o5 j- P6 [    int x,y;
    for(int i=0;i<3;i++)
- [) Q2 g1 N: }" Y; W# _8 ]4 y; D0 E    for(int j=0;j<3;j++)
6 e2 w% g4 o! I5 O; o7 s    {
( u2 t# w* E# R5 \6 q        if(max<b[i][j]&&b[i][j]>0)
        {
" Q; S) E3 T0 V( ]. ?! v0 G            max=b[i][j];
; A1 M. |! d. n            x=i;
            y=j;
& \; @6 l; ~8 c0 m( S. V( T
        }
3 `& g1 }, e( l2 a6 {& K    }
: O7 F4 T3 J# X   
    if(a[y]>0)
. [; V1 S! ?2 \7 \  ]0 R) [5 u    {
        c[x]=y;
2 A) O6 n  [5 O! L9 k        //cout<<"c["<<x<<"]="<<c[x]<<endl;
( c( c1 ]: W0 `# r& p( ]5 g& |' ?        sum+=max;//总喜好度加上添加
        temp[x]=max;
) R* C: c2 S/ l9 _4 _3 j( R3 M        a[y]--;//区域上限人数-1
    }
    for(int k=0;k<3;k++)
    {
; M9 w4 S9 U9 W: j: R: [" n        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
    }
8 |& \+ l) M9 F- J2 ?3 I( A    return sum;
}
' f# _0 T7 T/ lint main()
7 {4 L0 b0 \# K7 A{
: u$ `* [2 Y6 T8 [2 Y- {7 E  U) O   
' c/ F. v+ C' V6 b    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
) Q4 X$ g, ]3 x- B( `    {
        cin>>a[i];
  L% F. s8 s4 w# t3 u6 e    }
7 y. v, a: `% k* I    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
- E/ }2 D  t# b. f* Y    for(int j=0;j<3;j++)
9 E* F  z( R% Q" c    {
        cin>>b[i][j];
7 g0 S% b. H! |. p7 b    }
; s* O2 a( n- J    for(int k=0;k<3;k++)
% P: `/ F3 ~* T: j2 w; x* ]    {
        max_num();
    }
    //cout<<"sum="<<sum<<endl;
5 g, j' U' b  R" g1 k    cout<<"sum=";
0 r$ g& ?- L' W3 H" W! y- V' Z* Z1 v4 u    for(i=0;i<3;i++)
  S2 s/ `1 `( K& q% j, ?) n    {
9 \+ w8 B, f0 L8 ~% G        cout<<temp[i]<<"+";
    }
- f' j& }- K0 O! i/ t, ^    cout<<endl;
8 A0 w( M  a( A! P+ D* I    cout<<"reslut:"<<endl;
6 @& U+ r2 ^- S, f* o/ n    for(i=0;i<3;i++)
    {
        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
    }
; j0 i* }' h/ N4 v% V    return 0;
}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
( h2 u" t" M9 Z, E2 r, o数学中国社区分享快乐！

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！