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

厚积薄发

座位调整

" t; ^# z5 X% l题目描述：

, Z4 v. x- ]+ i' f百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。
+ p" I$ p4 X3 ?0 n
调整的方法如下：

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

- c; J% _4 H0 b3 ?2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。
: e- E( i6 R( A6 w% h! o. v7 r
3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。
0 m# i8 L; D, m' j6 `
# G. Y; e) q" [! Y+ v. P( d数据输入：
$ H! O8 r& B. R  M! O+ S/ R7 u# h
4 a2 O( L4 m6 h; n4 z4 e第一行包含两个整数 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 个区域的喜好度。
# q( i2 L( t) ~' N( M5 L- E* y; {, p
答案输出：

* a$ N, e7 r# [8 ]3 ~对于每个测试数据，输出可以达到的最大的喜好程度。

输入样例

8 z: K6 L% \$ ?0 A3 |9 i
: e9 m2 E( \9 G0 B/ ?# i& @4 |3 3

1 1 1

3 ~3 [8 o/ ~# g9 ]) R4 r8 R100 50 25
2 a% u/ h/ S4 `6 M7 w* N
100 50 25
" G* y7 D0 {; O' n: G& c
100 50 25
/ H# d, I/ h# \, _

% p8 r- r; Y3 \) o/ G+ l
1 |) Z0 i/ G2 E0 A9 ^  D输出样例

175
- U9 n, P' G8 |5 U4 Y$ v

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

厚积薄发

#include<iostream>
using namespace std;
5 i7 _4 ]* V. l8 H" |& C# @int b[3][3];//M*N矩阵
! ^& L' K/ `2 J1 P. ^( ]# w6 Z* Jint a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
int sum=0;
int max_num()
3 J  P: d) N- q0 H6 S' B{
4 T9 N" r. ^  O0 _& T    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
- ?2 k/ o* A% L. \0 T        if(max<b[j])
        {
            max=b[j];
, b$ Z# K" y4 D; T            x=i;
            y=j;
3 \, W2 Z1 o: ~) [" ~
        }
% D- t5 o5 q3 A" C% ?" ~    }
' x: m3 {8 Z  y1 N5 Z   
    if(a[y]>0)
    {
5 Z  F+ `. @$ a" E4 y5 e        c[x]=y;
        sum+=max;//总喜好度加上添加
7 Q" `% ^% _7 m        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
7 K/ B% H! D- L, U$ W' {. X$ F        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
& ^9 a# u+ e  `& k  k! _' B) n        }
    }
  p" D6 ^1 @1 U) A6 u3 X/ z. A8 Q) {    else
: N6 n# b3 H7 {. Y0 W, V    {
        b[x][y]=0;
    }
   
    return sum;
}
. ]* v- U- q7 u3 Q$ pint main()
0 e, j. C. _4 C; n0 S{
   
9 _' L! b+ z6 [- u; l7 N. T& s    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
    {
        cin>>a;
" p; {6 N! Y( m5 [+ k& \6 p    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        cin>>b[j];
0 c; D. R! _3 D5 f0 V' {    }
5 F) u7 j( F8 i' z0 r* w+ o" o    for(int k=0;k<9;k++)
    {
2 f% D  P9 E+ ]- v, \        max_num();
    }
2 e1 w1 A5 B; u2 g   
    cout<<"sum="<<sum<<endl;
    cout<<endl;
" j+ }' L- S0 S/ B7 D    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
' V2 ]' E" s( t. N    }
    return 0;
}#include<iostream>
" }& M! v8 C) [' \. Y: l2 Wusing namespace std;
" y* A3 V3 u* `$ _/ ~5 Pint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
" c* k& a  S9 V5 y9 b0 B% ]4 h: Wint c[3];//记录某人i去的区域j
int sum=0;
0 X+ F  h% @$ f' @int max_num()
{
    int max=-32767;
3 D& `4 ?$ f% `1 F4 D1 _/ x    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
) z9 l2 l+ n4 W7 `7 r+ P7 r( Y        if(max<b[j])
6 Q, C" F  q" y$ b$ l7 j3 F% Q- P        {
3 Q! h. v' r" {& i, N4 y/ H            max=b[j];
            x=i;
            y=j;
, U* @( y9 s  |4 ^# b0 A/ q- B
        }
& p: e! q" {, B: ]    }
   
    if(a[y]>0)
9 l6 k- l! a' m. H- l6 X  N+ L    {
8 _% X! d$ ?5 z# }% j        c[x]=y;
' |' @) O7 j2 }# a  d& c) A        sum+=max;//总喜好度加上添加
% }. n1 o( D: O: E# ]        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
9 u: r; |9 w% j! o5 k        }
6 ~* i. A7 z2 T# I    }
    else
    {
* A1 r) _8 W3 p( J1 Y        b[x][y]=0;
1 `% W, V/ b- o, r    }
+ k* d. a- V  i4 S, ~. K: e  j   
, n& Y- N% b! Y* c6 t. J    return sum;
}
int main()
{
   
9 o# G/ R0 B, G( e8 c( m    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
! a7 q9 s5 I9 a: I. B3 S' k) @    {
        cin>>a;
* K5 L0 t) X) Q+ ~- t# Q5 y    }
& f9 ]7 R' v, D    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
9 R0 C1 J) O9 a0 L    for(int j=0;j<3;j++)
0 A$ Z7 [+ s* h. b1 [/ x  M    {
8 b5 j+ R- g& J8 Z* q) |        cin>>b[j];
    }
( d& S; |1 P% G' f- u; J3 R! `( r    for(int k=0;k<9;k++)
    {
5 ?% ~2 M$ Z& H: c/ q        max_num();
: S6 N7 _, i$ M! t    }
5 y; R1 d. P/ W$ p, P1 `) l   
    cout<<"sum="<<sum<<endl;
. o3 n: ~$ M( Y% B    cout<<endl;
3 ^0 \+ B$ U: F, Z    cout<<"reslut:"<<endl;
7 s  I6 M/ P  w# o2 o* c* E    for(i=0;i<3;i++)
    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
    return 0;
}

厚积薄发

编程代码二：
#include<iostream>
4 Z/ v- k% I5 h+ E* c, M#include<cstring>
6 J' m" |3 D1 k9 [% W#include<ctime>
9 l1 A+ Q3 n1 i( Z& g  R4 E5 ^using namespace std;
! _6 O& n/ j, t& _/ ^" Gclass ifo{//矩阵的元素
    int clerk;//员工号
' [: P- s. B' \+ O. w1 V    int area;//区域号
& I: m! i- x  D    int per;//爱好度
public:
    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
/ v* a7 v" y$ l8 N# n; _    int getclerk(){return clerk;}
) W6 E6 [4 i. c1 Z0 M1 q! w* t    int getarea(){return area;}
    int getper(){return per;}
    void setclerk(int i){clerk=i;}
    void setper(int p){per=p;}
    void setarea(int a){area=a;}
- {; q4 x$ f; C' o3 Q: A};
" B& H; ], S% ]9 i# i9 G& u( s) Yclass area;
( v; Z1 [! J# Z, h! Pclass clerk{
3 l6 Z7 t$ f/ ^7 p6 r+ P& t% M- c    int areanum;
    bool isin;
    int inarea;
7 ?3 ?' R* ^3 p! y4 \public:
% W3 q1 F/ _6 C6 s# F' U    void set(int num){isin=true;inarea=num;};
    void setisin(bool b=true){isin=b;}
  n/ t: _: K3 ^( t5 ^5 s8 I& v    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
};
- u# `  A$ h# b7 q8 C/ l3 \9 P9 Oclass area{
    int num;
& P3 f1 g8 `" x7 L' G: O) w; E8 y    int max_num;
public:
    friend void set(int);
7 s$ Z3 s8 P1 u$ f2 u    int getnum(){return num;}
    void setnum(int number){num=number;}
, E. x  o- p8 G" U, n    int getmax_num(){return max_num;}
0 s' O) I# q6 L    area(int number=0){num=number;}
    int getclerk(){return num;}
    void addclerk(int ps){num++;set(ps);}
3 Z+ x# H! Y! [7 r4 T# K' H2 a};
: [  C: _0 D  U6 w5 I' i5 c8 H5 Cvoid getorderbyper(ifo array[]);
- V9 i  k5 d: H' t1 f  ?int areanums;
/ u! K/ l- k  e/ y) n+ L- @void main(){
7 p" ~2 [9 h: E: b. M9 V    //input
1 ]9 u4 b/ `  J% h9 w0 d    cout<<"输入区域数：\n";
    int area_num;
% C9 G- l7 Y2 A$ q: W    cin>>area_num;
    areanums=area_num;
    cout<<"输入员工数：\n";
5 @$ |% h6 m* a; [    int c_num;
    cin>>c_num;
- q3 M6 x9 B  w3 K. z% S    cout<<"依次输入每个区域能容纳的员工数:\n";
    int *max=new int[area_num];
    int nownum=c_num;
    while(nownum){
        for(int i=0;i<area_num;i++)
1 f+ v" G- b- s# n        {cin>>max[i];nownum-=max[i];}
, L. h2 O. c) E2 x3 a0 O        if(nownum>0){
+ N0 Z& v* n$ [3 g% X6 ~( S+ O8 T            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
2 [3 B+ W" \3 L5 [            nownum=c_num;
' A/ Y$ G) W$ `& K0 f; P        }
        else nownum=0;
8 D% `( j$ ~1 ^' _    }
    cout<<"按行输入每个员工的偏好：\n";
# H% }# w2 j. L1 L5 l    ifo** per=new ifo*[c_num];
2 h' `9 N/ g1 t    for(int j=0;j<c_num;j++)
) y6 P2 B, g5 z8 d3 }        per[j]=new ifo[area_num];
    srand(time(0));
& n3 k# e% B" t/ f8 \    for(int c=0;c<c_num;c++){
5 e! V5 `: h" T7 M: v        for(int a=0;a<area_num;a++)/*
        {    int p;cin>>p;per[c][a].setper(p);
1 g4 Q) C: B& ~, \0 T% @( g            per[a][c].setarea(a);
            per[a][c].setclerk(c);
1 v3 D, y" ~3 P- T3 x        }
        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
. j* B% l4 J: S, A+ H        {    per[c][a].setper((rand()%60)+40);
2 V. u; E! o6 L- ~            cout<<per[c][a].getper()<<'\t';
        }//测试时懒得输入，故以60-100的随机数代替。
8 |& t- T- e; c2 h7 v-    cout<<endl;
    }
    //output
        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
+ {" k  `- u; W) }6 Y& c. ]5 d* p        clerk* people=new clerk[c_num];
        area*  areas=new area[area_num];
        int totalper=0;
7 h, ~! H) g6 s! x        for(i=0;i<c_num;i++){
            for(j=0;j<area_num;j++){
' g1 h' U$ M' q% e3 E: ~            if(areas[per[i][j].getarea()].getnum()<areas[per[i][j].getarea()].getmax_num())
                people[i].set(per[i][j].getarea());
                people[i].setisin();
                int number=areas[per[i][j].getarea()].getnum();
% B" x* {% r4 q8 ~1 d4 f                areas[per[i][j].getarea()].setnum(number);
* j3 X  u4 @9 b                totalper+=per[i][j].getper();
                break;
            }
  u0 k) a) Y' x        }
        cout<<"能达到的最大喜好度为："<<totalper<<endl;
% Q, S. e5 u7 t6 e}
void getorderbyper(ifo array[]){
    int max=0;
    for(int i=1;i<areanums;i++){
& v9 M1 O. e" ^$ G1 ^        for(int j=0;j<areanums-i;j++){
        if(array[i].getper()>array[max].getper()){
9 R; q$ w% s6 E% b. H            max=i;}
3 `- w4 w8 x. X6 R" ?4 t5 D: ?        }
0 l% s  M) {; u6 s        ifo temp=array[max];
$ g0 d3 D* k: D        array[max]=array[areanums-i];
        array[areanums-i]=temp;
        max=0;
3 G5 M5 ]3 W' v% M4 B- u    }
}

厚积薄发

代码3：
3 Q; v# a  e* Y# x/*
算法思路：
1 d2 e/ _3 v; F- u（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
再加，该人的所有喜好度设为0，
（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
7 W4 X$ w" U+ x; J& F（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
+ Y, w2 n3 `# P) w(4)最后输出总喜好度。
*/
) y( `& w9 g- u7 X* e: P- i#include<iostream>
) M+ R% u9 {$ c/ a9 W6 v" t) r7 Iusing namespace std;
$ J1 p" V- i3 I  i% T; o* ^int b[3][3];//M*N矩阵
  c4 U" u, C1 h0 J. [8 H  L$ oint a[3]; //区域人数上限数组
int c[3];
6 X* C' ~: u- _. Nint temp[3];
6 v9 a- n, w! s3 d5 a1 o! A# n1 Iint sum=0;
int max_num()
{
    int max=-32767;
6 [5 m+ h& _% f    int x,y;
& }9 N9 p+ V0 A$ H3 ]9 z    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        if(max<b[i][j]&&b[i][j]>0)
        {
; _: W- V. g5 l9 ?* t/ j% ]            max=b[i][j];
            x=i;
! @* o9 d$ m& m4 b3 a            y=j;
$ I  n8 b( _6 Z" N2 t& ?
        }
3 T' v( S  S3 `- e    }
+ A8 Z! d3 r! ~8 g8 v" }   
4 s4 N' q& n, @    if(a[y]>0)
. _* M# P* e- E  G    {
        c[x]=y;
8 M* c( U0 p7 H        //cout<<"c["<<x<<"]="<<c[x]<<endl;
1 F  U  f) }4 P* `        sum+=max;//总喜好度加上添加
/ L# j6 J  L; ~. y        temp[x]=max;
" z: `! r8 q! F1 t1 v- V        a[y]--;//区域上限人数-1
) x! y- N1 O( d    }
! Y; B& Q9 i, q" u' H    for(int k=0;k<3;k++)
3 i0 O% a: M2 {% h9 k5 s3 B    {
. ]# F, X8 X) U( f1 x; ?. R0 C        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
) z5 k% |1 N6 W" W: X    }
/ I2 u; z" O# q8 e. C+ z3 ^: z- P    return sum;
6 J* D# U  Y+ D  m% w! S- d}
% T5 z& ^$ Q- J0 D' O6 {$ V8 _int main()
) ~) P) v2 T( f. B9 E8 l{
   
    cout<<"input 3 zone's limit:"<<endl;
2 H7 I3 C/ n+ C* l- Z    for(int i=0;i<3;i++)
    {
. l# a+ v/ c. V1 w        cin>>a[i];
    }
. Q+ y+ y6 T3 R: X. h    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        cin>>b[i][j];
    }
    for(int k=0;k<3;k++)
/ z/ T/ |6 q1 d9 C    {
        max_num();
" U7 ?5 V; M" s! x; Z# i" ]    }
    //cout<<"sum="<<sum<<endl;
$ e- ]3 m9 e5 ^    cout<<"sum=";
    for(i=0;i<3;i++)
    {
        cout<<temp[i]<<"+";
$ I8 }0 i* a" M    }
2 B1 l2 l3 D" u2 j& g7 e& ?( r8 D    cout<<endl;
    cout<<"reslut:"<<endl;
* w8 C7 T; ?2 T' `7 W    for(i=0;i<3;i++)
7 w! ]8 l; q/ p# M0 q6 ]    {
7 M* ?" B9 F% Q9 R: A# P/ M0 q        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
( v6 S* O+ T. a$ |, c# v    }
" |  M( l- J. [/ u; y3 g    return 0;
}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
数学中国社区分享快乐！
7 z1 l/ t* y+ ^0 k

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！