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

厚积薄发

座位调整

" d( L4 `$ w. o# o! s题目描述：

' r! p& a" ]$ q  \2 G' s% S百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。
: q; Y0 a2 c  A9 n" T7 }5 H4 s- e
( e+ a0 P$ d$ f- ]5 g调整的方法如下：
% U1 m' L7 S) e  j1 }: r) J
& y- C# m: A! R7 R# w% T1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。

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

3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。
) j9 X6 E  F3 |1 C1 B. q3 L' d
& v7 K. h' K8 h0 o0 e. c数据输入：

3 P7 d6 m1 K+ |5 D: D第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。
7 Q. P9 E! z8 y9 s; ~2 M
第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。
: m. }2 @+ s% O% K( ^) M
1 L" S7 ^( N& {9 v$ f紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。

答案输出：

7 H! ^  i, R$ O* C9 b对于每个测试数据，输出可以达到的最大的喜好程度。

输入样例

8 n3 h( }% R9 l9 g3 V# B. M1 z! |
3 3
4 F' O1 b% W) n/ [) |2 v/ k
; o) D9 [; }/ E) w/ a1 1 1

  T/ b* w) v6 G100 50 25
" L9 U; ^) s! h8 \
100 50 25

100 50 25

, }6 {1 y5 U& E3 v% Y6 P
- n  R$ I; K9 `' u* z输出样例

: Q0 Z( J7 M# z! G4 b
7 K# w9 a8 p" r; T# I175
" _: K" W) b/ u8 }# F- m
) ]" }/ \$ V3 m3 Q: A- L" b

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

厚积薄发

! H# h2 j5 A/ }/ F
#include<iostream>
. `0 u1 U# Z' I: ]using namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
int sum=0;
7 R8 r* j  H7 W2 `0 z& @: w3 f- V9 _int max_num()
{
: W: e% @+ _1 g5 u( N; h    int max=-32767;
$ a8 U' B: ~0 B5 \9 [! n  I    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
  Y& f+ Q' W& F    {
        if(max<b[j])
  A* Z. p$ D: K4 Y7 E  ?3 B) x        {
7 e, Y- a2 i" X; y1 ]- d            max=b[j];
            x=i;
            y=j;

/ p  J$ x6 V9 n" p        }
0 z2 k3 [: ^# x    }
4 \- Y* W& U# |, _* T   
$ U9 k6 J, F9 O; ]) e5 x    if(a[y]>0)
+ V# a8 K( t( Z6 T9 K    {
        c[x]=y;
        sum+=max;//总喜好度加上添加
6 C9 S6 ~1 q7 c9 Y- i8 q        a[y]--;//区域上限人数-1
% U! v' X3 C5 U        for(int k=0;k<3;k++)
        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
( K4 P' D$ s  \6 \! p* c  g2 Q    }
+ `' K$ k* n* K1 g) W+ X    else
    {
        b[x][y]=0;
+ `% H& e. v8 X+ V2 J$ x3 |- T    }
: h5 D- c- M- z$ x   
    return sum;
$ |8 Y/ U. l% c* l}
* u  u  g- B. V* _2 `$ F4 Dint main()
6 d: Q' y' F; C{
   
2 ~/ W0 x# E1 L+ }9 Z+ m2 x    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
    {
$ k( s! r  C. t7 O2 m/ Y8 H        cin>>a;
    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
  Y) c" {4 y3 i- o1 y  S* y    {
        cin>>b[j];
    }
$ D  S- z8 Z9 N; z/ d2 _    for(int k=0;k<9;k++)
    {
0 {) x7 G) {6 K. S$ G4 ]: r4 c" w1 B        max_num();
    }
4 L: C  I7 a  {   
    cout<<"sum="<<sum<<endl;
    cout<<endl;
    cout<<"reslut:"<<endl;
) l6 w' s. B5 M3 y" l! I$ }2 R. }* h* x    for(i=0;i<3;i++)
    {
" W0 K' K* S' j  B2 J4 w        cout<<"people "<<i<<" go to zone "<<c<<endl;
6 y" K+ A9 A0 f: X; W6 P5 H" _3 m    }
    return 0;
}#include<iostream>
using namespace std;
5 s& x0 u, ^& ]9 k4 mint b[3][3];//M*N矩阵
% |3 C% L+ v2 ?( |7 V0 Fint a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
int sum=0;
int max_num()
{
  B/ ~- s7 a/ Y0 l4 q0 ]    int max=-32767;
9 m: E9 C! n' W! _    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        if(max<b[j])
        {
; W5 v7 t, w( ?$ m            max=b[j];
            x=i;
            y=j;

        }
    }
8 U" c4 w+ I0 q: @" W+ ]# K   
& s' j$ P! Y1 _) O    if(a[y]>0)
  l( t3 D# |3 N    {
        c[x]=y;
        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
0 ~" J% F5 [! D3 c+ x, n        for(int k=0;k<3;k++)
        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
* b3 [5 y" \' c9 P. A+ }; j" Z/ |        }
    }
    else
0 O2 I3 n( h) Y* z3 c9 H* y6 |# S* \    {
        b[x][y]=0;
    }
   
8 ?+ l# g" u7 n; `8 C    return sum;
}
int main()
# F* t- g5 ]3 b6 G) @" E" x# A{
4 ~/ x: _; a& P4 k* n( i   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
    {
# @' V0 s7 ^& W9 h3 P        cin>>a;
0 o5 f7 h: t: e    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
4 U4 A( e; Q0 }/ T( H7 `    for(int j=0;j<3;j++)
    {
- g* t+ {2 \% l* Z& R        cin>>b[j];
  [- @2 B% s1 k6 E0 p    }
3 N4 X# I4 u* @2 B/ a1 m7 k    for(int k=0;k<9;k++)
, _7 K) x  S, H7 f$ m8 N    {
        max_num();
    }
   
3 W3 F3 [, N. T+ `) I' J    cout<<"sum="<<sum<<endl;
    cout<<endl;
2 K5 ^2 r5 o6 _. g4 x! Y9 k1 e1 ~7 u  q    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
8 {& @9 D# E& I, ~9 S. d        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
9 H4 E) C0 `, |# j1 r. c0 i; R    return 0;
}

厚积薄发

编程代码二：
#include<iostream>
#include<cstring>
- |4 b) G/ A  ~7 K#include<ctime>
using namespace std;
class ifo{//矩阵的元素
    int clerk;//员工号
$ w+ [4 U) b2 e4 j$ B5 |6 Q4 V    int area;//区域号
' @) N8 a, ]& h  q( |    int per;//爱好度
7 z. J% }6 n5 `' y/ \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;}
" v& L& I9 p. P: ^2 J    int getper(){return per;}
    void setclerk(int i){clerk=i;}
2 H! }0 T  X$ w2 c  [    void setper(int p){per=p;}
2 Y( b0 j2 A+ b6 W# }7 L2 S$ O3 n    void setarea(int a){area=a;}
};
1 |0 C: l5 ?6 M7 C5 zclass area;
& @1 [8 a% }; q6 p: V7 k% u: sclass clerk{
    int areanum;
    bool isin;
7 o$ D4 M, b" i    int inarea;
5 }0 `- D0 ?3 _& m; ]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;}
( \2 Z$ V2 p  N" \5 `/ _5 R0 [};
class area{
    int num;
    int max_num;
0 @. C: O$ U/ l7 b  mpublic:
- o8 L3 l4 W: u! h4 W    friend void set(int);
    int getnum(){return num;}
7 b1 P8 b; ?; f) M0 S& ?) m& E( v' R    void setnum(int number){num=number;}
    int getmax_num(){return max_num;}
    area(int number=0){num=number;}
# x& Q( w& t6 Q8 K0 Y    int getclerk(){return num;}
& Z/ V6 U+ ~, Q; R  n4 {1 u    void addclerk(int ps){num++;set(ps);}
5 I  P) u  n; ^) c};
void getorderbyper(ifo array[]);
int areanums;
void main(){
    //input
    cout<<"输入区域数：\n";
& y( a# B* m( s/ T. s    int area_num;
    cin>>area_num;
    areanums=area_num;
    cout<<"输入员工数：\n";
    int c_num;
. {# j( E$ p* z1 D) x* l    cin>>c_num;
" p% Y5 T3 |, ?& T' e; \    cout<<"依次输入每个区域能容纳的员工数:\n";
    int *max=new int[area_num];
7 X6 E# f4 s1 J    int nownum=c_num;
    while(nownum){
' |  O# J' @! G, Z        for(int i=0;i<area_num;i++)
        {cin>>max[i];nownum-=max[i];}
, J* ~, G* [% g# X        if(nownum>0){
6 J" Y* [$ O: X( P9 ^            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
' \% ^7 v" k5 E            nownum=c_num;
        }
0 k! F+ W* j# y; s4 \        else nownum=0;
. Q7 }  p; h2 H# E6 o" v' t& l4 Z    }
6 J2 m. Z8 a! I# O! g0 d- \. H7 D    cout<<"按行输入每个员工的偏好：\n";
    ifo** per=new ifo*[c_num];
/ ~6 Y) l  ]. J" l  ?: {    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++){
9 f7 {& ]+ x- X% y- ?        for(int a=0;a<area_num;a++)/*
* X7 O6 e4 }5 W        {    int p;cin>>p;per[c][a].setper(p);
            per[a][c].setarea(a);
; |$ W5 w  F2 }) T% E            per[a][c].setclerk(c);
        }
        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
4 T$ Q( d! G; Q9 `' v        {    per[c][a].setper((rand()%60)+40);
            cout<<per[c][a].getper()<<'\t';
& Y8 ]- v" c0 N4 |$ b& \        }//测试时懒得输入，故以60-100的随机数代替。
# d+ g; \0 ]2 Y( ]" W-    cout<<endl;
    }
; h1 J4 K& N6 @5 J- [/ r4 v    //output
        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
( R' q* T" o' N/ g# |$ e        clerk* people=new clerk[c_num];
: ^3 M- j: q- q. n        area*  areas=new area[area_num];
        int totalper=0;
+ \7 d+ ?, e, s/ Z- M: l- S        for(i=0;i<c_num;i++){
/ ~  Z+ d9 }  L! m. C4 h            for(j=0;j<area_num;j++){
            if(areas[per[i][j].getarea()].getnum()<areas[per[i][j].getarea()].getmax_num())
+ O9 C$ ^* e* L# A3 [+ V. Y                people[i].set(per[i][j].getarea());
                people[i].setisin();
' O" a4 O0 m1 l: _9 i# M# e                int number=areas[per[i][j].getarea()].getnum();
% u. k( p. O- m& }9 L% ?. d6 d  Z                areas[per[i][j].getarea()].setnum(number);
                totalper+=per[i][j].getper();
  M( n" U2 ^; C+ E                break;
            }
        }
        cout<<"能达到的最大喜好度为："<<totalper<<endl;
1 d) d- l. Z+ c' Q, z. p}
void getorderbyper(ifo array[]){
    int max=0;
    for(int i=1;i<areanums;i++){
( q; e9 O; z2 H' V/ u7 z        for(int j=0;j<areanums-i;j++){
9 H' V* h+ H. ]        if(array[i].getper()>array[max].getper()){
/ G" b8 ^- f9 j            max=i;}
        }
& [! I5 a, k& X: e) m; y: E4 _        ifo temp=array[max];
. n3 J! U& N6 j! o  Y4 J0 ^! d7 O        array[max]=array[areanums-i];
* e3 T3 X' F7 k; i) D3 V+ Y6 c        array[areanums-i]=temp;
        max=0;
    }
}

厚积薄发

代码3：
/*
算法思路：
8 [( v. t/ b9 E$ |, H& Z（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
再加，该人的所有喜好度设为0，
$ P8 X4 [4 t8 o" s" q: c. G% N/ e（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
(4)最后输出总喜好度。
*/
#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];
int temp[3];
) Q" b2 A  ]* y7 Uint sum=0;
" R  h1 F, f; r) \; H+ x! W0 B, Iint max_num()
7 Y8 d5 k. W- G- X( c: t) Y{
! |& q0 V% D* J% L$ p    int max=-32767;
    int x,y;
) |* `$ x  T6 ]: p- P    for(int i=0;i<3;i++)
, X. d' ?- f% }: {, l4 d0 L    for(int j=0;j<3;j++)
5 \# f' ^9 e8 _" y) L    {
        if(max<b[i][j]&&b[i][j]>0)
1 v5 }. _9 j. w8 g9 k        {
  K9 U/ x' Q% ^            max=b[i][j];
            x=i;
            y=j;
+ \% W' t0 a6 C
        }
    }
' n2 X* q! ]8 b   
/ e: J% P6 l, c: e    if(a[y]>0)
    {
        c[x]=y;
) f# m5 Y* [* H# I$ p, x/ p7 ]        //cout<<"c["<<x<<"]="<<c[x]<<endl;
        sum+=max;//总喜好度加上添加
7 f7 i! O0 U  h/ V* G        temp[x]=max;
        a[y]--;//区域上限人数-1
  e  O! a. u; v8 J    }
    for(int k=0;k<3;k++)
: u1 E! F3 @3 r, Z( _- d0 u    {
        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
    }
    return sum;
* ]( R6 o; c( n- A8 L}
* P. q: @8 H/ C, j9 |' d; gint main()
8 m: u! B6 t1 [' C0 X) G4 ?{
   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
" D6 k- F6 l6 c3 G) y    {
/ C! H6 e5 O$ U* K/ k  P        cin>>a[i];
# ^6 K8 [6 S% @0 r. K$ s    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
+ y0 J! w7 E" ~% ?- ^5 |  o    for(int j=0;j<3;j++)
    {
        cin>>b[i][j];
    }
: r! U8 F+ C) o; M" t$ s, V    for(int k=0;k<3;k++)
- W$ M4 p2 ^2 I1 I7 N    {
# }) g) [; G! y6 K5 s; l/ u$ G* @  B        max_num();
    }
    //cout<<"sum="<<sum<<endl;
9 H+ O: m  v) z1 G( @  z    cout<<"sum=";
/ I2 I* _; u+ p* ]) q    for(i=0;i<3;i++)
% w& U; y0 f5 O4 e% H9 H    {
' a0 A/ {" Q: m1 j0 z5 {        cout<<temp[i]<<"+";
- X! N. g+ x, `7 Z5 D+ r9 N1 C; a    }
+ i% t% b, q+ S    cout<<endl;
  H% R3 a6 x; P% @1 M    cout<<"reslut:"<<endl;
$ l6 a( i, l, y7 K! f" a    for(i=0;i<3;i++)
    {
' Y' E+ {  S2 V1 [        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
    }
    return 0;
: A3 l! n1 w& L* H" K}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
数学中国社区分享快乐！
( Z  K( v9 ^5 b* ~7 R3 W

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.
8 |+ O4 \$ Q* F  u# y

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！