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

厚积薄发

座位调整

$ o% f1 R) J$ O8 E* O3 w5 ^0 v2 k题目描述：

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

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

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

  r' v3 X) U+ _9 B9 x  ?' n* A3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。

数据输入：

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

答案输出：

对于每个测试数据，输出可以达到的最大的喜好程度。

输入样例

" V* S4 n7 H  |3 A2 F" ^3 3
7 m/ l+ G0 F& b6 J
: X% Q) q+ m% D. P2 Y$ @6 C1 a1 1 1
1 W9 b  J4 e1 H9 i1 N- f0 E
100 50 25
0 ~8 O* T6 o' J( K, W
# M: I- O" d7 W% J& I! I100 50 25

100 50 25
5 Q5 ?8 P" H0 R" U

0 b5 u! c: a2 Y" ?( U) i1 a) p
; K3 v+ z: u( O- T! T* y输出样例

8 A  [0 ~3 j6 v! Y% B
0 e- ?7 X, C" F5 f# k3 ?8 g175
2 {! T7 S; F; Z& a

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

厚积薄发

9 E5 P, {0 |3 G9 ~( l#include<iostream>
9 n' _" f; l" A% g# O- u+ a5 R& tusing namespace std;
int b[3][3];//M*N矩阵
. w7 j- l+ \- x/ `% t) bint a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
int sum=0;
int max_num()
{
    int max=-32767;
' A, E' _; T; q* Q' p5 _    int x,y;
& y# M$ S  l8 Y7 D  V    for(int i=0;i<3;i++)
( W$ f8 o# J6 b) }7 ?& @. W5 a7 f$ w    for(int j=0;j<3;j++)
/ L: I6 h' l8 h    {
        if(max<b[j])
: B* v3 }4 H  I6 M. H% d        {
            max=b[j];
            x=i;
            y=j;

        }
    }
   
    if(a[y]>0)
( `4 t  s; g- G; A( H4 W! Y! l    {
        c[x]=y;
1 D, f& i4 ]+ n% _# y# r+ x        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
/ v+ b8 M3 d: t6 a6 Q  \+ X        for(int k=0;k<3;k++)
- i0 a" r! S) l& Q1 @, X4 V/ n        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
    }
9 b3 ^- u3 K8 K- m1 y    else
    {
2 _' ~. t/ j. g7 U5 u' Q* i# y        b[x][y]=0;
. I( ~( [% e& T5 A% [! Y* D! o    }
   
    return sum;
}
int main()
! j5 U' k" u1 J. a4 Y{
   
3 H, |9 c4 s! M2 m    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
) I* H/ z' A% E! W    {
        cin>>a;
    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
( _( E4 @, y- y4 K4 X    for(int j=0;j<3;j++)
) C& V% B1 h, r+ Z8 q) J1 `- ^4 D! `    {
        cin>>b[j];
    }
    for(int k=0;k<9;k++)
    {
. ]+ a$ M: b8 v" F( x! V        max_num();
    }
   
    cout<<"sum="<<sum<<endl;
6 h7 M/ w7 w: c1 H2 _- s; O# Q% H    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
6 y3 f2 r& M+ E3 m1 H. A0 Z        cout<<"people "<<i<<" go to zone "<<c<<endl;
2 s# }3 ]) v, O( L- A    }
    return 0;
}#include<iostream>
. P# M1 G) l' w  Z0 Z( l& c/ _7 c4 Musing namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
5 }( A4 Z/ k# h7 Vint c[3];//记录某人i去的区域j
, `0 e2 \! q- Tint sum=0;
$ K# F8 K# g3 fint max_num()
7 ], [( z# |' W! m' c5 R{
    int max=-32767;
    int x,y;
& [$ P7 \# r! I1 b0 v. C5 r    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
# S( X7 a6 `& v% P  U  \        if(max<b[j])
7 w5 R) ?0 R  z1 J3 E: M/ h        {
, M" _# n& [  Z4 F% }" q. C- R/ c            max=b[j];
            x=i;
  _+ u: \! \& \7 @/ Y- O            y=j;
  ?! }7 Z. Z9 k  g- b/ r
        }
    }
2 P5 P7 W0 [. w& l   
    if(a[y]>0)
    {
( k. ]5 n, O* a! y5 W        c[x]=y;
        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
. ~. {. W# ]  n1 H        }
6 ~" w0 Q1 s8 B: @' [    }
( n1 Z. s. r5 m+ p* q- P+ ^# W. ]    else
7 J% x# P7 R4 R; Y3 I# ]    {
) Y$ U: x6 L, U        b[x][y]=0;
$ f0 b4 t6 V, y    }
4 q2 g6 L0 ^9 a. x   
2 _# C7 x; \) A' n# q    return sum;
}
% u+ M7 v" [2 ~: Hint main()
{
   
    cout<<"input 3 zone's limit:"<<endl;
( N: _$ c( E; O- Z3 ]    for(int i=0;i<3;i++)
    {
7 @$ S/ b1 E: w" x2 Z# u% O        cin>>a;
5 w% R# G  X- z; w! z9 N& T    }
    cout<<"input 3*3 actangle:"<<endl;
6 s3 w% v$ n) W6 m    for(i=0;i<3;i++)
! @9 V7 f% b4 d0 E    for(int j=0;j<3;j++)
" {6 m  u% ?# F; c+ c. ^! B    {
- F0 {; t8 b, }: I! J        cin>>b[j];
: N& N4 _: Z5 Q: U: H3 R+ y5 w/ _    }
    for(int k=0;k<9;k++)
% ^1 M7 J9 O3 N# K7 o1 V* k. g8 H    {
        max_num();
) T9 [6 _+ W' [$ X2 k# z" k. w# @/ C    }
3 {: n+ }6 q& C& H* A2 A) x$ ~2 u- g6 n) F   
0 x, Q3 a; c6 {* N, e  o    cout<<"sum="<<sum<<endl;
    cout<<endl;
    cout<<"reslut:"<<endl;
: g5 a) @5 I! R& v. }# Q    for(i=0;i<3;i++)
    {
  O/ T9 X2 Q4 ?3 r, E% g; ?* J        cout<<"people "<<i<<" go to zone "<<c<<endl;
9 |3 `8 P* [  V( E    }
    return 0;
0 k0 _3 ~1 j& H, z* R: ?}

厚积薄发

编程代码二：
#include<iostream>
#include<cstring>
+ p* s3 A! ?) E5 T* y: q6 d#include<ctime>
0 ?+ n$ v  V/ r3 T+ M- yusing namespace std;
, o# h! a0 m7 x3 Pclass ifo{//矩阵的元素
    int clerk;//员工号
    int area;//区域号
$ X: `$ K0 t' ~0 ?$ W    int per;//爱好度
/ ^  e) j' t3 opublic:
    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
    int getclerk(){return clerk;}
9 E  m8 U7 s! d/ r  w* n) N    int getarea(){return area;}
( Y2 y; B  W: G) g& p( P7 n    int getper(){return per;}
4 b. j8 }  J( L    void setclerk(int i){clerk=i;}
6 V, r- @) s# L( A    void setper(int p){per=p;}
, @# W& h0 S4 ~6 y4 f    void setarea(int a){area=a;}
};
& `2 c* n. X. A7 Q( E9 f, Bclass area;
class clerk{
, x, ~/ x5 t3 O* p1 t, g    int areanum;
. n& I: M/ A/ k# ~, R    bool isin;
    int inarea;
public:
& b5 W1 ?+ ]$ y    void set(int num){isin=true;inarea=num;};
- n$ P* H! |8 A/ K( q( T    void setisin(bool b=true){isin=b;}
3 |7 o0 S& w2 M    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
};
2 a" v' q: l1 Iclass area{
- g: |3 w, U& H" }+ s: ~    int num;
: w  ^7 p* V- A5 a' u    int max_num;
" j1 [9 B6 {, W/ d$ Fpublic:
. k1 W! Z6 i( O) }: r1 L+ w    friend void set(int);
: F2 v" J( Y( H, Q" p+ r1 _    int getnum(){return num;}
    void setnum(int number){num=number;}
    int getmax_num(){return max_num;}
! e6 \: x! y+ p1 f. g) S, u    area(int number=0){num=number;}
    int getclerk(){return num;}
    void addclerk(int ps){num++;set(ps);}
};
$ r) q# O8 Y& u" C; Cvoid getorderbyper(ifo array[]);
! @0 w$ v) L0 ^int areanums;
3 }+ ?- \4 l2 ^, x  i' ~void main(){
) s: f1 j# l% ~6 X0 {/ [6 I0 k6 ?    //input
    cout<<"输入区域数：\n";
  [4 [* Z. ?. \8 Y5 S, d    int area_num;
& D  Y; T0 U9 _. i4 o8 }    cin>>area_num;
+ M1 ]7 C/ Y$ m: t4 z+ n    areanums=area_num;
* B. N  H3 f/ \7 [) J! T4 g/ S    cout<<"输入员工数：\n";
    int c_num;
    cin>>c_num;
    cout<<"依次输入每个区域能容纳的员工数:\n";
    int *max=new int[area_num];
    int nownum=c_num;
    while(nownum){
        for(int i=0;i<area_num;i++)
        {cin>>max[i];nownum-=max[i];}
) v( b/ w: Y& ~; W4 v. E        if(nownum>0){
  E3 [" [( v; t" Z0 z' Z            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
* j; j$ P( A! k. k- [            nownum=c_num;
        }
9 V, {7 ]7 @* I8 o' G3 E1 ]- v  S        else nownum=0;
7 E0 Q/ Q5 Q1 J& s# g    }
+ f' f# ~% \9 l& T5 A    cout<<"按行输入每个员工的偏好：\n";
    ifo** per=new ifo*[c_num];
! g5 C; R7 R" O9 G, z+ |    for(int j=0;j<c_num;j++)
; e  ?4 L* U  Z, [        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++)/*
        {    int p;cin>>p;per[c][a].setper(p);
            per[a][c].setarea(a);
6 T5 D  X: `/ K            per[a][c].setclerk(c);
        }
$ y( X" Y1 R. L3 R* C        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
        {    per[c][a].setper((rand()%60)+40);
( s5 A0 P7 I) l8 C            cout<<per[c][a].getper()<<'\t';
        }//测试时懒得输入，故以60-100的随机数代替。
; R7 j( [" f% l6 f$ M-    cout<<endl;
    }
3 p, q, P* j2 l+ L5 d" w5 V    //output
        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
' A4 H" }/ q- Z: h        clerk* people=new clerk[c_num];
        area*  areas=new area[area_num];
        int totalper=0;
        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());
" _" Y) r- l. C                people[i].setisin();
                int number=areas[per[i][j].getarea()].getnum();
: x" d9 s  a. u# j  _                areas[per[i][j].getarea()].setnum(number);
                totalper+=per[i][j].getper();
: |# j  P7 j/ A& o; `; r3 t3 r                break;
' D* N' h8 I' r; |7 M            }
        }
0 n. t) X: l/ Z. P2 e; @3 x        cout<<"能达到的最大喜好度为："<<totalper<<endl;
8 k3 t" J- `* x' a}
void getorderbyper(ifo array[]){
3 M! }4 s0 u) J# ^5 W  I    int max=0;
    for(int i=1;i<areanums;i++){
        for(int j=0;j<areanums-i;j++){
3 B" E! h! a' c$ ^        if(array[i].getper()>array[max].getper()){
            max=i;}
5 D! a$ r' S. V) X) X3 ~% c2 Y        }
        ifo temp=array[max];
        array[max]=array[areanums-i];
        array[areanums-i]=temp;
        max=0;
    }
}

厚积薄发

代码3：
1 p4 l; n' `9 Q6 I- ~$ `( B/*
算法思路：
（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
再加，该人的所有喜好度设为0，
（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
(4)最后输出总喜好度。
*/
( h* d+ v/ k) b#include<iostream>
7 g9 d+ w2 _% M' r; Iusing namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];
int temp[3];
7 S$ W+ {. }; [/ @9 Sint sum=0;
/ W3 Z, w/ u+ p% j8 Aint max_num()
' k& T: g6 g: K# U{
" ]5 u; ]' W) s; P7 R    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
8 d. g0 J) @' h    for(int j=0;j<3;j++)
    {
; T1 H# [0 r6 p3 V1 w        if(max<b[i][j]&&b[i][j]>0)
  n. Q+ q( |, Q/ q8 [. y        {
( A4 M8 e, M" G/ M            max=b[i][j];
+ A0 X" Y* o! ^& m            x=i;
7 s3 c- R1 L3 t' j6 U. y' x            y=j;
4 w# ?3 g' B7 r+ S8 q
5 q3 ]7 S3 n- Y! K        }
    }
+ _% o2 y& [: m8 h5 P- `! g   
2 V5 b& e4 S( L) Y    if(a[y]>0)
% e# z, ?4 c- k: m' U, P& E5 a: Z    {
1 K4 W- a) a& \+ ^        c[x]=y;
        //cout<<"c["<<x<<"]="<<c[x]<<endl;
6 }' N4 h2 T8 \: w; j: s        sum+=max;//总喜好度加上添加
* p$ ?% n1 x1 I  f, u7 X( l        temp[x]=max;
        a[y]--;//区域上限人数-1
  s5 Y4 I; ], ^% U1 ^4 k6 `2 G7 i    }
: y9 \' o" T4 E    for(int k=0;k<3;k++)
9 U& c$ [3 \3 u9 S) [    {
' }2 o, L# Z1 I* {7 v        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
! s+ O3 u( ?9 U' D' O# }  M. g    }
    return sum;
2 z0 ^5 z$ I+ a- r1 C}
2 N) X. p0 J" }: h' l* Pint main()
2 W/ c6 c  T) @2 F9 S{
   
    cout<<"input 3 zone's limit:"<<endl;
/ V$ w7 C2 ~- R1 S* Z    for(int i=0;i<3;i++)
    {
        cin>>a[i];
9 ^% m7 _- a. `7 K; o4 R. z    }
    cout<<"input 3*3 actangle:"<<endl;
  O, X7 O" R( G6 o! _' r0 |    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
: l0 A! Q7 O4 A$ U" [        cin>>b[i][j];
- G7 y3 D: s" l7 ^  {+ y    }
' f& [/ g9 v3 g4 z    for(int k=0;k<3;k++)
    {
/ N+ l. V  X) ?/ b) r% f        max_num();
    }
    //cout<<"sum="<<sum<<endl;
1 B! Z! w/ d5 B+ z- A  J    cout<<"sum=";
    for(i=0;i<3;i++)
: t/ ^2 L5 M- z1 ]/ u: V    {
        cout<<temp[i]<<"+";
$ j# V  j; G; d    }
    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
& Y- j: |6 Z- n& y' Q6 q1 P    {
: W2 Z- X, V  b2 z1 T: w) n        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
    }
    return 0;
0 T" a2 p7 K# V( `* F  b; i}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
数学中国社区分享快乐！

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.
: N- x- G8 k. T' J6 N  u5 I0 b

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！