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

厚积薄发

座位调整
; y: z' F3 p% p
题目描述：
+ [, Z. _0 F9 m, ~
百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。
6 U& p6 `$ R2 x' h  P
调整的方法如下：

( Q8 \: {' I- I- P' U1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。
- R, a, e$ F" Q7 J% I; d
2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。

3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。
. D/ y: {! o, U
数据输入：
! j% T- |' L$ V% j
第一行包含两个整数 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 个区域的喜好度。

; J! u5 H  u- }  r9 q0 ^7 ^" j. k答案输出：
' z' a4 p( j! O# H
5 W# ~0 Y) l- e3 ?5 T对于每个测试数据，输出可以达到的最大的喜好程度。

! G( o: [6 ?: i4 Q# g! S输入样例

: K, U9 l% ]* b6 Y$ o3 Q. C
3 3
) s( @! p2 k* l7 B, e
. o! A. R* c* \- y1 1 1
( T, r/ ^5 [* ?% X$ _: f
* t0 E' Z4 D4 a% |- C. }, x, [9 D$ A100 50 25
1 z" B% x1 ?2 U
100 50 25
7 t* v( q! P' Q% q# {! H  G' x. h
100 50 25

* d3 B  A4 z! ?6 z/ v# a
  Y1 {( N5 q7 g6 _; A3 L输出样例

6 z' j' F. F& X7 ]' A175
4 O. }1 o' k: m& U( a$ C4 r  b' C

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

厚积薄发

3 {+ @9 {$ h0 J& m6 D8 ?; I* l5 r4 u#include<iostream>
/ [7 E2 z  W" D2 n8 i9 t: Zusing namespace std;
int b[3][3];//M*N矩阵
& e$ V/ I0 g- y3 p1 }1 s! @int a[3]; //区域人数上限数组
" k# g. I9 c# T# n; ?int c[3];//记录某人i去的区域j
int sum=0;
$ q$ i  j& D2 N2 T8 G2 zint max_num()
8 {& q4 W3 C# B{
) K6 r+ ~" k9 ~    int max=-32767;
    int x,y;
; t5 Y9 o$ w2 J    for(int i=0;i<3;i++)
/ c/ c; Q3 A7 v    for(int j=0;j<3;j++)
    {
4 v( D. G# {1 O; c3 B* h1 P        if(max<b[j])
) ]5 |6 G) L' U$ p* N, R        {
0 M: t1 h- a& R! c* r+ w            max=b[j];
, r/ J" o6 H, H( |            x=i;
$ c7 p- P& _' Q$ f            y=j;
& _8 s; E9 @: u* {' A& k# f& S
        }
    }
   
- X5 }( s& T/ x    if(a[y]>0)
    {
        c[x]=y;
        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
1 u( `5 W! C4 V5 \. |        for(int k=0;k<3;k++)
6 C" y+ @" }* e$ c+ D% U( Q        {
- _5 l6 G* X6 Y            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
9 w3 x2 }, q* H  k7 Z5 s* O8 a* K2 U        }
    }
    else
    {
- H) o, T7 q3 ~# G* D7 B: }        b[x][y]=0;
    }
   
    return sum;
}
9 @- i& Y- c6 L7 s  nint main()
6 r  y/ u& z/ e* ^! w9 t{
& Y* D4 ^) y3 p5 G5 `  v   
7 q5 f- t$ R5 p4 u6 P! P2 x; d7 i    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
    {
6 v+ E: H( j  R        cin>>a;
    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
' W* t4 d0 j% N; l    for(int j=0;j<3;j++)
$ s$ V. _8 `0 k/ H6 ?% p6 A    {
        cin>>b[j];
! Q% k7 B7 @: a6 ^4 P9 X    }
    for(int k=0;k<9;k++)
    {
* s9 v, J' l4 @& Y        max_num();
    }
   
! m) {$ r% X* N1 _& w5 h1 r9 @# O$ l: T    cout<<"sum="<<sum<<endl;
% p' t7 W$ u3 d    cout<<endl;
% y* A4 I- o$ V$ @$ J& L. V    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
/ B- J" @# C* n: Z0 d8 L    {
7 a' d9 k" Y( R' {$ a9 Q        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
    return 0;
}#include<iostream>
using namespace std;
6 Y4 Z, W! R/ F! T% N9 Bint b[3][3];//M*N矩阵
( T2 v0 c2 \( d3 Z  I" |( i6 Gint a[3]; //区域人数上限数组
: a0 ], }; {) f: H* }int c[3];//记录某人i去的区域j
int sum=0;
3 \4 S$ D! r, E6 Q2 @: \int max_num()
{
    int max=-32767;
2 L( c0 J7 d) K! d    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
+ h* w3 y1 k0 x        if(max<b[j])
. Y) s8 l8 `( x& D        {
" N% T5 Y; {3 x/ N$ F, n            max=b[j];
; s0 {3 e( R: {8 R1 E5 E9 t            x=i;
; k: u0 n  b  ^$ M$ b" s5 `# I            y=j;
5 E: t/ N6 r/ |5 d, G/ z
6 e0 P" M7 b% a% V/ e! k7 e& A  \        }
    }
   
    if(a[y]>0)
  p! e) G+ T( w9 x$ b: t$ R    {
7 E4 K# b9 e7 Z7 g6 r        c[x]=y;
        sum+=max;//总喜好度加上添加
# G. ~6 i% v3 U+ t        a[y]--;//区域上限人数-1
& p  U  {6 |6 o; y9 B        for(int k=0;k<3;k++)
$ }" q+ o- s8 h9 A0 ]        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
, y! I; n5 Z- ~% H# K2 l0 W. o        }
' b. u, Y( T8 n2 w    }
    else
    {
        b[x][y]=0;
, B5 h& J4 e! j' z; N! A2 S: H- d    }
   
7 p, m7 a& t* |  v3 l6 {: I' G3 ~    return sum;
}
! X: \' a. G4 r) m( K" g7 [int main()
{
   
6 {' H+ @! F+ A" k$ A, _    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
    {
( k* Y! z9 L+ k4 R  d        cin>>a;
    }
    cout<<"input 3*3 actangle:"<<endl;
& Z4 X$ `2 E/ J) \7 o    for(i=0;i<3;i++)
. ?; ?- W$ d" B8 t- C6 b8 X7 C0 g  @! T    for(int j=0;j<3;j++)
    {
, H. _, f7 u: l7 a% X6 R! b) d        cin>>b[j];
    }
    for(int k=0;k<9;k++)
( K' E" A* }/ _' o3 I7 l9 ^    {
& Z# D! ^* l4 c% g        max_num();
    }
% ]$ f2 D; F; v; t7 [   
  w0 B1 \  ]' E" O4 E, I/ I2 x    cout<<"sum="<<sum<<endl;
    cout<<endl;
  w* N# {9 V! o' W    cout<<"reslut:"<<endl;
, j/ }) Y9 B  k( E$ K    for(i=0;i<3;i++)
    {
  R# t3 B! c/ Y( _5 G        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
/ s6 c' x; ^5 s! D7 \- W5 }  `0 y    return 0;
}

厚积薄发

编程代码二：
#include<iostream>
0 D$ R0 ^* [5 v% j- l0 G! k#include<cstring>
& S( T( \7 Z9 t$ M#include<ctime>
using namespace std;
* |! H# b7 g" p' j, s, yclass ifo{//矩阵的元素
& ~# _; p$ E' A8 U! e( V  A. |! _- Y# b    int clerk;//员工号
    int area;//区域号
  K" j/ d( ?" ]8 o* [    int per;//爱好度
public:
0 _. B6 {; {& M! ^1 O& H    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
    int getclerk(){return clerk;}
    int getarea(){return area;}
8 T( x% y/ A7 o0 U# J; V0 `7 M    int getper(){return per;}
    void setclerk(int i){clerk=i;}
    void setper(int p){per=p;}
9 X; a3 S. m; w7 O. A+ S$ w    void setarea(int a){area=a;}
};
class area;
class clerk{
    int areanum;
    bool isin;
. h) e0 O" p5 s- h7 E$ P    int inarea;
public:
( E, W, e' l- b: r    void set(int num){isin=true;inarea=num;};
" `9 l7 ^" a. j- v    void setisin(bool b=true){isin=b;}
% c' f4 R/ g7 V    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
};
class area{
- i4 {6 G3 Z  y8 t" D3 n- R    int num;
    int max_num;
7 d& h/ X, e% x0 gpublic:
! L& h& e9 @0 J! A    friend void set(int);
  J3 q9 ^7 C' z3 d) v: g    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);}
};
0 [9 \, Y8 H% O$ P. U2 {5 Dvoid getorderbyper(ifo array[]);
) A& g! l* D6 w: x# \; l" g- R4 h5 Aint areanums;
void main(){
: s6 H) R& a  X% A    //input
( l. F9 U* d/ z  \9 Z5 g* z    cout<<"输入区域数：\n";
6 M3 p+ x- M  m1 A  o: v3 S" L2 O    int area_num;
- b2 |: Y4 r. C: U4 G    cin>>area_num;
# `- J. @" h; G: r; j    areanums=area_num;
    cout<<"输入员工数：\n";
, k* K9 x# R& j; l8 I1 [0 f    int c_num;
    cin>>c_num;
2 e8 h* u0 z0 o8 f+ h    cout<<"依次输入每个区域能容纳的员工数:\n";
: O# `) M- {$ M) Z    int *max=new int[area_num];
8 o6 D* q) _: ~& R. L+ B    int nownum=c_num;
    while(nownum){
$ i& g' z1 a' X9 J        for(int i=0;i<area_num;i++)
# m& _% L5 ]* B        {cin>>max[i];nownum-=max[i];}
        if(nownum>0){
( s" s' F6 t; [, y            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
: U# s# N% V4 a6 k$ I            nownum=c_num;
% q* F7 l% ^  Q        }
        else nownum=0;
( K8 N) k, d; I. `6 ?    }
    cout<<"按行输入每个员工的偏好：\n";
0 A) @/ \8 t6 {    ifo** per=new ifo*[c_num];
    for(int j=0;j<c_num;j++)
1 A/ z* b( p8 k) Q0 }7 n- p1 F1 U        per[j]=new ifo[area_num];
    srand(time(0));
, X) F( t! d! e0 ~    for(int c=0;c<c_num;c++){
) A9 ~" \( f; z1 ~( M  @  J        for(int a=0;a<area_num;a++)/*
0 w* h" U" M- B        {    int p;cin>>p;per[c][a].setper(p);
. r1 A2 {; l/ K4 r            per[a][c].setarea(a);
7 U+ R# F% }8 B% O7 V; W            per[a][c].setclerk(c);
        }
        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
  y5 t% L; N: T        {    per[c][a].setper((rand()%60)+40);
            cout<<per[c][a].getper()<<'\t';
9 o; b" [- {' Q7 v        }//测试时懒得输入，故以60-100的随机数代替。
# T7 J3 R- k7 V. v6 G# `% C' U* w-    cout<<endl;
    }
/ j) b# v) L0 x9 q1 u, q+ X) t1 H    //output
$ _# Y8 @' r8 m        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
        clerk* people=new clerk[c_num];
% t1 ?$ O7 j! i. }$ c9 s, Z        area*  areas=new area[area_num];
4 e& Q2 I: V+ S+ B. u+ L8 @$ a1 ]/ u        int totalper=0;
7 N. J0 M) r  H$ v  u        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());
7 ?4 k( W) k; D: v4 J0 r4 p                people[i].setisin();
                int number=areas[per[i][j].getarea()].getnum();
                areas[per[i][j].getarea()].setnum(number);
/ e  ]1 `% `$ b$ i, W# V- b                totalper+=per[i][j].getper();
                break;
5 G1 S# L: A, E6 _% T8 ?1 }; i5 G            }
# n3 _, W3 e8 I8 K4 `        }
        cout<<"能达到的最大喜好度为："<<totalper<<endl;
}
$ Y' i# |0 h) V0 E4 j2 _" S. E3 Kvoid getorderbyper(ifo array[]){
    int max=0;
    for(int i=1;i<areanums;i++){
        for(int j=0;j<areanums-i;j++){
& l+ n" }. z+ }- w        if(array[i].getper()>array[max].getper()){
            max=i;}
        }
        ifo temp=array[max];
        array[max]=array[areanums-i];
        array[areanums-i]=temp;
        max=0;
- r9 q) ]- @! Y6 J4 }    }
}

厚积薄发

代码3：
/*
算法思路：
/ c* v2 t. h' j6 U（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
' M+ a7 @: o1 W  j' a/ I" C再加，该人的所有喜好度设为0，
* J4 W9 w. V- V& x（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
+ R0 r2 e5 h9 A1 R& x$ F  a（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
, a5 V, r1 R  A+ I0 o(4)最后输出总喜好度。
- R* }0 Y# X) R, A  M/ B*/
#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
$ G# n+ o, s# u6 _- w! n4 v6 A- vint a[3]; //区域人数上限数组
7 }; }7 C# d. q$ ]  oint c[3];
: V' x$ a- }! h' x- C' |int temp[3];
/ K9 Z  h- q6 B9 J  F# Cint sum=0;
8 R# s( d+ x# Xint max_num()
6 z! l1 t- G* a" d0 T1 |{
7 K% |7 O9 E4 q- |9 d    int max=-32767;
0 G: ~; N0 u# e; q9 I5 ~    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
8 i' U& D& A. j: s4 d7 c    {
        if(max<b[i][j]&&b[i][j]>0)
0 m+ }* c" k5 \8 L% T+ g/ E        {
$ M# `8 M% g7 M# l4 x# H5 m3 J& m" s1 A            max=b[i][j];
9 Q/ e/ `+ }1 G+ p            x=i;
5 k$ H2 c' U" a- D* W+ M. o5 S            y=j;
! Y% j" H' y' _. k2 ~6 Z
        }
    }
# _& B/ H: F" H   
' a2 Y+ n' e: v1 r    if(a[y]>0)
& P; N$ o" K7 j. K" j: j* G    {
9 k5 w2 u- d3 s        c[x]=y;
1 W$ I$ C* J0 b; Q3 t: a) V        //cout<<"c["<<x<<"]="<<c[x]<<endl;
, d" S: R2 n) Y; t+ l( e; q) X        sum+=max;//总喜好度加上添加
        temp[x]=max;
        a[y]--;//区域上限人数-1
! E2 i; d' M% V8 K7 q0 D* P5 w    }
  `! B) X4 R. i    for(int k=0;k<3;k++)
2 t. d0 `, I& `8 U: _    {
        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
) X  y- M. {( T; B9 u    }
    return sum;
}
8 ~/ h7 O& d! k# s  F6 Gint main()
+ x7 r" W& A+ x" P/ Y/ K{
5 S, R$ z# N" \( s: U   
    cout<<"input 3 zone's limit:"<<endl;
6 g$ R) j) P0 H( [" v8 y# }    for(int i=0;i<3;i++)
    {
, f0 m, b+ d- {' v. \; B        cin>>a[i];
7 `. z/ T) i! v0 G; J+ g    }
    cout<<"input 3*3 actangle:"<<endl;
" w* x8 N( Q& L7 G5 M    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
' `( x# a  V) |( x0 K3 g' M        cin>>b[i][j];
" L. Q1 Y1 l, T, m, A; ^9 ]    }
! l! D7 w# S* t% J9 Y$ l, i    for(int k=0;k<3;k++)
0 y- I, }! x9 o% M5 v3 R# O    {
) P% Q8 [9 O% `& S4 g; V7 z& {        max_num();
1 Z/ k6 q+ W- `    }
) z0 Z" a8 o# E5 p3 s    //cout<<"sum="<<sum<<endl;
    cout<<"sum=";
    for(i=0;i<3;i++)
2 m. C7 V% e0 b    {
5 t; \# t" H8 \/ b1 P6 A3 I& H! M4 e, n0 q        cout<<temp[i]<<"+";
    }
    cout<<endl;
* i9 ?9 {$ ]1 C( R    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
7 T9 f; j% }1 `. r, p        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
    }
    return 0;
}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
9 e5 ~7 m9 r" C) ?数学中国社区分享快乐！

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.
1 u& ]6 ?2 ?* N! b8 b! X: k0 e; s

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！