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

厚积薄发

座位调整

& @) n# E* s9 d% w4 O0 R2 q题目描述：
7 h1 u/ r7 R$ E. ^, g- J
百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。

- D$ w6 }. B3 {- x; m调整的方法如下：
+ T  H% ^; s4 t" I/ v8 n
0 `/ h/ c/ B" i' Z0 o' D# I1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。
7 d5 e' k- D% R' q" V3 J
2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。

3 a# v/ W. c2 q! ]8 L; m7 e" i* P3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。
# ^# Q: @# j/ t* E0 C$ t
数据输入：
1 W! Q$ \' ~& {$ i6 b
第一行包含两个整数 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 个区域的喜好度。
  A# v$ E6 J  I9 J1 r. O0 j
答案输出：

对于每个测试数据，输出可以达到的最大的喜好程度。
' D, K1 U3 `% \" q
输入样例

5 Y1 w8 t: Q8 {: C" N, b* j, j3 3

  f4 m! I8 ]8 ^8 m+ e7 T7 g, W1 1 1
3 `+ J( P+ ?& i2 ]
100 50 25
+ X' l3 _- }. u1 j( W* |* \
3 j. c9 ~6 }3 r2 T1 D100 50 25
! K9 s4 A' Q# N- a0 e. G$ N; X
8 r+ n( M/ z" A* [( K, f; z0 D4 G100 50 25

输出样例

- X8 t! l, P( |, |0 R* f- ~6 b175

& q* H3 Q  ~& |. D: _8 O2 r

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

厚积薄发

' d; a& F' r2 [9 U* _
  l) q" X0 n+ X, {7 D9 ]$ S#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
int sum=0;
$ _# n) |9 c( Q, t: i, Eint max_num()
{
% R% y3 X( f) l: V7 W7 q+ {; b  e    int max=-32767;
, n, d2 v- w7 S# Q    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
6 d# [! C6 S8 w1 j$ P) \# Q        if(max<b[j])
        {
            max=b[j];
( s5 B, a$ |2 T% R) V* S: V            x=i;
            y=j;
  t  u5 t- y  l! I) N/ F1 k
        }
: n: a3 ?6 J6 J    }
   
& Y& }1 q7 G3 I7 }- E    if(a[y]>0)
    {
        c[x]=y;
4 C% E0 d/ R# Z; C( b) b, A' f        sum+=max;//总喜好度加上添加
; |# ^% L5 Q: M# O6 ^5 S        a[y]--;//区域上限人数-1
( M5 ~% z- e4 [        for(int k=0;k<3;k++)
/ f& ^7 k/ |8 j* o8 b7 ]        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
$ q( j) g8 S7 L& q- @' a# D+ \- M        }
( U. N+ W+ A8 x  z% m    }
    else
4 }, |8 U; G# p1 L# E    {
& ^8 X" r) z% S+ Y2 Y        b[x][y]=0;
    }
) {9 n* X' N9 \$ \7 _! {   
    return sum;
}
  k# f8 H$ G! vint main()
  V0 \* T) Q* {8 s" w1 @{
   
    cout<<"input 3 zone's limit:"<<endl;
: j8 }: L) @) M. n1 i( P: ?+ Y    for(int i=0;i<3;i++)
    {
' U' K4 I, c7 v! e6 f$ b        cin>>a;
    }
    cout<<"input 3*3 actangle:"<<endl;
) R& ?' e/ H- v+ p; p. F    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
  b) ^$ w1 M# V2 c: N        cin>>b[j];
    }
    for(int k=0;k<9;k++)
( T  m4 e* c, V6 G0 F$ g    {
( |5 R+ Q$ m7 s$ |        max_num();
, ^7 s: Y; f) a: m; W0 D/ E# s# g7 W    }
   
    cout<<"sum="<<sum<<endl;
! B# {! l: b: N  Y0 ~& F& C- Q    cout<<endl;
6 K  ~& g& j  O' \6 u, L    cout<<"reslut:"<<endl;
$ W4 W  w* G# Q+ `4 B3 z    for(i=0;i<3;i++)
4 A# Y( g# ^6 v( m    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
    return 0;
4 P. q# w2 z% {3 X, r}#include<iostream>
using namespace std;
8 [4 j4 @9 l& i0 s2 D5 `- b1 hint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
8 U( ~7 h- y* G' b2 aint sum=0;
& J: S/ M( }( \' X' O! D  H( Iint max_num()
{
    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
2 |; X5 E8 @( |; Q6 T; F. X0 |- S    {
        if(max<b[j])
! G0 D9 c+ v: f( Q/ ~# y        {
            max=b[j];
$ Z  ?' u/ F$ ^            x=i;
$ B: K% J2 ^) B( ^            y=j;

        }
- x, G' M8 d/ p    }
  m2 w$ ]( @" b; p+ _* n+ }4 v   
6 n3 r# p# a' Q/ }0 j: a$ k+ U    if(a[y]>0)
    {
( r, I, ~! i% u2 }/ E        c[x]=y;
        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
9 C- r5 R% O8 u: m  j# V        {
. a6 \! ^; v! r  z# C1 r            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
8 u9 U3 E9 ]; a1 T: i( b% I        }
, n7 D/ j% s" r& e  _' s    }
    else
    {
: k4 m! P$ P: R; `5 @" u        b[x][y]=0;
) @  w& X% o+ a8 V! g6 i    }
   
    return sum;
* g. b9 L- m" N}
int main()
  K0 r+ w4 Y  t& \. q{
   
1 E2 o0 ]- A" u  Z    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
  U. Q0 z% Z3 s% U, [8 [3 y! r    {
& Q6 I& `( o& `- ?5 k( @        cin>>a;
    }
" O( f4 \& [% o8 v0 o; ?    cout<<"input 3*3 actangle:"<<endl;
1 U5 C5 P$ ^+ c( c( Q9 G    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
& F1 c) m6 j$ t, B& y% g( g        cin>>b[j];
    }
    for(int k=0;k<9;k++)
    {
6 K, O8 ~, G) `+ a        max_num();
    }
   
    cout<<"sum="<<sum<<endl;
    cout<<endl;
, x0 V1 l7 L# {! v    cout<<"reslut:"<<endl;
' H1 b: y1 F5 u  F4 U    for(i=0;i<3;i++)
5 `9 I8 U$ C2 L+ Z3 C; G& ~) ^0 N# C    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
6 X. n0 _  q& p( s4 [5 h    }
! b8 l' A: h+ D7 Y    return 0;
- _( |+ C: K3 ^  n0 X& Q- W}

厚积薄发

编程代码二：
& l% ]/ L' A" l4 N$ o, ^3 w7 J#include<iostream>
' ^/ C- K( s2 O2 j' s+ a: \#include<cstring>
8 ?; W. ]$ L8 n; Y" n& v#include<ctime>
using namespace std;
7 N/ r; _$ c. z4 Z9 Tclass ifo{//矩阵的元素
, S( P( Q' X! L+ F# A    int clerk;//员工号
& q  x4 F- U% j    int area;//区域号
; B% i! D! j7 [5 d2 L/ U    int per;//爱好度
public:
    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
    int getclerk(){return clerk;}
    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;}
};
, s6 Z! A5 W5 v5 `* qclass area;
, l. }3 \0 S' z8 k7 U8 q4 Eclass clerk{
% s3 ~. @  t( `5 \3 h  T    int areanum;
    bool isin;
3 Z2 ]) H4 U) \1 X4 |/ S7 C) T    int inarea;
( y- W, k- ~1 V2 c" l2 v% n+ K& V& wpublic:
* U" A$ S; u  o% F+ k    void set(int num){isin=true;inarea=num;};
# p- h" \/ ?  J2 n3 f5 U    void setisin(bool b=true){isin=b;}
    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
5 L1 m* e( r5 ]" o: _4 `};
# q" z# ~# j# M3 K' l3 Rclass area{
    int num;
    int max_num;
/ }) w0 j2 C* @2 Qpublic:
    friend void set(int);
/ R0 c8 _  I, f" W6 l( o, n    int getnum(){return num;}
    void setnum(int number){num=number;}
    int getmax_num(){return max_num;}
, z- k& L3 h0 Z3 x! ?  ^: \+ g; P    area(int number=0){num=number;}
. ~6 c3 o/ N' W    int getclerk(){return num;}
0 h% b: p3 x# ~  N    void addclerk(int ps){num++;set(ps);}
+ `+ s" w- C" O3 E9 T8 m};
void getorderbyper(ifo array[]);
int areanums;
- w7 v& F! `& M, i' w2 [; pvoid main(){
    //input
    cout<<"输入区域数：\n";
& h0 @& }7 J/ o( Z, f' i    int area_num;
    cin>>area_num;
    areanums=area_num;
0 \' [/ X4 D$ c+ ?) `: I9 E6 B    cout<<"输入员工数：\n";
    int c_num;
    cin>>c_num;
    cout<<"依次输入每个区域能容纳的员工数:\n";
    int *max=new int[area_num];
" p8 Q& r! V' D: P  |) P1 U7 z    int nownum=c_num;
3 b. e2 C! N0 `/ l- z/ d) u" [    while(nownum){
* p+ i6 j, a" K2 P& t        for(int i=0;i<area_num;i++)
        {cin>>max[i];nownum-=max[i];}
- B$ q; E/ e9 x8 A        if(nownum>0){
* w- e7 V& O  S$ @+ f1 h            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
+ W' y/ D+ v" J            nownum=c_num;
$ h. M; U2 p( J' m* N        }
5 V# I1 p8 z/ Y9 s        else nownum=0;
4 m3 R. ~$ }; G! d9 _6 m) W' B1 W    }
    cout<<"按行输入每个员工的偏好：\n";
    ifo** per=new ifo*[c_num];
    for(int j=0;j<c_num;j++)
        per[j]=new ifo[area_num];
    srand(time(0));
    for(int c=0;c<c_num;c++){
        for(int a=0;a<area_num;a++)/*
# K6 t& k+ T, Q) l$ h        {    int p;cin>>p;per[c][a].setper(p);
            per[a][c].setarea(a);
# s$ F# R& G3 U: f            per[a][c].setclerk(c);
8 D5 m2 ]. h8 |& g1 o1 V        }
        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
        {    per[c][a].setper((rand()%60)+40);
3 e4 U  ^5 J) d- z. f% ^! p  L4 X            cout<<per[c][a].getper()<<'\t';
) ]1 ^5 M" |5 ?# I. H        }//测试时懒得输入，故以60-100的随机数代替。
: w; W; @( R( l/ G; [-    cout<<endl;
1 x$ Q+ H1 w% B* d/ i    }
    //output
        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
. L" J- S: j0 Z( T% G* S        clerk* people=new clerk[c_num];
        area*  areas=new area[area_num];
        int totalper=0;
* S4 F. Q, T2 K" ^; w% d1 ^0 b1 L        for(i=0;i<c_num;i++){
- I% E0 e* ]7 u            for(j=0;j<area_num;j++){
. r6 f  x: [7 A1 f            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();
8 z# Q8 E$ f$ V( e                areas[per[i][j].getarea()].setnum(number);
& v4 q4 p5 e# A- w  l% S- M$ m' X4 Y0 b( b                totalper+=per[i][j].getper();
                break;
: L. R) E6 `, ~3 f) V: F, D            }
        }
        cout<<"能达到的最大喜好度为："<<totalper<<endl;
2 t% C: T* j# ~1 [1 o7 R9 E! S}
" |9 [! Y8 X7 ^+ ovoid getorderbyper(ifo array[]){
* i, N8 ^# \) L5 _/ I" f' P2 F    int max=0;
# a" P2 V9 B  i) C& C% ]/ ^6 p    for(int i=1;i<areanums;i++){
        for(int j=0;j<areanums-i;j++){
        if(array[i].getper()>array[max].getper()){
( H: s$ W, X( @7 G) A- t' `0 ^" P1 x! R. r            max=i;}
        }
9 G! `5 G' v5 ?3 Z+ P        ifo temp=array[max];
/ w! S% U7 o3 p, T% y. Y& \, E        array[max]=array[areanums-i];
7 N8 f7 q! A' S# H' b) H: `        array[areanums-i]=temp;
3 _! T4 |. c& J( a. D        max=0;
    }
}

厚积薄发

代码3：
/*
+ n; ^  ~! W& D. e+ u+ Y: D算法思路：
4 Y5 [  Y# F" k1 T- v3 }8 v) b（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
再加，该人的所有喜好度设为0，
$ ^  o6 {5 s: m% O$ f( ~（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
% y' ~6 w9 o. W* h5 E" s（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
(4)最后输出总喜好度。
*/
#include<iostream>
8 K+ F' L9 R( }2 yusing namespace std;
: y: D+ v, l- m3 C6 R( @int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];
% ~% C" ~) T  f+ z" t% i7 m4 Rint temp[3];
4 p0 b# i+ c/ [+ @: iint sum=0;
9 k) N' D' y$ i- Cint max_num()
# F% E/ W! r+ i- E/ n# N' L{
    int max=-32767;
    int x,y;
; D' s* Z) ~" D8 S    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
! _$ X8 s: G  W: ~+ j4 Y    {
6 {- }) g/ E9 v' J        if(max<b[i][j]&&b[i][j]>0)
$ O7 l  V! k3 s        {
" k' |$ ?# ]( c% R& ~, f- e3 ~$ F            max=b[i][j];
            x=i;
            y=j;
! j: A% [6 I' T; ]& X
        }
9 {. A2 u+ p8 U3 X7 G) D    }
   
  h& n0 _# D! u# k8 @! Z- z' G    if(a[y]>0)
    {
6 j) M, P- D6 I! s$ m        c[x]=y;
  N7 G% L. Q4 i% F9 Z7 C        //cout<<"c["<<x<<"]="<<c[x]<<endl;
        sum+=max;//总喜好度加上添加
  g: p* V* h7 Z$ H; }        temp[x]=max;
$ Y; D" U2 o8 |( h0 l0 n' A        a[y]--;//区域上限人数-1
$ x  y! G% I, |) @1 ?. t* J    }
' p# c; K1 R) M: _& h( b' I( ?' ]/ b    for(int k=0;k<3;k++)
: a' X2 V/ @0 j; Y+ m& E, Q' K    {
+ P* ]: s" S; z$ {        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
    }
    return sum;
}
int main()
{
$ R- D6 X, x% K2 e# a2 x5 ?/ V$ W   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
! w* c2 R9 C, v9 g0 o    {
( a0 i& x$ X& `' }3 G        cin>>a[i];
    }
    cout<<"input 3*3 actangle:"<<endl;
4 T& _- J" B0 C$ x    for(i=0;i<3;i++)
% [& |9 P3 G" K: H# E" B' D    for(int j=0;j<3;j++)
2 j  h" f6 w) W" `' ]. ?- f# t# {    {
        cin>>b[i][j];
    }
    for(int k=0;k<3;k++)
    {
        max_num();
    }
2 P; O" [1 f- ~, y  c& t. u    //cout<<"sum="<<sum<<endl;
    cout<<"sum=";
    for(i=0;i<3;i++)
8 e3 E# M( o1 f' u& Y    {
        cout<<temp[i]<<"+";
' l! B, l: g$ c! A% \* H) m    }
* o6 z; L4 `0 U    cout<<endl;
- K. T. @- e. t% y' n) N* E    cout<<"reslut:"<<endl;
) y9 V* k7 H3 E. p7 U    for(i=0;i<3;i++)
    {
        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
    }
8 c: ?2 e! h+ e- H7 w$ _    return 0;
}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
% C5 W$ I' M8 x4 k4 v4 {/ f数学中国社区分享快乐！

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.
7 E2 o  M- d9 b- ?

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！