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

厚积薄发

座位调整

# T- l0 E6 n4 @; y- R题目描述：
$ J  N% Q0 d# t, H* B
百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。

$ E; b& V" a3 d6 a! \. J4 q9 g调整的方法如下：

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

2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。
4 X2 C3 S# C, M' s; i* t1 Z
: ^5 c. V2 f' I' b9 j+ F3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。
0 l& L8 T% z* H* A
- ^! m' Q. b3 u, U, O# P# X/ T/ }' ^数据输入：

第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。

: K7 L* O" N0 Z  y0 i+ B第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。

紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。
- A) M4 C2 G- I% V: w! C, A. H
+ N( D, s! G8 V" N答案输出：
1 o* A0 Y# K# z; R8 a
对于每个测试数据，输出可以达到的最大的喜好程度。
; Q: }5 ]7 W2 c
9 O& ?3 m+ c+ `5 m输入样例

1 b( h. o2 W2 Y, C
3 3

3 m7 {5 C6 P7 E& i1 1 1
7 r  C# q( m, O
0 I; m* j$ j4 Z6 Q100 50 25

100 50 25
4 f/ k. Z# I, ]5 k
$ Y2 ]' o: U# O+ f+ F100 50 25
5 [$ x" j' Q' L' k7 S

8 B( p- d0 E1 h; N输出样例

. i! A& z/ k9 P2 W- d! t3 o
175

$ `7 @8 T+ x" H: I数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175

厚积薄发

- E/ V2 c) u6 k7 o* j
9 x0 w# K$ A& v2 t% j#include<iostream>
5 i+ l; p4 D/ N- \, l# Musing namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
int sum=0;
int max_num()
{
9 E/ ?* W. a/ z# _( v2 D    int max=-32767;
$ P1 E* h5 N- N0 Y: t7 H5 C    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
6 p1 j& ]7 u' L; ~% Y    {
8 f/ l; j$ h' @- h3 s/ j        if(max<b[j])
        {
            max=b[j];
1 r$ Z; O% J& ~$ K) b            x=i;
            y=j;

; d( S/ ?! G$ p! Z: ^5 Q        }
    }
- K. P- H- C  _: }   
2 I0 s  c. d# Z! a" B5 A    if(a[y]>0)
5 f, f* O! B; C  E  {* T) [4 }    {
        c[x]=y;
+ n' [* x( I  S: l8 @& W1 R( x- L        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
. n' W! g7 v& _* p1 ]) P        for(int k=0;k<3;k++)
- y/ U/ T, B8 A7 ]: F- ]        {
  D; N1 U/ X( ?  r7 ?' E' O            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
1 C: q: c7 O% p8 R% }" h        }
/ U) C& F% I8 v    }
    else
, H$ M& _4 i, s) C5 f    {
7 I7 R; u$ }7 _; C' w        b[x][y]=0;
; K5 x, t/ p# N% i    }
   
    return sum;
}
8 d( ?' y9 H/ jint main()
{
   
! o! U6 a: T1 m$ h9 D* L: f; e    cout<<"input 3 zone's limit:"<<endl;
% ~4 C4 U% Z# r1 E    for(int i=0;i<3;i++)
/ [" R# l/ X$ B, @* }    {
        cin>>a;
) h: a9 n' t. \  Z    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
* E1 K+ _& T: Z. K+ E    for(int j=0;j<3;j++)
    {
        cin>>b[j];
8 ?. m# F2 |9 D& k    }
* `$ R) e0 H1 B$ F7 Y    for(int k=0;k<9;k++)
    {
& j* \. a9 Q0 ]1 {: m1 T        max_num();
. @: e+ f, |; p( P; L    }
/ `! y) x/ y6 r; Z   
+ _6 Y4 w9 P% k3 K% D# T    cout<<"sum="<<sum<<endl;
+ E. b. U1 u& ^" z    cout<<endl;
    cout<<"reslut:"<<endl;
- W2 u" q/ m: G( A8 y/ Z  C    for(i=0;i<3;i++)
    {
; m% E: h. z9 n+ w5 S' d( p        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
3 \2 ?$ S% f2 Z    return 0;
}#include<iostream>
5 F# ^- e+ i$ O2 U) Y/ wusing namespace std;
8 b1 x5 t9 |6 ?: G$ v. ]# wint b[3][3];//M*N矩阵
* L% b, L* H  l7 G5 dint a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
& h3 l: Z9 f- V1 Zint sum=0;
int max_num()
{
    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
% @" `. U, _+ S* W    {
# T" C7 \6 P$ P9 y& z. y8 P        if(max<b[j])
' E9 Q8 N, _) c3 n        {
; ?6 y8 L# W5 _4 b* ~            max=b[j];
            x=i;
' L% Z/ c; Y! j7 S' n4 _* g            y=j;
6 R3 p$ J" K, x" s" a' X! O
        }
, g% j  V* t% \    }
1 j- `# H- y/ W6 z1 q: r8 `   
* q" v' ?# L, u+ ~7 {* |    if(a[y]>0)
9 _9 B  I9 x8 z5 V/ T* G; q& Y& F    {
        c[x]=y;
        sum+=max;//总喜好度加上添加
. B6 h- x. r0 G; [5 T% F8 O9 v4 O        a[y]--;//区域上限人数-1
. e' E. K& n+ H1 g( w' t' @        for(int k=0;k<3;k++)
0 V" k) O* m6 C7 n, A        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
- U9 m7 j9 O$ S) i/ `6 V: N/ u/ |        }
; i' b5 J1 z0 }; _4 P& r+ k    }
    else
    {
        b[x][y]=0;
    }
9 u9 S' d+ n% i( K/ g   
  e. }. B7 n  P* o+ Q7 @( ?. m    return sum;
' x/ @9 T3 ]! G2 }2 V3 z, r' D}
+ Y2 D/ V) }( }int main()
{
   
+ e( V0 d$ k& g0 Q+ L- \, C    cout<<"input 3 zone's limit:"<<endl;
% y( m) W+ ~6 m/ L+ U    for(int i=0;i<3;i++)
    {
        cin>>a;
    }
" z" {: a& p' o. {    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
8 A% m" u" [4 C, p    {
        cin>>b[j];
- _1 {% x$ }. ]* ?    }
+ L' q8 I  k9 q+ `    for(int k=0;k<9;k++)
    {
" d! E* J& z" E8 g# Z& P        max_num();
. Q( ~; Z8 n" s/ L1 v    }
   
% {3 Q. k/ t3 X9 _: G1 j# z  ?! y    cout<<"sum="<<sum<<endl;
    cout<<endl;
    cout<<"reslut:"<<endl;
0 Y* O' g4 G% P: e9 D2 J$ ~    for(i=0;i<3;i++)
0 g. S9 U5 m6 \" i    {
/ H, C7 _7 x4 i0 l% m/ I        cout<<"people "<<i<<" go to zone "<<c<<endl;
) X/ {  G9 G4 t1 f    }
    return 0;
}

厚积薄发

编程代码二：
#include<iostream>
6 c( G1 W2 R1 v#include<cstring>
* S7 I* Z  g5 {9 t$ G#include<ctime>
( m* S7 d, j6 t+ D. uusing namespace std;
! B; B$ c8 \$ c- \/ d* k' gclass ifo{//矩阵的元素
    int clerk;//员工号
* h5 W1 K( J6 Z2 l$ J, R, N' H    int area;//区域号
    int per;//爱好度
0 D$ ~, {! A  rpublic:
    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
    int getclerk(){return clerk;}
6 @" }( z. h) h5 w4 X    int getarea(){return area;}
    int getper(){return per;}
    void setclerk(int i){clerk=i;}
0 Q6 [/ p1 Z) g    void setper(int p){per=p;}
    void setarea(int a){area=a;}
3 o  k; p* q  ?5 k+ `3 R6 z};
class area;
! Z# u% E, h3 w1 G* bclass clerk{
    int areanum;
  G7 c' _- Z# e7 ~: e7 B    bool isin;
+ f; y* A( h4 ^2 n0 j7 z    int inarea;
public:
( j" o+ W9 [4 l+ m7 N+ d  E& j( t4 ]    void set(int num){isin=true;inarea=num;};
    void setisin(bool b=true){isin=b;}
    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
, `' J3 K; [5 x5 R4 I9 H4 G};
  H2 k/ H" K8 r# ?3 T4 t3 a% Pclass area{
4 y# D* v/ p- {, h' ~    int num;
    int max_num;
public:
    friend void set(int);
    int getnum(){return num;}
6 D$ f+ I1 i0 Y8 t% T; M/ y' a    void setnum(int number){num=number;}
. n# f  D1 `, |& X5 i    int getmax_num(){return max_num;}
6 B) z7 f) ]8 Z/ K/ [. f3 `    area(int number=0){num=number;}
    int getclerk(){return num;}
    void addclerk(int ps){num++;set(ps);}
  @" Y2 w+ y4 ^% U4 y};
! n) e# B( V1 [' U- R% O  P# avoid getorderbyper(ifo array[]);
* Y5 K8 ~( r8 q/ j0 m3 Xint areanums;
0 }! r1 a/ x' D; B% F/ W0 w! j% ?( yvoid main(){
1 H3 W3 ~3 k+ m    //input
    cout<<"输入区域数：\n";
    int area_num;
2 C5 J6 n( B" Q% l$ O    cin>>area_num;
( q# I  @) }+ P- H9 ]    areanums=area_num;
& N2 P' y2 A+ f" _    cout<<"输入员工数：\n";
    int c_num;
. m. q$ M! E1 M) k( S    cin>>c_num;
    cout<<"依次输入每个区域能容纳的员工数:\n";
    int *max=new int[area_num];
: e  i4 x/ ^$ s) l% n2 C! t    int nownum=c_num;
7 e5 k* J: I; k    while(nownum){
# {! ]% Q- I! G        for(int i=0;i<area_num;i++)
8 Q$ }$ B! z$ L& j, C5 [        {cin>>max[i];nownum-=max[i];}
) R8 t4 l! c3 @6 _* O$ W0 ^        if(nownum>0){
            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
            nownum=c_num;
- ?( b* w' @2 I# K        }
8 t3 l$ D" B# L" w4 r3 ]9 B        else nownum=0;
    }
& A9 J, l( g8 V; K. R    cout<<"按行输入每个员工的偏好：\n";
    ifo** per=new ifo*[c_num];
( |$ W& z3 t* r1 q    for(int j=0;j<c_num;j++)
        per[j]=new ifo[area_num];
1 U4 q1 ~# g. G: F0 ]    srand(time(0));
  a# \$ p1 n# V% X8 a    for(int c=0;c<c_num;c++){
# S8 C5 ]  Q/ k9 u        for(int a=0;a<area_num;a++)/*
        {    int p;cin>>p;per[c][a].setper(p);
' _: N9 ~" k, x; W2 q4 s+ x4 B3 r            per[a][c].setarea(a);
6 T1 u4 Z/ r# @. `% U. s- B9 t3 }, B            per[a][c].setclerk(c);
; Q7 f/ o) S: r" y; m; \# e        }
9 H0 C: j( T0 r+ ?: {6 N% d+ J        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
        {    per[c][a].setper((rand()%60)+40);
            cout<<per[c][a].getper()<<'\t';
        }//测试时懒得输入，故以60-100的随机数代替。
* s+ x, p5 F! }-    cout<<endl;
    }
    //output
        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
        clerk* people=new clerk[c_num];
        area*  areas=new area[area_num];
        int totalper=0;
" m2 c0 k, I! n* }6 W& O$ E        for(i=0;i<c_num;i++){
: u  K, @* x) N3 T$ U, O8 p            for(j=0;j<area_num;j++){
( f6 L$ {8 m4 P4 S5 i            if(areas[per[i][j].getarea()].getnum()<areas[per[i][j].getarea()].getmax_num())
( l% ]- ?8 k- H  p5 U                people[i].set(per[i][j].getarea());
: n7 ^+ g6 L  H                people[i].setisin();
" Y+ q5 a, X1 f2 R                int number=areas[per[i][j].getarea()].getnum();
/ L- t3 U5 a3 m. [. y( q                areas[per[i][j].getarea()].setnum(number);
                totalper+=per[i][j].getper();
5 {9 k1 i2 r, x- o: t                break;
            }
        }
5 u) D0 i0 s) L        cout<<"能达到的最大喜好度为："<<totalper<<endl;
1 ^$ I3 P# n/ C' T% f* \% ?}
void getorderbyper(ifo array[]){
    int max=0;
    for(int i=1;i<areanums;i++){
        for(int j=0;j<areanums-i;j++){
6 ?7 p- w  V9 z' K* }$ G' K1 Q- T        if(array[i].getper()>array[max].getper()){
! m2 s8 V4 U/ P' u: G( ]            max=i;}
        }
$ O$ s7 P7 Y* j3 s% s        ifo temp=array[max];
        array[max]=array[areanums-i];
. G" @2 k2 f# n        array[areanums-i]=temp;
3 H# `* H5 _/ o( P        max=0;
. t* T: k7 q9 \4 e% }1 [" |    }
' m- r5 J2 M- A% v- F9 ]}

厚积薄发

代码3：
/*
; a2 g, t, Z3 J" Y算法思路：
/ j7 e. c" o8 L4 @. g5 E; C（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
再加，该人的所有喜好度设为0，
" L$ Z7 r( A$ m（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
7 h) z- s0 W' E2 i' w$ o* n（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
(4)最后输出总喜好度。
, F2 i8 D+ F; [2 e; x*/
: x  s* D6 W0 c5 s#include<iostream>
using namespace std;
  }9 J# Y$ M2 ?( W& z( Lint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
# \+ J( B+ r1 e% c# Lint c[3];
int temp[3];
/ N* D& G" x$ d( l' ^$ k8 Sint sum=0;
int max_num()
" O% {( t7 X4 a, m{
    int max=-32767;
6 r' y6 W0 I' D, j6 Y9 h    int x,y;
    for(int i=0;i<3;i++)
6 V7 [" O# W& v4 h. v% o    for(int j=0;j<3;j++)
    {
2 h6 I& P/ w( z! \        if(max<b[i][j]&&b[i][j]>0)
! v/ H  C; ^6 b+ ~8 |        {
            max=b[i][j];
4 F' [2 ^& H; N, r. u            x=i;
7 N/ a; E) M6 r            y=j;
7 B3 V9 T$ F% U0 k2 M
2 O; d+ j, ^5 z4 @! V        }
2 f; F8 G9 y! O; S- e/ s, G    }
  S9 Q. y* m  {4 A) F8 d* c; ?, A   
( C# {/ S+ x$ ?1 n  b% `8 v    if(a[y]>0)
5 P: m1 P- ]/ j! W  ~2 \2 z    {
        c[x]=y;
        //cout<<"c["<<x<<"]="<<c[x]<<endl;
        sum+=max;//总喜好度加上添加
* ?/ T9 x; t% s1 w# A        temp[x]=max;
; l8 _3 c  ?0 p( t% U( ^" Q6 d        a[y]--;//区域上限人数-1
, q% q: t6 Y" `% X8 e  |    }
    for(int k=0;k<3;k++)
* l( `9 o0 }" L- c    {
2 j6 `. U' Z! F7 y2 r) `        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
    }
    return sum;
}
3 |9 T' m+ E2 B4 M( Xint main()
{
  ~! f2 b. c% C  N   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
    {
        cin>>a[i];
8 ?- V  d% S/ b" Q$ y    }
$ J8 n0 \- {9 |) {) G, |    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        cin>>b[i][j];
3 ~, I! f" _. D" A' S: x, c1 {    }
    for(int k=0;k<3;k++)
* N) K, F) T1 {! t5 Y    {
4 c2 z5 u+ t8 Z        max_num();
    }
    //cout<<"sum="<<sum<<endl;
2 H# T4 t1 m( G5 a- H    cout<<"sum=";
5 b% Y6 @) |- n- U4 k, `/ K    for(i=0;i<3;i++)
; p" S: h+ w3 X0 U    {
        cout<<temp[i]<<"+";
    }
6 _- {3 D- T+ O8 O, d    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
+ g/ S) \" ]  O' C2 b    {
, ~/ q3 M2 a! x! A  f        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
    }
    return 0;
}

葉_浅浅

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

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.
7 F6 _: J, i6 {6 w% S

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！