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

厚积薄发

座位调整

题目描述：

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

$ o7 [! n$ s$ i* u" ]- m# K: G2 l调整的方法如下：

1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。
) A/ z! G+ H: G1 x3 V6 u
- v1 K- u5 |. m4 T. v; A2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。
% q  v: R! X! O- t* F0 d
3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。

数据输入：

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

+ n6 h5 `- V6 {+ K! K第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。

) S' Y1 `7 |9 ]7 P紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。
- x3 Q% J6 o1 U! _# N* t
答案输出：

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

输入样例

6 z; _  G9 \  b6 V3 3

1 1 1
! F% {' a/ q3 O8 V8 v$ X2 P7 `
100 50 25

100 50 25
; Y. ~2 M! G' V5 z) `; ]
100 50 25

" m- V: ^: l. w8 p# R: b* ?; M输出样例

175

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

厚积薄发

& [# W4 o1 e5 Y' ~6 ~
  m) T. Y5 u7 `' j$ W' M#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
" e4 n% z1 U; o$ V. o5 c, H2 Nint c[3];//记录某人i去的区域j
int sum=0;
7 j" C, U: m2 \int max_num()
{
    int max=-32767;
" G$ @- k5 M( [  y+ g    int x,y;
# O( N5 Q& \( F    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
* x1 y' w% F) F4 n$ {! j0 W6 @    {
) j/ y9 w4 B, X        if(max<b[j])
        {
' F: o! H( ?8 @' ~: Q            max=b[j];
+ b' N. H% q( M: Y& v/ n            x=i;
            y=j;

% f: Q1 S( S- }        }
* k+ [, n- P( y3 m- U$ {    }
+ @4 {. P2 A- @. R: b: s3 t$ F8 @7 q   
5 H( @5 o$ f7 m    if(a[y]>0)
% N- n1 T7 _+ j: U( t    {
6 `. o1 x) J+ z# K7 F4 o        c[x]=y;
        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
0 z5 f0 O$ N6 A& W6 D        for(int k=0;k<3;k++)
/ Z: R+ [- X" @3 t0 r9 y        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
% u4 j$ Q3 H$ T        }
    }
    else
% i: [) n* P$ P& Y% Y    {
* T( ^4 A1 e% R/ \( `* M        b[x][y]=0;
    }
0 g" M+ d9 ]- a8 l   
    return sum;
}
int main()
, O& {5 i8 u: a7 Z: n% k- Z9 L{
   
. g& T5 b& O4 E! O, `3 T    cout<<"input 3 zone's limit:"<<endl;
% ]) e; x3 Z( |: ]( z$ d    for(int i=0;i<3;i++)
' }$ P% ?9 ?% e. r  Y1 D4 q! ?5 V    {
6 f2 y9 u* N. S4 ?5 d' a4 `* P, |, _        cin>>a;
% W1 }5 Y$ r  m/ ~' q( `- C% d    }
: J) n/ G7 q" d% G9 {$ z4 |    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
+ ]% S* k& H0 b% y* n: r    {
. @* l9 F1 S( {, I6 w        cin>>b[j];
* t/ j; O, x8 D, D' F, M0 w    }
    for(int k=0;k<9;k++)
    {
  @2 H( b6 _8 |0 D. S/ ^. [7 k        max_num();
    }
   
    cout<<"sum="<<sum<<endl;
    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
3 b4 Z, q- V0 s' ^3 {    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
; z3 r- ?0 b/ A/ M8 l    }
# X  @; B; \6 R    return 0;
. k( l) b1 v3 G9 ]6 O}#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
8 D7 c6 {- f0 Q# W5 Cint a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
! q( ^' r( w+ N# x2 jint sum=0;
int max_num()
{
( Z% C. O! N9 _. U9 ~; t$ ?/ C    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
1 X/ f  s; ]6 [" x1 R: ~" p; }    for(int j=0;j<3;j++)
3 m1 C0 f; R' X; f    {
6 C; R: ]0 Z- s" I        if(max<b[j])
        {
            max=b[j];
' f5 Y. D, |4 {% J            x=i;
" n; T" W& `+ T; [# B            y=j;

        }
    }
   
    if(a[y]>0)
    {
        c[x]=y;
3 \: D9 [. h# _8 c        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
, ^- x& X' x/ @) [: l9 j, S        for(int k=0;k<3;k++)
        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
$ R9 t7 N$ W! S2 B        }
    }
    else
2 O4 @, }+ ?0 @8 K0 L    {
- \+ l+ h* h( a! W        b[x][y]=0;
    }
   
    return sum;
}
3 G  u' v" G1 e+ V+ ?% i7 q, Sint main()
{
4 j+ K6 c+ G. P% `" q' ?   
4 j* i, F) s! Y% U. v, f0 b    cout<<"input 3 zone's limit:"<<endl;
$ R6 M% U' n* z8 ~2 _( a    for(int i=0;i<3;i++)
    {
        cin>>a;
( X& h" a8 A) L+ g& v9 o    }
3 y6 ^+ l- z. N& H" L9 e    cout<<"input 3*3 actangle:"<<endl;
, b  J6 A. O, ]" g' a. k! Z! s3 l    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
1 m$ q* Q+ l' ~: ~3 D, s- F# _    {
        cin>>b[j];
+ P; @! l3 H3 w( @, B    }
    for(int k=0;k<9;k++)
    {
  Y: h/ Y0 f$ s9 {2 v  {        max_num();
    }
   
    cout<<"sum="<<sum<<endl;
    cout<<endl;
& Z* h4 t: G/ [    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
. T+ ]: s$ A4 ]" M    {
/ g% h# o, G8 S9 E: W. u+ G- {        cout<<"people "<<i<<" go to zone "<<c<<endl;
1 x2 H$ ^0 C9 _& |" G. Y+ I    }
    return 0;
9 q3 G" s; x' b1 B4 ^  ^}

厚积薄发

编程代码二：
' I/ e8 R8 l2 Z- h+ p% D#include<iostream>
#include<cstring>
#include<ctime>
" L/ s4 h$ [# f" ]$ _, \8 Pusing namespace std;
class ifo{//矩阵的元素
2 {+ n- B8 z- t* x    int clerk;//员工号
7 m* n4 G/ @! ]# G4 _- f    int area;//区域号
    int per;//爱好度
$ f7 ]: S% z0 D9 x( o, F# mpublic:
+ {* M0 \  g% Q5 H* \    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
    int getclerk(){return clerk;}
4 l( Q' p' u' s: F    int getarea(){return area;}
    int getper(){return per;}
8 B. h) L: u% P/ H    void setclerk(int i){clerk=i;}
    void setper(int p){per=p;}
    void setarea(int a){area=a;}
6 M4 G8 ?% c% B4 ~- K};
5 c# g7 C, g4 k+ \' }, _" xclass area;
class clerk{
' t% Y/ b: W+ q( S+ b$ h) h+ D    int areanum;
    bool isin;
" {1 C1 v$ I* B    int inarea;
' ?0 h7 m- \$ f8 P- q2 H/ Dpublic:
    void set(int num){isin=true;inarea=num;};
1 u; L" }" @2 E% s+ L" d5 z- z    void setisin(bool b=true){isin=b;}
- y  N5 q- y, X9 ]8 |- ~$ D  N2 `$ X    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
};
class area{
    int num;
    int max_num;
public:
    friend void set(int);
    int getnum(){return num;}
: |+ W! s* O, v    void setnum(int number){num=number;}
. K' Z3 f# j( g8 Y7 R    int getmax_num(){return max_num;}
% T' _/ P* a$ g6 V+ j" K    area(int number=0){num=number;}
    int getclerk(){return num;}
  h8 O# U2 Q5 V2 _- c3 x    void addclerk(int ps){num++;set(ps);}
};
: h# s5 `4 s- [1 f" s: M8 J  M4 a/ lvoid getorderbyper(ifo array[]);
int areanums;
" S8 B/ I4 g3 Tvoid main(){
$ w9 r: r3 Q3 d! A! o    //input
) ^& V. C. j2 w# o  w) K    cout<<"输入区域数：\n";
& Z1 N$ ^. W1 p% Q$ L1 m  N    int area_num;
    cin>>area_num;
    areanums=area_num;
    cout<<"输入员工数：\n";
$ n+ ~. u6 i  z% o    int c_num;
    cin>>c_num;
( Z$ @- _$ g, S  {' [    cout<<"依次输入每个区域能容纳的员工数:\n";
- d7 j. ^7 ^; A* z* I. V) [! N    int *max=new int[area_num];
    int nownum=c_num;
    while(nownum){
        for(int i=0;i<area_num;i++)
) h4 \+ R- X5 i        {cin>>max[i];nownum-=max[i];}
        if(nownum>0){
            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
            nownum=c_num;
        }
! g; {) h6 R5 |4 h! U5 O5 e        else nownum=0;
3 g8 U) [- I% A7 i* s+ K3 I# a    }
    cout<<"按行输入每个员工的偏好：\n";
9 b) w# i: A- ^1 K; \    ifo** per=new ifo*[c_num];
, M- F+ R6 ?$ O    for(int j=0;j<c_num;j++)
" [  l5 q7 Q$ E7 r. L$ \        per[j]=new ifo[area_num];
    srand(time(0));
/ X, Q* B% I3 z' P# ~; W* i8 O    for(int c=0;c<c_num;c++){
- e/ x  Y9 c# Q2 |8 X3 g$ |4 I        for(int a=0;a<area_num;a++)/*
% v% F2 g. h+ w        {    int p;cin>>p;per[c][a].setper(p);
4 `" \0 b2 E, w+ |5 @, l            per[a][c].setarea(a);
' a* ^6 B7 \( W. k            per[a][c].setclerk(c);
        }
        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
        {    per[c][a].setper((rand()%60)+40);
            cout<<per[c][a].getper()<<'\t';
( U$ c8 p  x8 V0 M0 x* W, ~7 n' g        }//测试时懒得输入，故以60-100的随机数代替。
-    cout<<endl;
    }
    //output
+ k( H1 U/ J7 Z9 K1 \        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;
        for(i=0;i<c_num;i++){
. C; F/ _3 A* ^. N- w            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());
                people[i].setisin();
8 U+ j3 v8 L& V0 h' ^                int number=areas[per[i][j].getarea()].getnum();
5 U# R6 ~4 @2 @) [9 N9 g4 {& D                areas[per[i][j].getarea()].setnum(number);
, g' h1 r' }* R" ~# F                totalper+=per[i][j].getper();
* ?- w' Z, B5 z5 q) O                break;
. ~% J3 Y) `, ]- R            }
( r+ v$ T. t2 l5 \        }
        cout<<"能达到的最大喜好度为："<<totalper<<endl;
}
void getorderbyper(ifo array[]){
' E4 t! R9 d) M% q9 U( ^    int max=0;
% r& u# \( e( J, K' J- ^    for(int i=1;i<areanums;i++){
        for(int j=0;j<areanums-i;j++){
        if(array[i].getper()>array[max].getper()){
% Y2 W2 U% ]- W2 g            max=i;}
        }
% n/ k4 u5 _& c        ifo temp=array[max];
3 [0 l$ d- k. h6 `        array[max]=array[areanums-i];
0 g2 n' \+ n1 ~/ ^7 p: w/ E5 V0 C: d        array[areanums-i]=temp;
        max=0;
+ ?! g# Y7 `- S4 v$ q    }
. F5 {; ?# y( n6 F# ~% w% Q: p}

厚积薄发

代码3：
6 @2 \3 \1 G7 f/ v; c/*
! a+ T% o" o1 U算法思路：
（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
再加，该人的所有喜好度设为0，
7 d7 e, A& T" \; X4 k（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
- W% y  u. b( B* F6 [/ L/ ?, s(4)最后输出总喜好度。
*/
& ?4 e2 k0 o* p3 `4 k- ?#include<iostream>
using namespace std;
4 L- |/ X/ d5 l* Mint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];
4 ~5 h  }: H( H# j! W. g  b$ @int temp[3];
int sum=0;
int max_num()
+ E$ H/ W  r4 r( M{
9 I) N. c& k9 _8 ?' f% p7 o    int max=-32767;
    int x,y;
& \7 B- C8 m; }3 b% S- D    for(int i=0;i<3;i++)
# n, H$ x% E. t, g) ~8 Q( k    for(int j=0;j<3;j++)
    {
        if(max<b[i][j]&&b[i][j]>0)
4 X5 y: h9 w  g        {
+ o+ ~. K* A, r% Z7 k. F& l) A/ V            max=b[i][j];
            x=i;
. N8 y1 {& c* i, d) d0 s" l. i            y=j;
7 h: k  k2 K9 H9 t# P3 Y
        }
    }
   
$ ?  W  l: X$ A6 q( c9 _; B    if(a[y]>0)
7 S, M9 M/ p) y+ K2 n    {
        c[x]=y;
: T+ S1 C9 r# i# ~# b        //cout<<"c["<<x<<"]="<<c[x]<<endl;
- a+ d! ~4 A8 q0 \: z        sum+=max;//总喜好度加上添加
        temp[x]=max;
. u* O' Y( l3 h& w        a[y]--;//区域上限人数-1
    }
    for(int k=0;k<3;k++)
    {
        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
5 D/ G% G7 ^$ E0 p9 o    }
9 r: l: J3 m. K: ]' D    return sum;
  S7 D& T( a5 n$ H+ @/ _1 Q- @}
int main()
; O9 o) G* Q. S1 B% h2 \{
   
    cout<<"input 3 zone's limit:"<<endl;
( [( @1 E0 w5 Z" T) \# ^" q% [    for(int i=0;i<3;i++)
    {
        cin>>a[i];
    }
% C7 e) i+ |8 y0 n1 g0 e" |1 Z& Y    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
4 f( s/ I0 I$ }) l" s1 z7 B    for(int j=0;j<3;j++)
    {
        cin>>b[i][j];
* Y% a- h& ~1 ]" Q: w6 T6 W    }
$ G8 ?, s8 d; d1 t2 Y4 K  N4 B! V1 Z    for(int k=0;k<3;k++)
    {
        max_num();
    }
    //cout<<"sum="<<sum<<endl;
& P$ ?% _7 y9 I! L* W. f    cout<<"sum=";
" o$ k3 s+ K& e0 w    for(i=0;i<3;i++)
    {
4 K6 U3 d3 `& x  l8 |        cout<<temp[i]<<"+";
/ d) Y% }0 p0 N# @; B9 I0 }    }
    cout<<endl;
# E" Z+ l2 x% x3 e. U) b/ X+ Q; I+ F    cout<<"reslut:"<<endl;
# N; s/ `5 s2 K    for(i=0;i<3;i++)
    {
5 x( Y# G: X% Y- ~% R        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
    }
    return 0;
}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
$ c  R5 J( C! U+ O) H. g数学中国社区分享快乐！
. `) p7 E' e4 N' w

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.
  }  {9 t- [& c( d, {* l

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！