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

厚积薄发

座位调整

- D, j5 H$ x0 y1 p题目描述：

% T- N5 `2 M2 \百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。
8 s: ]; p  `, T" x2 T
调整的方法如下：
6 W: F% M& z. j) _, D- I' x6 n
& d8 ?; r1 K8 b2 e) v1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。
4 I: O$ J3 Y, r$ E
2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。
8 S# o- o+ Z) c% T! M. I' I
+ B) T  X6 G4 x; J9 ~& s3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。
# y  U: N6 H+ ^5 n. O' J
数据输入：

1 H+ P/ t6 i; P9 s  a4 q' \* |$ _第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。
! {2 g  M1 ]1 B
第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。

3 a; E. }) E  z" h8 R( N( N5 Z紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。
  ]# P, N; F2 |
! {1 V3 D2 e" ?# o" R答案输出：

对于每个测试数据，输出可以达到的最大的喜好程度。
: D) d- Z; Z! @, H
$ o5 K& p. a+ E. b1 z- P0 ~输入样例

1 u" y+ @, L) s3 t" J3 3

% I/ K, e% @- `" A$ B+ u( |1 1 1

8 z$ L/ U. q3 ^! `- y8 N5 e100 50 25

7 B( i' r7 C* [- D( D! E) E100 50 25
- v  d, S+ u& `- W
- D8 R+ f! |, Q" n100 50 25

: [0 U3 y6 Y' T" ^! b, b
! Z% N$ \3 a% y8 x! G: T输出样例

175

. J4 ?* N- k. H+ X0 J! w

& I2 ~  T4 w/ C: n& F  \
数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175

厚积薄发

* r4 s/ X* I" s1 Q2 b8 C7 T
# l/ M8 P" W! _7 R" h#include<iostream>
using namespace std;
, Q% V& o$ |; K' ~5 q' a* _# b- Wint b[3][3];//M*N矩阵
6 I! c2 g/ p' Q9 o7 s( i8 C8 l  Kint a[3]; //区域人数上限数组
" i# K) Q( |/ x) C; v( {0 t; x6 Zint c[3];//记录某人i去的区域j
int sum=0;
int max_num()
' x( \: }2 l7 O0 p+ Z  d: B) G{
8 f$ U# ]- U$ f* `: H9 y; w# ]( j    int max=-32767;
. z. c# o8 t. j# _( V    int x,y;
    for(int i=0;i<3;i++)
0 v6 v7 z' V; r* ~1 v6 L    for(int j=0;j<3;j++)
    {
! B3 H2 y8 {: Z        if(max<b[j])
        {
            max=b[j];
            x=i;
            y=j;
$ w- A  ?0 Q9 v; T
        }
    }
1 a; C5 H0 l1 {( z% I0 w+ F! Z   
    if(a[y]>0)
    {
        c[x]=y;
2 [+ l, _3 A) r* s: u        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
        {
5 }$ W, ^* p8 T4 P2 _2 x' i            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
9 U1 }1 K- M- G3 c        }
6 i- I5 O4 z& F5 h' J! v+ r8 I  I3 {" O    }
    else
    {
        b[x][y]=0;
. r  W- V6 N9 ^+ C+ k; y1 u    }
   
    return sum;
}
int main()
$ k$ U5 ~! i- a; j' }% W% m{
$ `5 t8 m/ ?- m% {  l2 ^   
3 C0 F+ c; K2 x& s8 o' Q8 g8 `- [3 B    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
    {
        cin>>a;
  G1 p  m4 E. U3 n, B+ n! ^    }
    cout<<"input 3*3 actangle:"<<endl;
. \6 J1 B; p5 T  _$ Y3 R    for(i=0;i<3;i++)
. J* W7 R6 M1 V& @2 ]' g7 q1 i    for(int j=0;j<3;j++)
    {
9 m1 G/ I9 h/ ]# H* ^0 Y: Y        cin>>b[j];
    }
6 p0 _- K0 A: {6 W    for(int k=0;k<9;k++)
( M4 {/ @, M; Y) k4 A1 F) Y0 [2 |    {
4 {# D; I$ B3 X9 D% H& Y        max_num();
2 ?4 ^# m% J8 ?$ f. w$ m3 n    }
   
    cout<<"sum="<<sum<<endl;
- H1 B  ^0 w* n3 L: R8 E# _0 L  y    cout<<endl;
    cout<<"reslut:"<<endl;
5 G; T; S! l+ }: l8 l    for(i=0;i<3;i++)
5 `9 t( V/ F' w! x% J) u. \" y+ V) b3 T    {
7 ~0 C# a0 K) B2 [" W) P+ W+ u        cout<<"people "<<i<<" go to zone "<<c<<endl;
. ^7 ?; R& l1 K3 Y3 X) b# i    }
  @+ J( J: I4 t" _! n    return 0;
}#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
+ |5 M, N/ J# ^int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
+ V! o; j4 M$ N+ _% _: x) z2 j) Lint sum=0;
$ \) Z; g9 L& g& b6 W& mint max_num()
{
4 `/ u# s: R: s) S/ V; l    int max=-32767;
& _) U7 ]6 C& c' V8 b    int x,y;
+ H1 F* K& f: n" u$ i    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
' w# }: c; Q  @  B    {
1 b9 z- ~; Q5 _: L5 g; T, i% A        if(max<b[j])
        {
* q. y# Q' P4 H5 W$ ^* ?3 M" |            max=b[j];
            x=i;
            y=j;

        }
+ A, l/ b; |8 D1 e6 J    }
   
    if(a[y]>0)
    {
        c[x]=y;
  g) |# q; v4 j  y" c! \        sum+=max;//总喜好度加上添加
: V# s  o! i4 W        a[y]--;//区域上限人数-1
$ Q  }3 y9 Q9 j6 d        for(int k=0;k<3;k++)
        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
' o( b- `/ u% i        }
) J9 @$ A0 P( ?  P5 Y    }
    else
    {
        b[x][y]=0;
- \0 f  Z" K5 ~. n! k# ~8 U    }
% f, N7 k4 Q/ T9 O% Y   
6 q0 d0 u' E" a) O, t* Q, K3 }' P    return sum;
2 F3 i: J7 N! c% j) D9 Y}
int main()
- @5 @$ r) a  m' l8 a1 R$ N& F{
   
# F7 ~" o) r- G+ c5 h1 Y. l    cout<<"input 3 zone's limit:"<<endl;
8 W2 e9 U/ T% M3 v3 ?7 u    for(int i=0;i<3;i++)
! ~# ]+ k! S  L6 @1 j    {
" [. i* }/ g3 p0 D% I        cin>>a;
! O4 W6 |9 G* i% b    }
    cout<<"input 3*3 actangle:"<<endl;
) j7 r# h7 e% n  p' _0 y    for(i=0;i<3;i++)
( v- Y' z- E& R& w- P+ J, I, X    for(int j=0;j<3;j++)
    {
        cin>>b[j];
7 g2 A8 y1 I0 V. S/ c& n    }
    for(int k=0;k<9;k++)
    {
        max_num();
  v0 e' M1 K9 y4 l9 T9 b    }
   
' d9 G  R# N1 T$ P; v    cout<<"sum="<<sum<<endl;
    cout<<endl;
' \# X3 v: c1 t* Z1 C8 Q) k% ^    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
0 j- k6 F, L& k8 C* i% ^    {
  c; v' u6 p; n3 [2 d- m/ y        cout<<"people "<<i<<" go to zone "<<c<<endl;
* n6 }( o+ P# u    }
    return 0;
! r/ G6 H. [1 _6 u8 i9 m: L}

厚积薄发

编程代码二：
  w! {2 a1 K$ M3 e#include<iostream>
7 ^+ T: d/ j/ k& F. y8 H/ g#include<cstring>
#include<ctime>
1 Y7 H# c' T( Q8 h: Rusing namespace std;
class ifo{//矩阵的元素
    int clerk;//员工号
    int area;//区域号
  x4 M( B# F4 r; [/ Y4 W    int per;//爱好度
public:
# M' _( c+ h2 {- l* X/ O5 x    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
+ a  [3 B% r( c8 {7 O4 F    int getclerk(){return clerk;}
    int getarea(){return area;}
    int getper(){return per;}
    void setclerk(int i){clerk=i;}
    void setper(int p){per=p;}
3 k& Q. J/ o4 l- }    void setarea(int a){area=a;}
3 c0 T9 F! l9 Z/ V! @/ [6 {};
. @- p! r0 Y$ k9 m: ]/ j5 b/ I5 qclass area;
3 J. _3 c3 r) B# z; I6 f% i$ Rclass clerk{
: t+ G! Q8 F+ s4 Q5 b/ X) y3 N    int areanum;
! ]: k8 I+ b* i+ C$ l2 }    bool isin;
    int inarea;
* T" x+ t# H5 F% w' Ipublic:
1 o  S9 ^, |( O9 O( g/ `: M    void set(int num){isin=true;inarea=num;};
. Z9 ~) {3 c  b1 M& Z& a' d8 {+ z    void setisin(bool b=true){isin=b;}
    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
) I) [' X( N+ ~( f- d9 A. E7 E: c};
class area{
* K+ f( u. {# ~" X4 s# h3 y    int num;
3 Z7 i  p' Q* m8 y8 J    int max_num;
public:
( @. F9 q+ u0 s    friend void set(int);
& r- w' v! q  w    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;}
6 w5 E0 i5 M1 c6 `0 N0 H) d    void addclerk(int ps){num++;set(ps);}
, H/ a2 s4 Z+ U. {& ^5 J' f};
4 E; z1 V5 g9 _$ L0 N9 q$ h# @# ?) hvoid getorderbyper(ifo array[]);
int areanums;
! ^% V5 ?4 M3 h2 Fvoid main(){
    //input
% V) d& ^! L2 j+ N; i4 P0 P    cout<<"输入区域数：\n";
1 F; W2 U( Y/ l; m6 @    int area_num;
    cin>>area_num;
    areanums=area_num;
1 {9 y9 H7 m) P0 w) c    cout<<"输入员工数：\n";
7 {6 Z1 _1 k2 d8 z! N( f. D    int c_num;
+ {, u9 G. M( u+ X    cin>>c_num;
    cout<<"依次输入每个区域能容纳的员工数:\n";
& A8 `! ~" P0 i- h* M    int *max=new int[area_num];
  N& Z$ _) W$ m! F$ c( g5 @    int nownum=c_num;
    while(nownum){
        for(int i=0;i<area_num;i++)
        {cin>>max[i];nownum-=max[i];}
        if(nownum>0){
            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
            nownum=c_num;
2 }& r1 @0 c- l$ b/ g1 A  |        }
        else nownum=0;
/ q) ^: d. w9 o9 l    }
    cout<<"按行输入每个员工的偏好：\n";
" c, A. P' p" H7 s* s' P  K    ifo** per=new ifo*[c_num];
% R: b8 b( B$ G6 P9 r8 N    for(int j=0;j<c_num;j++)
        per[j]=new ifo[area_num];
    srand(time(0));
, A; S, I1 x; K, B' e9 ~) K! H& `    for(int c=0;c<c_num;c++){
        for(int a=0;a<area_num;a++)/*
: j4 g' f- \8 V! }) v7 A4 p        {    int p;cin>>p;per[c][a].setper(p);
6 {, Z6 W# Z. _) j            per[a][c].setarea(a);
            per[a][c].setclerk(c);
        }
$ x! p+ l7 B4 J; N1 y3 r0 C# `        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
2 e2 R; h) p) g3 L        {    per[c][a].setper((rand()%60)+40);
/ B7 U& y% }# d9 o0 P            cout<<per[c][a].getper()<<'\t';
        }//测试时懒得输入，故以60-100的随机数代替。
8 Z5 \" Y* A& o0 X3 X-    cout<<endl;
  u9 V; G& \2 K2 p" |# _. ]$ k2 T    }
* X$ l( Q! d! o    //output
        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
        clerk* people=new clerk[c_num];
$ D5 u- u% A1 {1 L+ C) \        area*  areas=new area[area_num];
" y8 Y. s9 t7 P        int totalper=0;
/ H8 F0 q) F1 S$ }) n+ d4 T* M& f4 X        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());
) g* d1 h) P! C0 K0 i                people[i].setisin();
                int number=areas[per[i][j].getarea()].getnum();
, L  x$ O- u; f. h/ o                areas[per[i][j].getarea()].setnum(number);
                totalper+=per[i][j].getper();
                break;
5 f% ]; o5 D3 ?1 \. @) O! z            }
4 N2 e3 p6 x/ @2 T2 z2 ~9 W        }
+ X4 P, b" r! H# A        cout<<"能达到的最大喜好度为："<<totalper<<endl;
}
void getorderbyper(ifo array[]){
7 L9 w6 j1 ?! Y4 |$ `    int max=0;
    for(int i=1;i<areanums;i++){
4 j$ }" G8 \( ^* S4 p        for(int j=0;j<areanums-i;j++){
# i' d/ T9 X, V1 G+ G( f) \        if(array[i].getper()>array[max].getper()){
, f# O( e+ D) q: {. H            max=i;}
        }
5 t3 q  r. f+ b2 p9 {, b        ifo temp=array[max];
0 H- p7 ?2 B5 V. u2 g) h        array[max]=array[areanums-i];
) k$ l2 u# z3 c9 i        array[areanums-i]=temp;
& s# [/ K; U9 ?4 `        max=0;
3 a! k$ m$ a' H/ H$ Q8 D    }
}

厚积薄发

代码3：
/*
+ w& A) w! v1 Y) U& Y算法思路：
2 a- L) v7 f( S6 @. Z  [9 H& V: N; y（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
) V) U6 ~# |# r$ f- b再加，该人的所有喜好度设为0，
（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
% s# B, N2 R7 C) H; O, J$ X& H(4)最后输出总喜好度。
*/
0 j' j+ z& K+ x' y/ l6 v! U#include<iostream>
9 q# R- P! [' _2 L( kusing namespace std;
! J; a8 V/ I2 ]5 m0 eint b[3][3];//M*N矩阵
6 E5 t7 ^! ~8 f: bint a[3]; //区域人数上限数组
+ L- d; s  G6 `% T( Xint c[3];
int temp[3];
int sum=0;
! Y6 h3 G: l3 v+ u& Yint max_num()
# ?% A: k, \" Y+ u/ y7 W{
    int max=-32767;
* ^  A4 l6 _7 ]0 Z' i! q& r    int x,y;
    for(int i=0;i<3;i++)
3 v7 S7 \' v- u3 y% z    for(int j=0;j<3;j++)
+ D( E3 d; d) c" i* t  Z    {
. ^& {7 O$ G; x/ k' p        if(max<b[i][j]&&b[i][j]>0)
        {
            max=b[i][j];
6 p! N$ D1 J- y: w4 }5 I! T& C            x=i;
            y=j;

* x- h% p" o6 E. d        }
    }
   
    if(a[y]>0)
    {
        c[x]=y;
  f7 d" x: f. h' q* i" r        //cout<<"c["<<x<<"]="<<c[x]<<endl;
        sum+=max;//总喜好度加上添加
9 E; Z/ n1 K( `8 K4 u, O% y; F# ]        temp[x]=max;
        a[y]--;//区域上限人数-1
    }
    for(int k=0;k<3;k++)
1 v6 Y! q0 h1 I% P: j! \    {
: v' ], C1 I. V# Q) j' A% [        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
    }
5 S2 @  ], ~! B+ N# @# O$ d0 q    return sum;
6 }5 k5 Q* @* _7 r& ^}
6 u  ^  ^* ]& e, ?int main()
( U: [* [9 ^% }( {{
   
    cout<<"input 3 zone's limit:"<<endl;
/ K  F/ Y9 X& a$ k3 C: V/ b# v+ G    for(int i=0;i<3;i++)
    {
        cin>>a[i];
' |# L7 l* T. }$ N* X; [1 v% f    }
    cout<<"input 3*3 actangle:"<<endl;
' j+ H4 p, J( v! q* O6 a: K    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
* e& N& f; D9 s- r, x, i    {
        cin>>b[i][j];
1 U6 N& @( g* v5 U2 ]+ x5 P$ x    }
    for(int k=0;k<3;k++)
" a" R  {0 Z7 n4 t8 G    {
& a8 Q: ]/ k: e) K% ]        max_num();
4 f4 I: [6 u) e. `% m% J    }
    //cout<<"sum="<<sum<<endl;
- W3 l' N5 i+ t9 P* @6 L    cout<<"sum=";
    for(i=0;i<3;i++)
% v9 k' ]# y8 `: d    {
        cout<<temp[i]<<"+";
    }
& W( G- m5 `; t$ U2 G4 p8 h1 G, i5 X4 j; F    cout<<endl;
    cout<<"reslut:"<<endl;
9 L' W8 j5 x0 h: \* ?    for(i=0;i<3;i++)
    {
% ?" r! W9 C; A# O8 F  e# C% f1 S7 V        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
: z( W* ^3 r) x- k5 }7 ]; p    }
    return 0;
8 b- Y1 y& P5 {% y3 F}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
数学中国社区分享快乐！
1 Z  \% a; e' {4 m; h) X

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.
2 b% P  z7 z9 L" ]' q. I7 h

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！