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

厚积薄发

座位调整

题目描述：

0 F  i! D3 g: C9 r; c6 K! ~百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。
/ V5 q4 d6 u) i' q
' r" e* g: v! i/ f8 X$ l调整的方法如下：
. g7 O4 A6 s5 f8 e
1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。
9 x8 Q6 {9 m/ ~0 _' G, K" e
2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。

3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。

3 S+ v- l9 L& D- M% Y数据输入：
& N' u% |: t, n, K" i; x
第一行包含两个整数 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 个区域的喜好度。
* T3 N% Z. J6 F' D1 k, J' l
- m7 i& m- c1 ]+ |+ _! z答案输出：

3 C, P0 h: l$ q- g对于每个测试数据，输出可以达到的最大的喜好程度。

1 o1 ~( i$ P# O' R, u% @输入样例

: D" d" m( O# F" W+ i( n" M
: ]' J" E- \& d* A* {! C4 F" |3 3
! I4 A: I& W) y
1 1 1

100 50 25
$ N* s9 z" V0 P5 u! S- ]* a+ H- {
100 50 25

5 q% F5 X/ t+ D100 50 25
& ?4 E  T4 l* K

$ M7 _) o8 ?4 ~5 A% |- K: j( t: E
输出样例

4 o8 f" J+ m6 S$ v' K; m( U
175

  Y# ?8 ?( `: t

7 Z: `# ~8 Q1 `9 {# z: l; j数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175

厚积薄发

1 {, q* F  G+ B/ E/ c7 Y
8 F8 v) s4 W3 w# b: b3 d#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
' L$ E8 |9 m5 Q" y! g5 I, Kint sum=0;
$ B/ L1 v1 G8 [# b' \2 Qint max_num()
( X) t$ S* r1 J* |+ F/ z; L6 c- m{
0 d2 V2 a* ^" w; [8 l    int max=-32767;
" R  m% \' X: x& [& f+ C    int x,y;
8 j* Y$ [4 i2 e9 k1 V% u+ i    for(int i=0;i<3;i++)
. p: X$ @: H" Z    for(int j=0;j<3;j++)
: l" r9 z. O$ V5 o+ G1 \3 ~& K6 L    {
        if(max<b[j])
! Q  F# I2 B* c0 Y        {
8 ]& D7 b+ }' w, ^) z. y* k            max=b[j];
" b+ u* J8 I/ T4 ^. i4 S! ^7 s8 x            x=i;
# k' B$ i; ^/ R8 P6 @7 `            y=j;
  c& q5 R; K  @7 B
        }
    }
+ p; Q& s9 p" P3 J! f- t   
+ B! b( K/ F4 p9 w4 w    if(a[y]>0)
3 |' J: C) s" |' T% W4 R    {
- c0 ~6 x7 {' @# f        c[x]=y;
% y( m+ @# u8 U% o- V- R        sum+=max;//总喜好度加上添加
2 f4 w; F1 n( V/ b2 ?1 c        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
7 F0 @% A2 `; C0 B5 ~0 ^, }; _        }
    }
) w: M: z5 \1 O2 w    else
8 t5 g2 r* n$ D5 v    {
4 C* I# {4 q! P+ m  d" Y9 h- k        b[x][y]=0;
- ?& M  h/ J- K* H    }
+ M7 |/ I- k! O   
    return sum;
+ D2 `7 s, V  H; [7 m}
, @5 b' M) v/ g5 tint main()
{
   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
    {
5 W1 X* q! @7 P  s* q1 `- [' f        cin>>a;
    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        cin>>b[j];
- V& W- W/ }4 N2 ^/ T- }    }
    for(int k=0;k<9;k++)
; F8 X) T! a' h' [3 l: A+ E    {
        max_num();
; Z- @4 T5 A6 m' R( z2 w3 U$ o    }
; u& n/ K/ H- R% t0 F0 ?6 e  ?2 h   
: |7 V8 _6 t* p3 e% T    cout<<"sum="<<sum<<endl;
( X; t; ~4 n% m; y$ m" E    cout<<endl;
6 a2 Y3 ?7 q7 i* P( R    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
9 g2 T6 p7 ^# v( x3 H, O        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
    return 0;
}#include<iostream>
+ D8 A( k/ b; j( ], |using namespace std;
int b[3][3];//M*N矩阵
* j% `  `7 C0 {, F4 e& Cint a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
; _& |1 s) N! Z, e  o% N3 ^/ S# kint sum=0;
/ e. ^9 v' U% Mint max_num()
{
    int max=-32767;
1 A6 j8 M) S6 I& c' s5 w    int x,y;
2 S. s3 H2 I3 o# V/ d    for(int i=0;i<3;i++)
' g  m7 |  F  i3 p    for(int j=0;j<3;j++)
    {
' h# n$ `, y* C  [# b        if(max<b[j])
, {% A: U/ Q3 k        {
            max=b[j];
8 ]& M. D" Q+ s            x=i;
            y=j;
% r1 r9 `# w1 |, z( q( I) r
        }
    }
   
) m, U6 \, s. h0 l1 J3 e0 N    if(a[y]>0)
    {
        c[x]=y;
        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
    }
    else
8 K; B3 z  K0 G    {
        b[x][y]=0;
    }
   
    return sum;
; X5 E7 a+ M/ E  l/ W6 X: `}
5 R/ U6 g2 y* Z; E! I2 x# k) qint main()
{
   
$ V; y% }) a* k9 e2 H    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
9 s& C! p1 g5 z    {
0 g" I) b- l1 m$ E7 e        cin>>a;
% T0 \5 z8 N2 k- Q2 B2 N% M    }
! |  d+ V2 R$ v( n    cout<<"input 3*3 actangle:"<<endl;
/ k# M2 [7 }9 \; s- A+ D    for(i=0;i<3;i++)
4 c3 S% _  L& y% Y* |; ~5 Q7 G    for(int j=0;j<3;j++)
    {
$ L# Z, Q9 M# I        cin>>b[j];
# M% ^, G* q% _+ l1 D    }
4 t$ D! U: R+ S* L    for(int k=0;k<9;k++)
    {
        max_num();
    }
   
    cout<<"sum="<<sum<<endl;
    cout<<endl;
; L' @1 a5 a3 Z4 z$ y    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
7 t/ J# x! r3 J) h" ?6 f1 z6 J    return 0;
$ j# e( C2 R4 U# q* b" d# E}

厚积薄发

编程代码二：
; m% @/ M2 v* G. N#include<iostream>
! {* e0 a  J) i# C% g5 V2 v1 k#include<cstring>
#include<ctime>
using namespace std;
class ifo{//矩阵的元素
    int clerk;//员工号
- B+ w( _/ a2 J) P3 W3 k    int area;//区域号
% u4 ^0 `' r0 I. N+ p) r7 s    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;}
3 i: p* X! o! v( Y* a( r4 e    int getper(){return per;}
" @. b" z8 l- \: i0 ~    void setclerk(int i){clerk=i;}
3 Z, R- T/ T* r" `! N) G    void setper(int p){per=p;}
# f8 E( \; u% \    void setarea(int a){area=a;}
8 u6 O3 ^: }' V/ q, b};
class area;
class clerk{
    int areanum;
) q8 P. f$ C$ j- p$ P    bool isin;
    int inarea;
3 N/ Q8 O3 `+ q$ U' }* Tpublic:
1 h! E% e3 A* p. L# u' _    void set(int num){isin=true;inarea=num;};
    void setisin(bool b=true){isin=b;}
& Q" e4 P8 N- P0 t4 {/ z6 I. F    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
* P: B& w: _0 U+ C* e1 y};
class area{
    int num;
2 `  X9 R/ V7 p9 b    int max_num;
# [4 l/ e8 c4 u0 C2 Jpublic:
    friend void set(int);
+ N+ r. q9 b% p& c: E- _    int getnum(){return num;}
; ~$ p  R% U2 \7 e( i    void setnum(int number){num=number;}
    int getmax_num(){return max_num;}
    area(int number=0){num=number;}
# Q6 B' O$ |5 y2 c3 i( i' B    int getclerk(){return num;}
, K& ]# I6 k8 U  d2 Z  l+ V/ K    void addclerk(int ps){num++;set(ps);}
};
' H) F( K9 Y; `, Rvoid getorderbyper(ifo array[]);
int areanums;
void main(){
    //input
3 M1 K+ }' D* y+ q4 M$ P/ G    cout<<"输入区域数：\n";
    int area_num;
    cin>>area_num;
    areanums=area_num;
- a& W' I+ m5 ?6 F    cout<<"输入员工数：\n";
    int c_num;
  N1 c' h3 q$ g9 _+ f" _    cin>>c_num;
( x% F4 J. }, j! L. R    cout<<"依次输入每个区域能容纳的员工数:\n";
    int *max=new int[area_num];
    int nownum=c_num;
    while(nownum){
2 C  \5 ]' n# ]' p        for(int i=0;i<area_num;i++)
/ Z/ f$ c6 l0 u0 [3 @' h% g9 j4 I        {cin>>max[i];nownum-=max[i];}
) i4 I/ |; V9 m! y1 q" A7 T        if(nownum>0){
: ^# o' ~; [0 R# ^            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
            nownum=c_num;
        }
' q/ x; l6 X2 L( O        else nownum=0;
2 n  _: i9 `. |" D1 u7 t    }
% u; |+ i% C7 F/ s    cout<<"按行输入每个员工的偏好：\n";
+ \' ?$ V$ F+ l! G/ W# D    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++){
+ v: @) D- [- X) Z) G" W        for(int a=0;a<area_num;a++)/*
        {    int p;cin>>p;per[c][a].setper(p);
9 P: z4 R. z" U; p% r% j% A- T7 a            per[a][c].setarea(a);
            per[a][c].setclerk(c);
; z- ~2 B% }9 h4 w        }
        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
: l6 v; p7 u/ p1 I! q' Y        {    per[c][a].setper((rand()%60)+40);
            cout<<per[c][a].getper()<<'\t';
        }//测试时懒得输入，故以60-100的随机数代替。
8 [+ |% {7 V* G- Z+ k-    cout<<endl;
    }
, D) C. v0 i1 l$ b, ?    //output
        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;
3 N" o# z5 c, T8 ]        for(i=0;i<c_num;i++){
; N2 ~, E, C/ u# Y            for(j=0;j<area_num;j++){
2 S' B3 E$ G! W" |6 x- c' }            if(areas[per[i][j].getarea()].getnum()<areas[per[i][j].getarea()].getmax_num())
6 {4 {7 K/ ]4 D- m9 k( I/ o                people[i].set(per[i][j].getarea());
                people[i].setisin();
                int number=areas[per[i][j].getarea()].getnum();
                areas[per[i][j].getarea()].setnum(number);
                totalper+=per[i][j].getper();
: }3 N6 U5 M' K, c                break;
2 r4 T+ r6 |0 L. w& F            }
        }
5 u7 \! a% ]2 y. a        cout<<"能达到的最大喜好度为："<<totalper<<endl;
}
void getorderbyper(ifo array[]){
    int max=0;
8 \5 F5 p7 \4 L3 q% M; ~# x% B( b    for(int i=1;i<areanums;i++){
! n6 h) B2 @2 ~% g: q& d& t3 C! q: ~        for(int j=0;j<areanums-i;j++){
1 ~1 O- f5 G% Z" @' d/ y        if(array[i].getper()>array[max].getper()){
, O6 f) C! E3 a1 X0 _/ `! e            max=i;}
8 g0 C) i7 X& Y$ U. C! I: A& c& o        }
        ifo temp=array[max];
4 k6 V! u' p6 D; i4 H% m        array[max]=array[areanums-i];
  b4 ^: Q+ G* i. [        array[areanums-i]=temp;
        max=0;
    }
0 U  ]& e! c. F. @' X, O}

厚积薄发

代码3：
2 q8 ]: T" @7 K5 q+ s" p" @5 C/*
1 i4 l1 Z7 l& s# W算法思路：
（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
# j% D. @" C# F3 u; [: i/ t9 s6 z5 k# M再加，该人的所有喜好度设为0，
（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
, z# k& x2 |. T) ~: g6 J8 {（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
. M! x% W& [! e(4)最后输出总喜好度。
6 w9 R; y( X; E5 x( I*/
3 q! ?% f. o; x5 n#include<iostream>
using namespace std;
% c; p2 M, o: a* mint b[3][3];//M*N矩阵
7 K1 H1 C& |; y! r* F$ d5 aint a[3]; //区域人数上限数组
! M9 q3 h1 f8 w2 sint c[3];
int temp[3];
$ O' X% w9 T& Q, M) Qint sum=0;
* I; A6 V7 s( lint max_num()
{
    int max=-32767;
4 O9 A; l  ~0 L/ U    int x,y;
9 Y1 L7 c8 ~+ d' b( n4 t& h! r- O    for(int i=0;i<3;i++)
5 D! q% T% ]# o- h) d    for(int j=0;j<3;j++)
    {
* x3 u& m2 M# l; {/ q0 E        if(max<b[i][j]&&b[i][j]>0)
( x  a1 l( f- ]* Y( J; y. q        {
            max=b[i][j];
            x=i;
) \. w& g/ E) F+ F% R& ~            y=j;
; a! @/ \+ G; \) b- g& Z' w
; X( d$ V- u, _: I7 v+ ^/ B  o* v        }
    }
, R* k# f! `) K, G) k- t   
    if(a[y]>0)
    {
        c[x]=y;
" b9 }7 ?" F1 h4 ], p        //cout<<"c["<<x<<"]="<<c[x]<<endl;
2 ~: i! I0 [' g5 j( F        sum+=max;//总喜好度加上添加
9 w: p/ ?! e  d- [. X        temp[x]=max;
        a[y]--;//区域上限人数-1
    }
    for(int k=0;k<3;k++)
    {
        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
    }
: S9 b: u1 s! J    return sum;
  ?0 @# c' z+ i+ O& b7 V}
3 v5 }+ U6 A2 t  Z3 P- s5 Dint main()
{
   
    cout<<"input 3 zone's limit:"<<endl;
: b8 k$ q/ f+ g2 M/ S' K, t0 D* s    for(int i=0;i<3;i++)
9 J) _( x4 @* H. a$ ]/ N    {
        cin>>a[i];
& ]( }+ m4 V$ t, ]# ^1 Q' Z7 g    }
9 Y2 e$ L$ N. j# L$ q    cout<<"input 3*3 actangle:"<<endl;
% f8 B3 o- Z" Z    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
, k' ], S+ ?2 x3 y        cin>>b[i][j];
- l" T- T5 @7 V" _7 U+ t* q    }
    for(int k=0;k<3;k++)
    {
2 J0 Q( A- B) R% x9 |1 v        max_num();
    }
/ m8 l; v5 h& A    //cout<<"sum="<<sum<<endl;
) z7 d. R: ]3 {, r9 A8 h1 S9 J    cout<<"sum=";
    for(i=0;i<3;i++)
    {
, n8 ?- E4 n2 w. ]1 X9 d; O        cout<<temp[i]<<"+";
, \9 X% l' ?5 ^$ e    }
& @! [* H& P! r% W, _4 s    cout<<endl;
    cout<<"reslut:"<<endl;
: Y3 l# l. w9 R* B6 w. m- T0 h    for(i=0;i<3;i++)
- @! t: F9 P9 r1 ]7 o/ O    {
# S* O: }3 _2 T) D' @8 F        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
    }
    return 0;
}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
数学中国社区分享快乐！
9 D5 Y& W  f5 b/ O

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.
8 m& ]+ J8 P9 M( Q* R

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！