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

厚积薄发

座位调整

1 H4 U2 n" e% L* k# k  q5 S题目描述：

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

/ m0 F* d4 ^; p; r+ {$ S调整的方法如下：
$ j8 {% u. T. v8 {
/ b" P( V" [4 k; T8 K( j1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。
9 d3 B+ r- [# ^  s/ X; r5 H# ]% }
: z7 f3 l* e( v1 x' |& b6 D- I" y% p' j2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。

' ?4 X! e+ \! b, ?3 i1 r2 g& G# |& P3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。

数据输入：

第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。
- C# o; l- f4 x0 f! z
4 U; O' ]( S& R第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。
# }  h% {6 ?: [- U1 _1 {
紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。
. R; a' X+ h' Y! x8 _+ H% Q
答案输出：
, G* q+ J" o/ e8 C1 p0 `
对于每个测试数据，输出可以达到的最大的喜好程度。

输入样例

- m- [7 f& @+ R# L' M' K3 3

; m: k0 X, m+ ~$ F# i) ]- B1 1 1

100 50 25

/ j7 @) u& C+ E. R$ ?8 K+ F100 50 25

+ Z; D3 s+ i! ~" V100 50 25

输出样例

; J2 e( s# b6 X) g/ T
175

, i. K  I) N* J8 F

: t4 ?# d+ u- O4 Q2 S$ x
数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175

厚积薄发

#include<iostream>
using namespace std;
1 M! C2 h7 T7 X( D7 kint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
int sum=0;
int max_num()
{
' |- d* B' z# y! u, a7 O    int max=-32767;
& c% p: q' ]0 S: v0 F    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
6 d' x- h1 q7 O8 A- o$ _    {
        if(max<b[j])
        {
            max=b[j];
7 @( O% X( M- G1 c2 j+ P4 s& M/ G            x=i;
            y=j;

1 ]! ~, [0 e/ t& h# m( _& n        }
+ L( E$ M4 Y8 E  g( z2 b% `    }
1 ^' L3 n8 ^& Y   
    if(a[y]>0)
    {
, }: |# l2 ?: H2 S# d" Y        c[x]=y;
, G+ @3 d1 |  f        sum+=max;//总喜好度加上添加
* y8 L7 {. T% e8 `# ]        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
        {
" E, t, z5 @* d  J/ d            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
) \$ R8 l, Z* g6 a; Y    }
. [9 T! l: }% d9 z5 A2 n1 C7 M    else
    {
- H' i% H, L/ ^4 \) C5 z, i! ?        b[x][y]=0;
    }
   
! |2 ~: L4 z  p- A6 v9 C0 J3 \/ S$ U    return sum;
9 f  s7 M4 k7 ?}
- P' \1 ^8 a. E* s. ]int main()
{
   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
    {
        cin>>a;
# @3 N! D0 _2 U/ s1 y0 e    }
2 T# ]6 j* g; u8 i% f% N    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
/ a& ]) i6 f) p6 ]/ S    for(int j=0;j<3;j++)
    {
* l7 y# t) ^# G  [9 [% D; s        cin>>b[j];
) f' N6 c# B" C2 i5 l    }
    for(int k=0;k<9;k++)
0 c! L: o6 i4 L# h* P, W    {
        max_num();
; M8 d% H, u+ e: i' H* q    }
0 c- x( u5 z  s; V5 y   
& F: H% D' ^9 ^    cout<<"sum="<<sum<<endl;
  c" x" ~. w3 [; ?1 h% g; B5 j/ b    cout<<endl;
9 Q7 N& j9 ?1 `! x    cout<<"reslut:"<<endl;
1 H) p$ \1 |* p+ w: P( q    for(i=0;i<3;i++)
    {
) V' p" q! Q9 {! ]        cout<<"people "<<i<<" go to zone "<<c<<endl;
3 g- E! v8 Y* H- i0 Q    }
) p  g3 n: V6 C" T& _& m    return 0;
}#include<iostream>
+ R& \& a$ t+ F: P2 }4 Jusing namespace std;
: y/ Z- O2 M. x& W8 s" \int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
0 S  z9 I. ^( J# w0 gint sum=0;
6 c- f1 g5 Z7 Z, Q7 yint max_num()
9 C" h; p: p' C" [3 V{
    int max=-32767;
    int x,y;
4 l- o. P, ?1 i" Y: K. U    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        if(max<b[j])
        {
# H/ L9 b" k( U            max=b[j];
            x=i;
) V5 _/ M4 D$ g$ P2 d- X& i            y=j;
5 a# j: r8 O8 }& }
0 U, r0 |' _- f  z        }
( l8 K( C% H" g9 c; l    }
8 y9 [+ R5 J( p; P& I   
9 [7 K; k+ N* d# |' ~    if(a[y]>0)
    {
        c[x]=y;
; ?7 v' u$ u6 S6 B7 o6 X4 p! ?        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
: x0 X$ j" {6 b% r- o! @        for(int k=0;k<3;k++)
        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
    }
    else
# q+ k$ c% J8 H4 V8 X$ y$ Q& ~    {
        b[x][y]=0;
    }
   
' d$ b; U2 A4 P/ }, `3 R  C    return sum;
}
int main()
; p( a' [. Y* l2 l5 R* c{
   
6 B' p5 P: e( W" Z3 s3 E5 h    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
    {
        cin>>a;
    }
. M% {5 p) S# W" E    cout<<"input 3*3 actangle:"<<endl;
# P% P+ m/ S2 _, J    for(i=0;i<3;i++)
9 v9 z; D# x: |# v# z    for(int j=0;j<3;j++)
    {
) p9 K! k. r; L! ]2 @! I2 Z& H        cin>>b[j];
/ K! w  Z2 x8 s4 {3 s( G0 d7 s    }
    for(int k=0;k<9;k++)
    {
        max_num();
) V6 j$ {0 {' _3 p  b: A    }
   
    cout<<"sum="<<sum<<endl;
    cout<<endl;
' O5 b- c3 x$ y& z/ Y: |& n# @. a: U    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
% w  F/ m! ?6 r% u, t% u0 S        cout<<"people "<<i<<" go to zone "<<c<<endl;
" O( f- j. O. [, ~# p* z    }
    return 0;
}

厚积薄发

编程代码二：
5 ~9 }/ S2 g: L$ w  f#include<iostream>
6 g5 F7 O0 R7 R6 E3 x# o9 A- F#include<cstring>
$ m- X5 j0 y4 m! i' l#include<ctime>
$ e- Y0 ~; m9 {using namespace std;
+ T1 K0 K, H8 \! ~# \class ifo{//矩阵的元素
    int clerk;//员工号
    int area;//区域号
    int per;//爱好度
public:
    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
5 h* ~0 C& T7 s$ V    int getclerk(){return clerk;}
    int getarea(){return area;}
+ H5 Q+ {( N0 W8 D0 ?! i    int getper(){return per;}
    void setclerk(int i){clerk=i;}
& A  P: x; p! V6 V3 M- [    void setper(int p){per=p;}
    void setarea(int a){area=a;}
};
class area;
class clerk{
! e" h% ^7 \) g- Z# i    int areanum;
    bool isin;
    int inarea;
public:
    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;}
* E) P& K5 g2 E6 G};
class area{
7 K% `$ q6 O! H    int num;
    int max_num;
; N. K/ _) e# i& E& g* I2 t, opublic:
    friend void set(int);
5 W+ F, ~5 D7 `1 `) i' K    int getnum(){return num;}
    void setnum(int number){num=number;}
    int getmax_num(){return max_num;}
3 N3 ^7 F: v9 d- J4 [* l' P    area(int number=0){num=number;}
6 w- A* M& g8 G  k# S  W% Y) r4 P    int getclerk(){return num;}
    void addclerk(int ps){num++;set(ps);}
: I% k9 x3 J, r6 j# Q};
/ U; o6 n' r" e/ mvoid getorderbyper(ifo array[]);
int areanums;
void main(){
* f5 @! p5 d4 l1 b    //input
; \  a, R0 o) h! b9 \: h+ |    cout<<"输入区域数：\n";
2 d/ b9 E! C. m8 }/ M0 P, h6 v    int area_num;
2 x5 C2 @5 ^6 t+ S* t    cin>>area_num;
    areanums=area_num;
    cout<<"输入员工数：\n";
# S5 g) ^0 s; Q, W5 |; A* }$ n( d    int c_num;
3 _: R+ u, Q0 @4 j    cin>>c_num;
/ U  c; A" F, w    cout<<"依次输入每个区域能容纳的员工数:\n";
    int *max=new int[area_num];
    int nownum=c_num;
9 a% e* X' [' X% E) j    while(nownum){
# u$ T1 {/ w+ I- D        for(int i=0;i<area_num;i++)
        {cin>>max[i];nownum-=max[i];}
        if(nownum>0){
            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
            nownum=c_num;
        }
        else nownum=0;
    }
4 z3 c5 J: A, D! Y9 C$ S  t3 V    cout<<"按行输入每个员工的偏好：\n";
    ifo** per=new ifo*[c_num];
. g6 L3 B2 e8 u. b    for(int j=0;j<c_num;j++)
( |: _7 Q( _9 Q9 q7 ]2 d        per[j]=new ifo[area_num];
6 L/ C0 V1 l) |& @% h6 o    srand(time(0));
    for(int c=0;c<c_num;c++){
- V: G/ b& o! \9 g) ~        for(int a=0;a<area_num;a++)/*
        {    int p;cin>>p;per[c][a].setper(p);
            per[a][c].setarea(a);
; x  u7 B: \6 G* n  b% c            per[a][c].setclerk(c);
3 W3 V# B0 u. o+ j, _- C        }
, W1 p4 t+ R0 J# v7 \, v        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
- ~; a5 T5 s# h# Z0 z        {    per[c][a].setper((rand()%60)+40);
. j# z0 s9 @/ \1 \; ?- g            cout<<per[c][a].getper()<<'\t';
& g1 c& }$ m: t+ Z        }//测试时懒得输入，故以60-100的随机数代替。
& g2 P2 X+ U! {-    cout<<endl;
    }
    //output
4 I- ~' D$ l1 A        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
        clerk* people=new clerk[c_num];
9 K* K; g" i/ r" W        area*  areas=new area[area_num];
2 N9 k0 V7 L) A8 |        int totalper=0;
' Z2 \0 l( P# M4 w1 l6 @1 `1 y( K        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());
                people[i].setisin();
3 U8 I1 z/ Z$ b1 }$ U/ e* v: j" w                int number=areas[per[i][j].getarea()].getnum();
! {1 V, e: m; u6 E                areas[per[i][j].getarea()].setnum(number);
1 _* y0 X) X" F: m% |# j                totalper+=per[i][j].getper();
                break;
            }
! E1 b# i, _2 u9 [0 h* e/ A! |        }
        cout<<"能达到的最大喜好度为："<<totalper<<endl;
6 r. ~1 y5 e% h6 Q+ E}
void getorderbyper(ifo array[]){
    int max=0;
    for(int i=1;i<areanums;i++){
        for(int j=0;j<areanums-i;j++){
        if(array[i].getper()>array[max].getper()){
  ?1 m8 h' N/ }! X. J9 J            max=i;}
        }
: z8 u( N4 [# \6 Y6 d. Z/ L        ifo temp=array[max];
        array[max]=array[areanums-i];
6 P$ y3 g& ]) a% w, z        array[areanums-i]=temp;
  f! L5 v' H& p$ u% w9 g        max=0;
& K' h/ Z$ `! Z' y    }
' u2 z, {# v# {) m) X4 p2 j}

厚积薄发

代码3：
* o' t" G% i& b$ N7 \7 h/*
- ^8 [+ [4 z0 {算法思路：
4 l! s3 ^3 E3 `% d: y6 w, ~（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
再加，该人的所有喜好度设为0，
/ F6 M9 [3 P( F8 D9 [5 J) q% X# H（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
(4)最后输出总喜好度。
3 V) p0 [) O" c- h0 v*/
#include<iostream>
; I  F, }6 w. G6 y' i. Gusing namespace std;
int b[3][3];//M*N矩阵
  z) N2 ~! r5 V0 u# x1 Wint a[3]; //区域人数上限数组
int c[3];
* N; s& O% G, q% F5 [2 q: y% N# l( s( rint temp[3];
int sum=0;
) W3 H; N+ @& `9 [* j% L: Lint max_num()
# N' `+ k5 N: X' W" M# `8 m{
    int max=-32767;
' u# n/ B. d9 u: V: _4 G# Q& c9 r/ {    int x,y;
% n, U5 n4 E' |7 B9 R/ c8 A    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        if(max<b[i][j]&&b[i][j]>0)
        {
/ ^1 P6 b0 b4 j4 p, Q* g) R            max=b[i][j];
% {& @: T- V( \9 L$ H, q            x=i;
) b$ O7 e8 J% |$ m) E4 X- k  M            y=j;

        }
$ s8 q2 u1 ]$ x9 f7 p' R3 C    }
   
  e( ~4 D* [: X9 ?  D: c    if(a[y]>0)
* f1 {% s9 z( q- m    {
4 Z1 i4 U4 C& i6 U: q        c[x]=y;
2 l4 X0 l' Q& w' H. `        //cout<<"c["<<x<<"]="<<c[x]<<endl;
# n( }: |6 a% R, F, }9 Z        sum+=max;//总喜好度加上添加
" |* P. d+ K2 k! [+ V        temp[x]=max;
        a[y]--;//区域上限人数-1
    }
; X  N. i9 j0 ~, V1 ]    for(int k=0;k<3;k++)
    {
- }" ]# }% K5 R6 G4 I: [1 Y        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
    }
    return sum;
}
int main()
{
   
    cout<<"input 3 zone's limit:"<<endl;
  i# B, |5 o' t    for(int i=0;i<3;i++)
    {
4 T5 M& w3 T* p2 {+ N        cin>>a[i];
    }
    cout<<"input 3*3 actangle:"<<endl;
# M& G/ d' ?4 b' t    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
' U4 M$ O5 }# s, X! y    {
0 Q- I8 k- i% c/ \/ n  Z! @2 j* D/ R        cin>>b[i][j];
    }
4 N* K: g6 L  |6 r. p( W8 v    for(int k=0;k<3;k++)
$ F7 a; [9 `1 ?+ e1 X& w    {
+ n& u, o+ }$ j( A* ~        max_num();
7 G5 M- ^  [; O  g7 w5 e7 d2 i) X& d    }
    //cout<<"sum="<<sum<<endl;
    cout<<"sum=";
    for(i=0;i<3;i++)
    {
        cout<<temp[i]<<"+";
; U' C& T0 D% J7 ]( E    }
* G+ f; d8 ?4 s5 y+ H& n    cout<<endl;
1 H4 a1 `9 l& {& b! R3 P. l7 f    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
  K, @5 z/ ~3 {    }
    return 0;
}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
数学中国社区分享快乐！
* t1 G' k  S6 C+ \

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！