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

厚积薄发

座位调整
6 e7 @7 j) e, J
: M8 L9 `1 G- q" ?题目描述：
  O  S) u3 g9 M& g3 ]
" k6 P6 J+ G% D4 W" x1 u3 h百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。
/ K+ c1 d' L4 T
调整的方法如下：

4 A4 {' [$ b  S4 x" y+ j8 b% }1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。

2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。

3 q( @. r4 L, I! ?9 a3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。

" l/ K8 j- S( g7 o* Y* Q- ?3 i数据输入：
: Q& }! i5 ?2 S7 [
) w! U. @: V6 r+ [9 I6 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 个区域的喜好度。
6 v8 b6 @; M' M% o* r7 I
* `) H) \! m; J' `. v答案输出：

0 b5 J4 U3 M& R6 e( W对于每个测试数据，输出可以达到的最大的喜好程度。

输入样例

1 A5 T4 L% Y6 W# ]' j1 x3 3

& A/ I" Q3 G/ j3 F1 1 1
$ d% p( J+ i. _) N" k( B- ~
100 50 25

* V1 @  o6 D# ?100 50 25

100 50 25
: m) S" L3 w: F) w

% A$ _3 {5 N4 v& K% `& V2 T0 e
2 y+ q: ~( }5 {9 m7 k输出样例

5 w1 E8 ~1 E; {' d4 ~5 b175
- E( K' f4 ~6 F5 U# `

4 B" B4 L! h' l7 V
8 t1 U8 U/ T. A  ]. u0 }8 N  I  o数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175

厚积薄发

& P8 s3 ^5 l4 W# k: E* m5 Y
3 o9 N2 L% w9 s+ ^#include<iostream>
using namespace std;
7 Q" Z( q$ o  D! Mint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
/ G1 s" r7 p+ |8 hint sum=0;
int max_num()
{
    int max=-32767;
    int x,y;
+ _+ O5 x' G7 Z& C; o8 y1 P) ~    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
. v! u/ o7 {2 `1 z2 G; [2 N& ?$ ?1 b    {
        if(max<b[j])
4 L* C3 O( i+ k* u; s; U' |% e' i, P        {
            max=b[j];
            x=i;
            y=j;
) {( q3 R! K4 E( O
        }
( P( s7 m  r' {( m    }
   
  R7 O$ z4 E4 k/ O/ w3 ^    if(a[y]>0)
% [3 h6 u2 F$ j6 ~/ N' f    {
  p1 L" A( ]* D) @/ K- I# K        c[x]=y;
        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
. U  j- B5 _' s8 v& G        for(int k=0;k<3;k++)
% p9 z: O( i9 g- m5 D        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
' d4 [, E' s4 ]" |4 |        }
    }
1 C  m+ }: S( x3 `) n, h    else
/ l- v% t  o) W0 E& V    {
2 @( w. Q8 X2 B- k3 Y        b[x][y]=0;
    }
   
    return sum;
, q+ T! p5 c6 Z/ C' M1 h}
int main()
; ~& O" C7 m  J7 j) V{
   
    cout<<"input 3 zone's limit:"<<endl;
2 z9 z4 c: f/ E4 ]: H0 p9 `8 O    for(int i=0;i<3;i++)
- u9 m3 [8 p! P& K- [- H# V    {
  b% ^& b1 K" x5 H5 h        cin>>a;
    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
8 Q; H( I& u: f( e. O8 r+ Y9 G( t    for(int j=0;j<3;j++)
$ @! {7 T1 _+ [5 h$ z: t) @    {
9 j2 m2 ?9 O1 d( k$ d# ^5 k1 j        cin>>b[j];
    }
    for(int k=0;k<9;k++)
9 I8 ?0 Y: T0 Y    {
( w) E' i7 q! n2 q' u3 C+ K+ |        max_num();
    }
$ W  X  W& `/ P" u   
    cout<<"sum="<<sum<<endl;
    cout<<endl;
* D; _/ t( o9 m! a  ]: a    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
    return 0;
}#include<iostream>
  E% R8 J3 ]0 B% i: [7 `using namespace std;
4 y  q; o  d1 O+ u/ a5 Y% gint b[3][3];//M*N矩阵
( T; H7 b: U# ^! G2 rint a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
# [! }' [$ ?! h# D! Hint sum=0;
int max_num()
3 v  x  g# ~  n7 {{
  I  m2 ~) ?* `# U    int max=-32767;
, Z9 ]7 ]2 f, i  j" f    int x,y;
' L3 ?6 p% N3 L. m1 @( h    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
/ N- t, |  I' P7 V" J6 d    {
/ N3 p% ?$ K5 Q        if(max<b[j])
        {
            max=b[j];
  B7 Z5 u, ^* Y% `0 O            x=i;
, ~- P8 m1 U; h/ I3 u' s            y=j;

        }
    }
   
7 H+ m7 v' _2 |' R    if(a[y]>0)
' O8 B' p) N; F' Q6 q5 F, s    {
        c[x]=y;
        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
! {4 r/ [: o$ M# R$ t" i        for(int k=0;k<3;k++)
0 m7 W# U( X5 E1 U( Q2 l7 ~9 n$ ?        {
. B- E/ w9 d/ |$ K. {8 Y2 d            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
    }
    else
    {
        b[x][y]=0;
    }
& B7 \8 S, I. T5 }, h  X! H   
/ J* }- \  p/ X$ j1 k9 W    return sum;
  d$ i7 y$ V- D5 _}
& t# a* v. ^) t: g, K3 W0 Z6 x# y8 ?, }int main()
{
( p% U. j( n1 A' g6 Y( J   
    cout<<"input 3 zone's limit:"<<endl;
  h& V$ G3 D: {+ P    for(int i=0;i<3;i++)
' Q* h- D- ~( a2 {    {
  R! X" k6 c; G: h$ q% w. a5 A& T        cin>>a;
    }
    cout<<"input 3*3 actangle:"<<endl;
( n) f& S2 H, _1 E/ d1 T5 W    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        cin>>b[j];
; b3 y4 X* c; O* U. b  A    }
    for(int k=0;k<9;k++)
    {
; g  j3 x) E5 g1 p0 H  i( n# Y; P! Z; n        max_num();
8 e: n. Z2 d: i( d7 B    }
& D$ W3 `( n: Q   
    cout<<"sum="<<sum<<endl;
2 X5 y+ \! }3 w    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
    return 0;
}

厚积薄发

编程代码二：
#include<iostream>
#include<cstring>
#include<ctime>
using namespace std;
class ifo{//矩阵的元素
    int clerk;//员工号
- _; d5 s7 Z- z0 j( D    int area;//区域号
' z: i  ^* |# \" [: q2 j9 d    int per;//爱好度
8 }6 t2 W2 o8 A/ vpublic:
    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;}
! I6 ^  A0 x7 d. R, m, ?8 ^    void setper(int p){per=p;}
    void setarea(int a){area=a;}
: V: w, F- ?7 l: _0 v7 w8 c};
0 Z& H: n8 V" ^$ vclass area;
* s" B9 u- ^6 ]% |4 ~- z4 Fclass clerk{
    int areanum;
    bool isin;
& H% q6 {) w: Q$ [4 V# G& |- L    int inarea;
6 I# T5 @% \; R( xpublic:
0 E) ~  S% z, ]3 ~; a; y7 L: R    void set(int num){isin=true;inarea=num;};
    void setisin(bool b=true){isin=b;}
* G9 C  Z7 ^  n+ ^6 t6 \9 P    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
};
class area{
. V" @* D9 Y, j+ B$ z5 O/ [    int num;
6 n, a  I/ [! A    int max_num;
public:
: X- E# b! l' I; C! p    friend void set(int);
2 K2 r; ~+ c' `" o    int getnum(){return num;}
    void setnum(int number){num=number;}
    int getmax_num(){return max_num;}
2 k' ], I: t* z8 P' e% M8 g    area(int number=0){num=number;}
    int getclerk(){return num;}
    void addclerk(int ps){num++;set(ps);}
; [5 A7 d2 |5 X! M2 B3 ~" j};
void getorderbyper(ifo array[]);
) x7 ?/ [+ K" U/ c- N5 d( P+ Zint areanums;
- p1 \" o& o$ S8 Jvoid main(){
    //input
# q0 A0 U% P5 R7 u    cout<<"输入区域数：\n";
2 d$ ~9 }4 ^  l% P' E8 ]    int area_num;
    cin>>area_num;
7 y2 s1 F0 ^2 J9 x6 w; l  W    areanums=area_num;
    cout<<"输入员工数：\n";
    int c_num;
3 s2 Q/ K5 Q  D9 a0 m# Q( `    cin>>c_num;
  J. ]$ x1 h! t' \    cout<<"依次输入每个区域能容纳的员工数:\n";
- M0 x) K3 ?: \4 K# U) u1 Q    int *max=new int[area_num];
2 K: y7 V6 P6 H6 K    int nownum=c_num;
3 J5 _8 S$ w6 T$ S2 W    while(nownum){
$ U4 D; w" A  y        for(int i=0;i<area_num;i++)
! N( Z, m" c) E/ A' f& B2 u        {cin>>max[i];nownum-=max[i];}
        if(nownum>0){
            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
            nownum=c_num;
9 m) t/ y. E- \$ \& M* c        }
) }0 [7 l; q/ U2 ^2 a        else nownum=0;
    }
! X1 {3 d7 n0 ^8 }, ^8 K0 Q    cout<<"按行输入每个员工的偏好：\n";
7 n; Y( I. X' W$ R    ifo** per=new ifo*[c_num];
    for(int j=0;j<c_num;j++)
        per[j]=new ifo[area_num];
    srand(time(0));
9 Y+ J0 S$ C# f" ~! M8 }  w    for(int c=0;c<c_num;c++){
" `" F. a7 u" g7 ]        for(int a=0;a<area_num;a++)/*
        {    int p;cin>>p;per[c][a].setper(p);
            per[a][c].setarea(a);
            per[a][c].setclerk(c);
        }
        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
        {    per[c][a].setper((rand()%60)+40);
            cout<<per[c][a].getper()<<'\t';
: L4 Q( {2 }0 R3 l7 j7 }0 b2 W        }//测试时懒得输入，故以60-100的随机数代替。
-    cout<<endl;
  U2 [, J9 j3 m  g# v4 Z; S/ K4 W7 m6 p1 ~    }
( ^( g0 u0 J$ G7 `    //output
. S& i& M0 U1 G* Y: k% R        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
2 {; n3 ~/ K+ ?        clerk* people=new clerk[c_num];
- P$ h9 L1 H( ?" t" a, ^" j* o2 I        area*  areas=new area[area_num];
        int totalper=0;
/ q' p" h" p, O; w& X$ |2 s        for(i=0;i<c_num;i++){
: C  y* i- L# d7 Y5 E6 ?# S            for(j=0;j<area_num;j++){
  x& p* _' m, ]( |            if(areas[per[i][j].getarea()].getnum()<areas[per[i][j].getarea()].getmax_num())
                people[i].set(per[i][j].getarea());
8 k0 e- v% a6 D$ M: f                people[i].setisin();
+ g# ^0 O6 R* x+ m# |9 ~9 ^                int number=areas[per[i][j].getarea()].getnum();
                areas[per[i][j].getarea()].setnum(number);
                totalper+=per[i][j].getper();
- y8 R- [) |# T0 u: v' Y                break;
9 a- K  p; g$ o% A, X/ L& j& Z$ j            }
        }
" I# F& B; {8 V' I' G1 {) M        cout<<"能达到的最大喜好度为："<<totalper<<endl;
}
8 ^* B) ^2 A9 Q5 D9 l7 uvoid getorderbyper(ifo array[]){
    int max=0;
& |6 b- w% P: v/ C8 [    for(int i=1;i<areanums;i++){
" ^8 ~& {* l* K7 F2 P5 r        for(int j=0;j<areanums-i;j++){
        if(array[i].getper()>array[max].getper()){
# [& S1 H: ~7 c  M% g0 V$ Y            max=i;}
4 |; h( v. w& E3 W6 A7 Z% O$ J        }
2 ?/ f# J8 Y. A* K- W) c        ifo temp=array[max];
; G; j! |+ q8 j9 N        array[max]=array[areanums-i];
( d- J/ U7 U, o' m- Q9 W, l        array[areanums-i]=temp;
! A! y3 [* R6 Q) G        max=0;
    }
' s3 M4 P$ q  G}

厚积薄发

代码3：
/*
+ f7 T! K- Y" j) U! x( l算法思路：
3 t8 C( `# H: h& P（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
% `5 y6 w/ T/ s再加，该人的所有喜好度设为0，
（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
1 y6 I% Y( W1 S（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
9 T& o1 z- M7 o(4)最后输出总喜好度。
) L* d+ d6 v0 z: K*/
#include<iostream>
" i  c+ b4 n# }  iusing namespace std;
; U: q, ]3 U2 {: cint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];
int temp[3];
int sum=0;
! w# Q% S# k8 W* M6 A# Q3 Oint max_num()
( N0 ]: W- j) O' [{
    int max=-32767;
    int x,y;
- [% H. v6 ^5 y7 z  y# ]6 b4 Z% G    for(int i=0;i<3;i++)
3 ^0 M1 b2 [' s    for(int j=0;j<3;j++)
    {
        if(max<b[i][j]&&b[i][j]>0)
        {
) {1 _: ~1 ]) Y3 d$ N1 Y            max=b[i][j];
            x=i;
+ F" N! f3 s: n4 A1 G1 l( g+ n& U            y=j;
% t& n6 F7 `' @6 y: I) o
        }
    }
% P7 R# N. a' L/ W1 k   
    if(a[y]>0)
7 t. B3 V$ D, l: B6 x) M7 f9 I    {
, p0 T! \, j  l* |  |. h& {% |        c[x]=y;
& I1 W* o' i0 s3 P2 h) J4 `        //cout<<"c["<<x<<"]="<<c[x]<<endl;
        sum+=max;//总喜好度加上添加
; \5 Y% u7 m2 [  ~$ V9 V        temp[x]=max;
& k7 ?- M4 m3 F( E( p8 _6 _- K# o        a[y]--;//区域上限人数-1
    }
3 G  T8 \$ i6 {; h1 k! @    for(int k=0;k<3;k++)
    {
        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
: M0 M& D' |( ]. n2 r. i  ^: L) s    }
$ e* z: t% p3 k5 U% f- m4 v    return sum;
3 G4 E6 l- ?4 R4 D0 U; {3 O}
int main()
{
& u; V; T4 r3 P( j, p2 B   
3 a+ [) R& D0 S) C7 e    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
6 E4 p, A4 S8 _- q" l4 D( j    {
        cin>>a[i];
    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
( O% U" K6 W6 W    for(int j=0;j<3;j++)
) |0 g# V; a" _" K3 M    {
        cin>>b[i][j];
4 u% c7 v3 L% s  C' `1 h% B) a    }
2 `8 \. G1 G& ?( _: W    for(int k=0;k<3;k++)
3 `' @" }9 ?7 ?* d, y' F3 y. ?2 p    {
        max_num();
4 ~8 M5 @7 f- K. K    }
    //cout<<"sum="<<sum<<endl;
" X6 V/ V4 C; t  G$ n' U2 A    cout<<"sum=";
    for(i=0;i<3;i++)
5 l& o1 b; ]1 w" b0 k+ ~+ v5 B    {
        cout<<temp[i]<<"+";
    }
5 j- a. v) w9 p% A5 c% P    cout<<endl;
7 [2 g" w" M# w5 n4 W    cout<<"reslut:"<<endl;
: M1 ^2 z* f4 {8 v    for(i=0;i<3;i++)
    {
/ S3 x! J2 x  I& Q( C; {; W/ q0 k        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
    }
    return 0;
7 w8 y5 C  y% J  X}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
# l% D  j( ^# p, f! V% M& R数学中国社区分享快乐！
' r' y3 p( _  g4 Z! d/ @2 b

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！