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

厚积薄发

座位调整
7 z" I$ r3 l5 L
题目描述：

, t0 [. {$ D; {5 Q/ L百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。
* w$ o: i+ t: g6 X2 Q3 r0 x" j
1 w5 D) @- \4 ~7 u. t# g调整的方法如下：
7 {8 c6 \- H# x- L# N& U% `# M
1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。
! A$ L- N6 A6 a' m$ D1 b; [
) |. ]5 o2 c# ~' R! k" v7 d2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。

' z, S7 T+ z' t# }5 ]2 [; F3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。
, P- l/ d% s& i( i* I" Z8 A
8 A7 j* I; u9 w8 z数据输入：

第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。

第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。
* `7 B) n& @$ d! Y, x
紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。

答案输出：
4 M$ f' M5 E; V( r; K
对于每个测试数据，输出可以达到的最大的喜好程度。

( j3 J7 y6 F: h) N# t: c5 e1 p3 j, z输入样例

& z4 v4 w; `0 R7 y5 W
. p4 U4 I( M+ E; T& ]3 3

1 1 1
8 g0 }2 e/ ~/ o* A) ?4 x5 k1 n4 q
9 v) K' F5 u6 m! A( q100 50 25

100 50 25

100 50 25

6 G. A7 i0 I0 j$ G
5 p5 y, A9 A1 a* \' k, C输出样例

  ^2 j: H* o' Z. D/ {3 b/ `9 h175
: S1 J" ?! P% _
/ ]0 f, i: O. _! o

' I# a4 X! p/ V' V' o6 M% h6 k! i' m
, l0 n  d* K) ~1 |$ b+ ]& Q数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175

hbdkfk2

看不懂！！

久玖九王

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

schnee

必须顶！！！

ehi28

嗯,不错,支持一下.
3 F" J9 y; ^1 L3 ]

_Amy_

程序最头疼

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
数学中国社区分享快乐！

厚积薄发

代码3：
/*
- ~; v7 y* v) s! n算法思路：
（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
再加，该人的所有喜好度设为0，
（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
$ W2 Z3 d& l/ x0 G% g1 C5 q" a" L: S9 r(4)最后输出总喜好度。
*/
9 D$ P- y  c3 f" n3 y$ [% @, @#include<iostream>
9 N7 i8 a# ^; W) G2 c# Busing namespace std;
int b[3][3];//M*N矩阵
5 F# a! m% z8 p+ \9 V/ S, iint a[3]; //区域人数上限数组
int c[3];
9 J2 z# ]% X' Y4 f/ s0 f) ^int temp[3];
int sum=0;
' [0 D' s! v! h8 T  o' f% hint max_num()
{
; r& U" A+ J. A, r9 S& a    int max=-32767;
) q, `8 @, ]8 L! v, l3 v- n* w    int x,y;
    for(int i=0;i<3;i++)
3 ]6 ^6 G9 Q" W    for(int j=0;j<3;j++)
. _3 e9 I% E! o* p1 h% G  D5 N    {
        if(max<b[i][j]&&b[i][j]>0)
        {
# x# ?) B3 K6 B0 b            max=b[i][j];
  {  u% w$ h- E4 c3 |6 B            x=i;
            y=j;

  i6 `: K" d* X9 S        }
    }
   
4 m4 u4 e) x8 m, S+ N    if(a[y]>0)
; ^4 b1 m2 U5 a7 Q; h    {
        c[x]=y;
        //cout<<"c["<<x<<"]="<<c[x]<<endl;
        sum+=max;//总喜好度加上添加
: ?: v* ?% I" Q/ D. S        temp[x]=max;
        a[y]--;//区域上限人数-1
8 K1 \5 ~" X; M' w    }
$ t7 x6 G5 X* {) z: B% J    for(int k=0;k<3;k++)
    {
        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
    }
/ @3 `- ^" N, n, p( p, t; G    return sum;
}
* B3 I" A3 p5 R# h- d% }int main()
. J4 f$ ^1 ]  m% T$ H{
   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
    {
        cin>>a[i];
3 X" Q! ^7 o; d# W5 z    }
2 N6 X- x1 q/ F    cout<<"input 3*3 actangle:"<<endl;
, P6 C+ o; I- q    for(i=0;i<3;i++)
3 f7 F! g, Q( d$ G    for(int j=0;j<3;j++)
    {
$ E# H1 Y8 o& T  i        cin>>b[i][j];
    }
    for(int k=0;k<3;k++)
    {
        max_num();
, f' }, H8 G( v. I2 Z9 R    }
    //cout<<"sum="<<sum<<endl;
$ ^" K2 h# U. f, D    cout<<"sum=";
1 X2 a& D2 ^% C  u7 J' ~    for(i=0;i<3;i++)
7 J2 D- J; v& o0 v. @( a8 s3 g4 v    {
        cout<<temp[i]<<"+";
    }
1 g# `; B$ w8 k    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
0 a6 }0 v9 l! j$ \5 N    {
        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
+ m3 P  t5 X$ P: T6 ]    }
) I( q& m* k4 i  p- o    return 0;
" V5 O) m7 I4 E2 D$ E2 k}

厚积薄发

编程代码二：
#include<iostream>
#include<cstring>
3 Y& M5 A# M6 n! p) _! g#include<ctime>
using namespace std;
0 r0 h, t* M/ W1 U, {; tclass ifo{//矩阵的元素
    int clerk;//员工号
' F0 o( }9 C7 F4 a" V. f    int area;//区域号
    int per;//爱好度
4 x; X$ {- U+ o5 H) I3 L8 Epublic:
6 K2 J$ b8 d% g6 _7 c, c; C    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
/ y( }$ Z3 A; H7 |- P3 H    int getclerk(){return clerk;}
    int getarea(){return area;}
6 a) D: \, T7 O2 K: p/ C( f    int getper(){return per;}
    void setclerk(int i){clerk=i;}
    void setper(int p){per=p;}
* r. g9 [# [- `5 E7 Q    void setarea(int a){area=a;}
$ [% h* o3 l7 \, W, A$ r: k};
4 Z- o" d3 R- Sclass area;
class clerk{
# A8 _( j0 o  e/ \, z3 O$ M    int areanum;
6 Q- R8 W6 _7 R1 x9 X- U' E    bool isin;
    int inarea;
0 C) h8 x' a6 M* k) }* C+ o, npublic:
    void set(int num){isin=true;inarea=num;};
, u" n( V3 W! m    void setisin(bool b=true){isin=b;}
    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
# e) j7 o2 ^" p! t};
class area{
/ L. h) C5 e% {5 A    int num;
  y4 C4 R* n1 S1 Q' G    int max_num;
: X& M& R) p+ {+ [+ apublic:
    friend void set(int);
3 g5 j0 R$ ?' ~- w8 m/ V# L3 o    int getnum(){return num;}
. n6 {5 N# b6 R$ s    void setnum(int number){num=number;}
    int getmax_num(){return max_num;}
, {3 O% T. W. [0 b* L9 i4 D    area(int number=0){num=number;}
* k6 n5 k2 z* A& u2 M    int getclerk(){return num;}
    void addclerk(int ps){num++;set(ps);}
. n8 _% V1 X* |) N' n( ]( Z  u};
void getorderbyper(ifo array[]);
int areanums;
void main(){
    //input
    cout<<"输入区域数：\n";
: B8 w6 e2 t" Q& P    int area_num;
0 \* F% k' z" k; \" z: t    cin>>area_num;
    areanums=area_num;
: M# N* H9 y' d$ y! L& n    cout<<"输入员工数：\n";
7 g1 \% ^& F: q5 `    int c_num;
( N1 M! k! x  D0 `4 u/ `, n3 y# Z    cin>>c_num;
" d, R5 ~5 a" m2 X    cout<<"依次输入每个区域能容纳的员工数:\n";
4 G: @4 k# {4 d* S2 E0 n! H: _    int *max=new int[area_num];
' p: p! Y* ^, V    int nownum=c_num;
    while(nownum){
5 j& z) }5 l- R3 G, t0 H        for(int i=0;i<area_num;i++)
        {cin>>max[i];nownum-=max[i];}
9 q4 J: j; G% X        if(nownum>0){
4 J6 h8 \- U- C+ K; F& o9 V7 |            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
9 m# m9 i; y5 y; @: b            nownum=c_num;
7 Q# C( B' {1 t, f        }
        else nownum=0;
    }
. Q; G( a+ @. ^# Q    cout<<"按行输入每个员工的偏好：\n";
    ifo** per=new ifo*[c_num];
' b2 M8 x& u$ g( K    for(int j=0;j<c_num;j++)
        per[j]=new ifo[area_num];
, R8 i  }3 r/ L! A4 I, J    srand(time(0));
    for(int c=0;c<c_num;c++){
        for(int a=0;a<area_num;a++)/*
* e; s! W/ r: [( b, M4 A3 Z% I/ c        {    int p;cin>>p;per[c][a].setper(p);
1 A6 b( g, x& q9 v% t            per[a][c].setarea(a);
( w, A3 e8 {, y1 W            per[a][c].setclerk(c);
        }
! V3 _0 N( f8 ~0 o+ a" i        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
        {    per[c][a].setper((rand()%60)+40);
0 m. C2 ~+ x4 U$ _% C            cout<<per[c][a].getper()<<'\t';
$ O2 |- R/ T* j) p$ P        }//测试时懒得输入，故以60-100的随机数代替。
-    cout<<endl;
% @2 N* S* P9 G1 q7 M    }
    //output
# Q$ o0 l- J& [: f/ `8 H        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
        clerk* people=new clerk[c_num];
) ]! q5 Z: Z. g% o        area*  areas=new area[area_num];
        int totalper=0;
4 y3 E$ y8 B1 _3 z  T        for(i=0;i<c_num;i++){
( C5 e8 D* W2 e* w, z6 A            for(j=0;j<area_num;j++){
            if(areas[per[i][j].getarea()].getnum()<areas[per[i][j].getarea()].getmax_num())
& c: D/ \8 {" i! }                people[i].set(per[i][j].getarea());
% R0 [* ~7 C3 {0 }7 G                people[i].setisin();
! U8 Z' m+ I, H/ s4 X/ h                int number=areas[per[i][j].getarea()].getnum();
                areas[per[i][j].getarea()].setnum(number);
& V) M3 Y& t0 N) u                totalper+=per[i][j].getper();
1 A3 w9 B5 X6 G- K: G1 B                break;
) `- [5 A2 |4 {( F            }
        }
        cout<<"能达到的最大喜好度为："<<totalper<<endl;
}
void getorderbyper(ifo array[]){
3 q. ]; |$ I6 s( _  G5 _: w    int max=0;
    for(int i=1;i<areanums;i++){
        for(int j=0;j<areanums-i;j++){
6 m4 C. K. T6 A8 G6 p5 V        if(array[i].getper()>array[max].getper()){
            max=i;}
+ w! d' y+ S4 g! I, g2 ~: ^1 Z        }
3 ]: ~+ l5 {/ l, o        ifo temp=array[max];
0 r8 o/ U9 U1 h3 P3 r0 N        array[max]=array[areanums-i];
        array[areanums-i]=temp;
        max=0;
    }
" Y4 ]8 W# v* e3 P2 q}

厚积薄发

" h9 x/ _2 K' W; ~- O1 \& D
, }* G) B9 C9 C6 I$ U( A  c#include<iostream>
2 ~0 n5 w- i0 x5 Dusing namespace std;
; ]2 Q7 Y: H/ J- }, W2 f4 bint b[3][3];//M*N矩阵
; ]5 R5 r: M0 {- Cint a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
int sum=0;
int max_num()
{
    int max=-32767;
! V, \" J; @+ `, h* `' @    int x,y;
3 ~; h" M' B% {/ L$ C5 j    for(int i=0;i<3;i++)
' F( L1 U  x/ g# x0 E  n2 `    for(int j=0;j<3;j++)
" R/ j. `% ]. I8 x) b0 d! n8 F    {
7 R/ z8 D$ Y, z2 k) o        if(max<b[j])
6 K$ ^( D3 V+ o        {
  {0 {1 B# o6 {8 Y+ \, h            max=b[j];
            x=i;
* X/ A' Q7 v: P2 `            y=j;

+ m  ^4 [5 T5 l' f7 @  R5 O1 W( O. z        }
    }
$ d: \9 b9 I: @6 N% \1 [   
  ~* }- l' J/ \. d    if(a[y]>0)
    {
        c[x]=y;
- ]/ S/ o. c( V& c+ l( u6 R- q8 p# W        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
6 D5 l- h9 b3 Y$ V& ^        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
" H- _! W5 @+ C) M    }
, g  x  E; P$ G4 c! D    else
8 ~/ i* i6 H6 d. w6 d$ T5 U    {
' y6 i3 K& U% H5 x9 s+ W. M2 Z        b[x][y]=0;
    }
$ K3 m4 Z& g5 Y# u, @+ E   
    return sum;
; A1 G  q6 l; `9 y! k" a}
int main()
{
   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
    {
1 M. l$ o- \+ P0 T! a4 t6 P" n        cin>>a;
3 Q( l: r; o7 w( q5 _% t! O" S0 b    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
  E& [' U* I% x% l! ^- X+ I    {
        cin>>b[j];
    }
4 x9 e+ \+ @# s8 h9 Q, @2 n    for(int k=0;k<9;k++)
    {
        max_num();
    }
8 g1 Z) r6 l) X6 j8 J   
2 h" `2 W8 g- `, p* j' W    cout<<"sum="<<sum<<endl;
    cout<<endl;
    cout<<"reslut:"<<endl;
! T! K; O. V& m* _# _; A% r) k! y    for(i=0;i<3;i++)
    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
    return 0;
}#include<iostream>
6 m+ ?+ N$ s0 Q" K; M/ zusing namespace std;
/ a0 x4 m, g4 Q" r5 h% }1 X$ ?% }, uint b[3][3];//M*N矩阵
# ^, f0 Z' `' s5 K, f3 n: E. D- oint a[3]; //区域人数上限数组
8 C" c3 R& H/ p% i8 e# Q; x' Cint c[3];//记录某人i去的区域j
int sum=0;
, p& o8 @/ z7 ~( K$ {int max_num()
: n9 K; I" @4 j3 x{
3 |8 h7 d$ k- A! \    int max=-32767;
% X, n5 |! a% m4 r$ T    int x,y;
    for(int i=0;i<3;i++)
/ B: V, _+ V4 K0 G5 K    for(int j=0;j<3;j++)
6 N1 ?" }( F4 y6 D: f) C* |    {
4 Q$ z- ^, k- l7 J        if(max<b[j])
9 y3 {! s# I7 k9 [1 f: i        {
            max=b[j];
& {+ F9 q2 e* T! I            x=i;
/ }& L" [: T- U7 k            y=j;

        }
    }
   
    if(a[y]>0)
    {
7 w- @  |1 t6 J4 q0 a! l9 w        c[x]=y;
4 G$ o2 @! O# T) K7 I8 W2 C        sum+=max;//总喜好度加上添加
% ]' @8 j$ U& }6 C7 }2 {8 S- A3 @        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
$ |  m; y$ \2 _/ v# I& H        }
4 C5 c* U% z5 O    }
3 a3 S4 F/ W; t0 a    else
! e2 X- G; P$ h3 `& P. f! y, w' ]    {
3 W, `/ |* T0 [3 x9 V9 l- v- Z        b[x][y]=0;
2 `2 K" I7 U6 t. l: m    }
   
    return sum;
2 m' o4 ]% M2 _- s3 c% u" }}
int main()
! k' v# G! \; d! k5 z1 ^{
   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
2 I% k7 ~' i) N1 r% E! ^    {
) J& l$ d5 ^- D6 v* U6 b" ^( U        cin>>a;
    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        cin>>b[j];
  G, I: [7 X7 {' O1 W7 \    }
    for(int k=0;k<9;k++)
8 F. {1 u! `6 _3 i0 H  Y! Q9 p  }    {
  l8 N& ?+ J1 X; i$ N) a% K        max_num();
    }
6 c4 `3 v, j% b$ L& c) r3 Y   
    cout<<"sum="<<sum<<endl;
    cout<<endl;
0 n: w2 @0 m1 }9 j3 z    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
    return 0;
2 `7 q& c( D2 `, B: i}