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

厚积薄发

座位调整
; O) I( H  G. ]" t  Q- ?
题目描述：

$ _0 R+ A6 u6 K) x$ M) A* g* M4 _; ~3 V百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。

( c# I3 P3 d2 z6 W! C( n调整的方法如下：
4 Y% v# M5 u1 f! T& i- {# b
% {( e1 z6 a' e# X1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。
9 |, E& }# w, N' y* ]$ }
2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。

& y3 t' n% L( T) K" \3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。

数据输入：

" p2 S- I, K5 ~$ z. N2 D第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。
+ O; h  U; D; F* @0 D: c; Q, r: [
第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。

紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。
  ?: r7 m& z% X: Q% t% C$ Z* {( P
答案输出：
" b, {1 x: V$ k) l
: R4 _0 c& Z  g对于每个测试数据，输出可以达到的最大的喜好程度。
) O, x  d& p- L4 ^2 l3 F
输入样例

3 3
: P$ _" k& @4 b% D
! y! l4 T' l& T; `1 1 1
. V: @9 J- v* h8 }
/ R$ @* y& y3 `3 S# p  Q100 50 25

100 50 25
8 ]0 B5 u% {& ^
4 M7 c; B. M  u8 A0 s6 O100 50 25
+ N0 I" b6 `+ S$ I; ^% Q# z

# H9 X3 k3 L* H  a
输出样例

! P" i! F1 ], f' o
175
% k" W8 w% V) A
. F' Z3 V0 ^1 W0 s/ [

, _# ]( U) Q4 M/ @* x3 Z# Z数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175

厚积薄发

" B) h* r3 y6 t* H4 |3 w' h#include<iostream>
using namespace std;
- |1 `: G5 \4 C& m. @int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
9 M" _" o! o( i& b, tint c[3];//记录某人i去的区域j
0 T+ x1 d! B8 @8 Qint sum=0;
int max_num()
% }- U, x% B2 q" `{
    int max=-32767;
) @3 p8 c1 J, x    int x,y;
; L. r! `% i( G2 L3 W+ b+ g    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
& P9 M+ e9 D4 a( c) B0 _9 N, d    {
* p- p/ e* O" X) x: O& j        if(max<b[j])
9 z' \; p, f& o' M" k- K        {
            max=b[j];
" j9 {9 I/ i( A( p            x=i;
            y=j;
' U9 }7 ^& K% w: X
/ u! A4 h) W- Q, R; z        }
) {  J! I& @) k( Z6 Z2 C* m# E* M0 z    }
8 C/ e# W4 ]$ O: R$ x   
    if(a[y]>0)
    {
* p% w0 D; W2 A$ B) R- Z% G- H* C! i# c0 ?        c[x]=y;
        sum+=max;//总喜好度加上添加
; I" I- e! _! a+ d9 S        a[y]--;//区域上限人数-1
7 ?5 l$ y0 S) N! J# d        for(int k=0;k<3;k++)
: b9 _. M& p( I* m8 b4 i        {
9 v0 J) A. N* R            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
    }
4 z+ H9 r: _0 G, Q. p* s    else
3 K: {6 M: B9 `' X    {
0 w/ s1 r. a/ C' f+ L) v" k        b[x][y]=0;
    }
/ Q8 b/ N# c& G; G+ N2 I   
    return sum;
1 z$ H* Y& T3 a* q9 S}
int main()
- W5 n4 `' F2 Y1 d( S{
   
3 u1 \5 `: a3 ?' N5 ?% m, a    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
    {
8 y4 @! f2 M% O. f        cin>>a;
  P. ^2 i0 s8 g/ {" h' \- r6 `2 ~  f- l    }
    cout<<"input 3*3 actangle:"<<endl;
, s! K8 D7 t/ [6 X- g: p5 O6 x! M    for(i=0;i<3;i++)
- {) g, d. k+ W    for(int j=0;j<3;j++)
    {
        cin>>b[j];
% Y0 h4 `. d% `    }
" T7 V, m' Z' @, b0 l    for(int k=0;k<9;k++)
& A, S% D% i' t7 X    {
# v$ J1 P8 m! q' v        max_num();
) n) D' H6 u! A6 ~  [$ c/ u$ f    }
0 Q: K2 C! l' y3 ^- F" P   
2 b1 T$ }& u8 E! J( m6 p( F+ g    cout<<"sum="<<sum<<endl;
    cout<<endl;
    cout<<"reslut:"<<endl;
  B5 K3 k8 T9 r) N3 h4 E    for(i=0;i<3;i++)
5 y* y" _! U+ `5 x( u  g    {
! k  e) C2 S! y5 G        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
4 S0 r8 t! ^7 a    return 0;
$ `! u. F/ @& w0 |}#include<iostream>
9 w/ I: H8 ^- o5 x$ f. o# zusing namespace std;
int b[3][3];//M*N矩阵
/ T" F  J2 `" G" Bint a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
: v) v4 l+ F2 q% Z; sint sum=0;
int max_num()
{
: S7 a% C' E# q2 A# E    int max=-32767;
    int x,y;
+ }) z4 W- S) v$ k5 M    for(int i=0;i<3;i++)
& j3 r( U% ~1 k0 M% }    for(int j=0;j<3;j++)
' d# L) q* a  U  i  D6 z) _4 i    {
1 p8 R' I1 E+ E- t        if(max<b[j])
5 |- E' N6 B7 m! }' r# Q, C- `        {
            max=b[j];
9 A! b* E+ n7 b3 n* p& Y            x=i;
8 U+ [1 c/ O. N  ~) \# ~            y=j;

        }
    }
   
    if(a[y]>0)
: G) v6 L8 Z! _" j8 ~    {
2 V& X# Z  \/ F+ |4 g        c[x]=y;
        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
, \; a# l) ?" O8 D% a    }
3 y0 J2 g% n2 n    else
4 U& K. s& T6 A8 Y3 T; E6 ~! k+ a    {
! [$ [0 r0 O0 W0 d' n        b[x][y]=0;
' m1 `% N) M& v1 t    }
/ M$ E# A3 O) z; o1 e   
& H( o4 u% R. l  t' k    return sum;
  Y6 Y. ?8 e# W7 D}
' _6 R- z) y, A& E0 o' _5 mint main()
/ y- |: k5 O0 z5 w- S* _( o' E# a. F" h{
   
$ ^$ J3 p- z/ r* J    cout<<"input 3 zone's limit:"<<endl;
6 w9 o+ Q; O9 A: X6 L8 I- \! `1 S    for(int i=0;i<3;i++)
    {
# I2 _! X3 T! x  t4 k        cin>>a;
    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        cin>>b[j];
, R! v; p1 X+ R9 B; Q. M4 x* }( O2 P    }
    for(int k=0;k<9;k++)
& s5 v/ G& x, G8 i. w, @: D    {
. T% b3 B7 V6 p8 R$ u' ?" L        max_num();
    }
  e0 a/ c  f: `- |* q$ h6 t   
    cout<<"sum="<<sum<<endl;
5 W- o4 z6 Z9 {    cout<<endl;
) h# b$ W7 m) \/ a5 M+ H  Y. R    cout<<"reslut:"<<endl;
& Q* m% e' `" u9 Z" y    for(i=0;i<3;i++)
    {
( J5 e" {' g' }# o+ r% H        cout<<"people "<<i<<" go to zone "<<c<<endl;
6 X! Y  [+ H9 S/ g0 v" b) F    }
+ v7 x8 K. a* o9 B    return 0;
0 d& E! W& }" D& ~}

厚积薄发

编程代码二：
#include<iostream>
* g9 r* U, v3 Y4 `8 Q6 @# g1 a+ x0 T#include<cstring>
#include<ctime>
5 e1 v/ V5 o$ N" Yusing namespace std;
class ifo{//矩阵的元素
8 [6 ]* _) R4 b1 R7 w    int clerk;//员工号
    int area;//区域号
' I6 M" [  f9 ]    int per;//爱好度
public:
' A+ W+ B5 A# ^: ~    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
& z/ }/ k* w* Z6 k0 l    int getclerk(){return clerk;}
% J( `# J7 Z/ f, n' {9 V" D* @    int getarea(){return area;}
( u1 E3 J. f2 i    int getper(){return per;}
7 k( N% l+ ^, O2 O( o( X5 _    void setclerk(int i){clerk=i;}
( Y) Q* \% v( a% w    void setper(int p){per=p;}
    void setarea(int a){area=a;}
};
class area;
class clerk{
0 b& b9 A* y6 Y& f! k. ~8 V( ?( M/ |$ U    int areanum;
    bool isin;
    int inarea;
public:
4 M6 z1 \- c: _1 H  m* g7 ?. Q    void set(int num){isin=true;inarea=num;};
4 ]- F2 [, K5 g( B9 J3 K( U    void setisin(bool b=true){isin=b;}
    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
};
$ u- g5 p4 O$ B/ ?6 X* _: zclass area{
; u" j/ G$ r( V# N3 O    int num;
    int max_num;
$ z% W4 O, E- b, g6 i: M1 q% z& g, vpublic:
' P$ Y# r( K( R0 d    friend void set(int);
! F3 s+ `" c0 ?, n9 u% G9 S6 x6 G    int getnum(){return num;}
% w5 h, t* V2 f    void setnum(int number){num=number;}
8 M  S2 W% q% h" S( _2 R% N% D# ^    int getmax_num(){return max_num;}
- \: G& ^$ P/ J) ^8 W6 U    area(int number=0){num=number;}
    int getclerk(){return num;}
    void addclerk(int ps){num++;set(ps);}
5 Y1 w% D. h) ^5 u, b};
/ ~6 r: Y! m: w; Q8 _4 h+ i  ^. R* |) Ivoid getorderbyper(ifo array[]);
- V: z) x9 r* _$ Dint areanums;
3 b' W- j% r6 }" Z+ R) f# evoid main(){
    //input
+ ~- C( e- C0 P: \  {* v+ `    cout<<"输入区域数：\n";
    int area_num;
    cin>>area_num;
  d! j6 A4 R" W4 X9 Z. k    areanums=area_num;
  f+ [. y/ e! t2 g! Y$ b1 j    cout<<"输入员工数：\n";
6 @& t) H& ^, u0 t$ W: E    int c_num;
" r* t6 O. k" l/ g    cin>>c_num;
5 q6 v/ S7 a; g6 j5 u* W    cout<<"依次输入每个区域能容纳的员工数:\n";
5 u% z; Z+ `. q9 I    int *max=new int[area_num];
    int nownum=c_num;
    while(nownum){
        for(int i=0;i<area_num;i++)
        {cin>>max[i];nownum-=max[i];}
; O# a7 }6 S% d        if(nownum>0){
            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
            nownum=c_num;
# J2 I, U, u. o5 \        }
; k" X  h' Z. F" |        else nownum=0;
+ C0 w- {: D( s/ h" g1 N1 p    }
' J* R" Z; d2 {  h" [2 i0 O# Z    cout<<"按行输入每个员工的偏好：\n";
    ifo** per=new ifo*[c_num];
    for(int j=0;j<c_num;j++)
        per[j]=new ifo[area_num];
1 h4 B& ^9 @- c1 j6 a% s) g) E    srand(time(0));
    for(int c=0;c<c_num;c++){
1 b6 N6 _- c& i        for(int a=0;a<area_num;a++)/*
7 ]; e3 U& l8 ~& x( f3 V9 ]        {    int p;cin>>p;per[c][a].setper(p);
            per[a][c].setarea(a);
            per[a][c].setclerk(c);
( H/ v  M5 A" C# ?! Z) d  S        }
        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
        {    per[c][a].setper((rand()%60)+40);
            cout<<per[c][a].getper()<<'\t';
        }//测试时懒得输入，故以60-100的随机数代替。
-    cout<<endl;
    }
& H4 ^- a, f" y# i0 s9 C    //output
8 b- o+ I0 T3 }) F        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
% l. h, C  g( f" _( N2 n# g7 |        clerk* people=new clerk[c_num];
        area*  areas=new area[area_num];
9 i: a/ j3 v! F        int totalper=0;
1 q: m1 @% ]( v& j        for(i=0;i<c_num;i++){
; P3 a$ K6 I, l- m" v' N. w4 K            for(j=0;j<area_num;j++){
            if(areas[per[i][j].getarea()].getnum()<areas[per[i][j].getarea()].getmax_num())
' x1 }5 D3 Y5 _) o" {                people[i].set(per[i][j].getarea());
% \, g0 M' b# Z+ |3 k( s( @+ h                people[i].setisin();
$ R) z" T. T7 f  {                int number=areas[per[i][j].getarea()].getnum();
* ^/ v; N- a( |: ?& f. y: Q                areas[per[i][j].getarea()].setnum(number);
                totalper+=per[i][j].getper();
" B! J; u+ ^; k9 W, s8 u; o                break;
            }
        }
4 y' w  ~) Z2 _        cout<<"能达到的最大喜好度为："<<totalper<<endl;
4 \8 ~2 b+ \: B0 J}
void getorderbyper(ifo array[]){
1 M5 ?0 N. N! e8 ^; a6 M, }# F    int max=0;
    for(int i=1;i<areanums;i++){
; {5 v& L, z& s* I8 s5 m) q1 ?        for(int j=0;j<areanums-i;j++){
        if(array[i].getper()>array[max].getper()){
            max=i;}
        }
        ifo temp=array[max];
        array[max]=array[areanums-i];
        array[areanums-i]=temp;
  ^$ A+ G( P: l2 J        max=0;
    }
8 G5 r. H/ d4 ?$ D$ M, V9 v}

厚积薄发

代码3：
) q( Y0 b' R! i' h; ^3 L/*
( i, p5 Q2 d* Z, Y  f8 r算法思路：
（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
再加，该人的所有喜好度设为0，
（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
) z2 R5 ]( c! _, Z- V: ?（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
; I7 t5 A" q- v- n" |(4)最后输出总喜好度。
*/
( e5 ~: {, E& X. Y: g#include<iostream>
( k. h1 @+ L6 }% I2 D8 u) Dusing namespace std;
9 H0 b: k5 i( C9 Sint b[3][3];//M*N矩阵
7 l: K6 k; E% Z0 Eint a[3]; //区域人数上限数组
4 d( o! k8 S4 b! f; lint c[3];
int temp[3];
int sum=0;
) J& U' D- ^! S8 ]. B+ w) nint max_num()
" i7 ~* \- }5 q! b3 o8 j{
    int max=-32767;
0 V9 p7 d( I2 R/ H8 j6 P    int x,y;
" f( G7 O9 n; I+ e% |    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        if(max<b[i][j]&&b[i][j]>0)
        {
            max=b[i][j];
' \$ N) }! p  P0 C. Y( b- T* K" I) }0 F            x=i;
            y=j;

        }
    }
' H# Z+ u- {2 y! o2 ~; \+ H   
    if(a[y]>0)
% p; W" ?" M  h, Y9 G; g    {
; f9 G$ E$ S) ]8 t1 I! {+ x        c[x]=y;
        //cout<<"c["<<x<<"]="<<c[x]<<endl;
        sum+=max;//总喜好度加上添加
        temp[x]=max;
        a[y]--;//区域上限人数-1
    }
    for(int k=0;k<3;k++)
8 f: j) d% {3 H. t. U; b3 w    {
        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
9 z6 g1 W5 ^) _2 q. M9 I$ E3 t& r    }
    return sum;
6 C( f# G+ p  I( t$ c$ ]}
8 _9 w: W, w$ Mint main()
1 A& Y, P( o+ i0 \/ q{
   
$ K5 f' t! `) d4 @0 w) q    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
* k5 P, A6 d9 O/ A1 O5 z    {
        cin>>a[i];
: H2 B1 ^2 g8 |: m    }
    cout<<"input 3*3 actangle:"<<endl;
' _4 I7 v, }! \6 |% @3 p( c8 C    for(i=0;i<3;i++)
5 B8 O0 S0 a7 G: q/ G) ]; f    for(int j=0;j<3;j++)
8 ]' ^% q9 i' P9 H9 Z    {
) L' B2 U; N; a# a        cin>>b[i][j];
" s( n) h5 \3 t, [    }
    for(int k=0;k<3;k++)
' s3 @# [* K, X" n. k( K    {
        max_num();
    }
" ~) f, G# H* V) `2 l/ @! A: D    //cout<<"sum="<<sum<<endl;
    cout<<"sum=";
    for(i=0;i<3;i++)
, a% ~2 ^5 W. {' m    {
        cout<<temp[i]<<"+";
    }
    cout<<endl;
9 S* |3 b5 z2 g2 u    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
7 l* S  g4 d% V5 ?9 `+ i% v3 M        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
; i" ^) u8 U' h: Z    }
    return 0;
}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
; ^& D# l3 G8 g9 Q/ ?2 ~0 S数学中国社区分享快乐！

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！