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

厚积薄发

座位调整
  f- {; V/ ~1 Z* k' p4 e* ~6 B
题目描述：

百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。
! v  p8 l5 G2 u* A% n
调整的方法如下：
. I8 G9 n% C( h* ^$ }+ e
$ {+ h' Q+ a1 x1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。
/ C) J" d( `, e) t2 r* W
2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。

, o1 @1 U" g% r; s% ~4 l5 ?1 x5 v3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。
" r0 D; y! ~- M% C- V2 a! Y/ a
数据输入：
/ d( r4 T7 ^9 P6 D$ ]( t. l, g7 ?$ S
第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。

第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。
/ m, y0 @4 b3 ^- D
紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。

答案输出：

% {% ]$ m$ Q/ R/ J& l3 L) r对于每个测试数据，输出可以达到的最大的喜好程度。
2 I9 u9 Y& W- J% s
$ K0 f' F  x& c7 K/ i输入样例

5 x0 a( |  D) ~7 E; B
3 3
9 z. h: C( `5 S8 e- v
1 1 1

100 50 25

100 50 25

% i5 e# V; t( [* D" ?+ _" t# s100 50 25

1 ]* H- M+ Y. }, C9 S8 V3 H
输出样例

6 y; b$ e6 Q$ L- S8 g: q. ^; q
* R$ \3 m" A# \. J+ h175
' y& f5 P( A& B  \1 s
/ h+ i5 B$ F2 r3 C. I* I

. y. [. w; j" V% Z5 f
数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175

厚积薄发

: K! C# q# I: k3 A# I9 q% u
#include<iostream>
- I/ `% B" N$ a: p, Z2 ^8 h8 ~& w: iusing namespace std;
( C: ^; |$ B% U9 ^; jint b[3][3];//M*N矩阵
6 \/ ]; ~" B, [0 iint a[3]; //区域人数上限数组
& Q; h+ B% {. P1 W# e8 dint c[3];//记录某人i去的区域j
; N1 D& Z4 v& ^0 }  g: T0 Fint sum=0;
, W3 f9 k- Z/ P/ Nint max_num()
  _7 C6 l: K. O( O7 h6 B{
, O+ J3 t- {  w8 k9 T: F1 {    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
( l3 V7 k' g2 A& G" l% e) c    for(int j=0;j<3;j++)
3 o* p( d! p) A# |% O    {
( ?+ A& z! ^2 @, u7 P; [        if(max<b[j])
        {
2 Y& U4 n! x7 l/ e) y            max=b[j];
9 k% U* f& t% S% H3 ?5 l# Z            x=i;
. I3 v+ _2 _2 F5 p2 Z4 w7 E            y=j;

1 }) [% Z. k& n' c6 u% f! ~        }
    }
+ N$ E& d( t; p/ ~   
& C! r& f5 h2 l6 d( M6 r' w* b7 C    if(a[y]>0)
7 |, D8 S) d  ^" O# h# c    {
        c[x]=y;
        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
: U9 B& J) J7 K+ @+ V4 T) Q        for(int k=0;k<3;k++)
        {
4 D, Y! i5 T/ l4 c( `# J- K+ f            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
& J3 A1 ^6 I2 ?- b( F; Q        }
    }
    else
    {
        b[x][y]=0;
    }
* }' [4 A% [1 v. C# ~- ^6 w; H   
# N3 ~/ w, L( ]: G; g: |    return sum;
}
int main()
{
   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
    {
+ |  o0 `" w. y- S, y        cin>>a;
    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
& w% g) z0 U/ o    for(int j=0;j<3;j++)
2 d# ^, K* g- F( Q( y) u! N7 R, @1 ~    {
8 H  j# C8 |5 e        cin>>b[j];
    }
    for(int k=0;k<9;k++)
    {
' b  b# @) l8 T0 o, T) c+ ]( ^        max_num();
$ J) \2 S7 I' d    }
   
3 v" q8 _4 c3 K* D    cout<<"sum="<<sum<<endl;
# [9 w4 N0 A( w. a. J    cout<<endl;
6 S' j' m$ v/ b' \% u. W3 C* a    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
: k6 v! B5 w- a+ {/ y    {
0 N: |" d! q# B4 Q+ F  |; f3 U        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
6 R, p8 G% `% f* P) ^+ z( A* {  ?& {    return 0;
}#include<iostream>
using namespace std;
+ h: y- t( Q2 a# S( Q$ Eint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
int sum=0;
int max_num()
{
    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        if(max<b[j])
; D# t8 u! y8 p4 e, Q7 o8 [        {
( f  b& {; P) x+ |1 U) ^            max=b[j];
            x=i;
, o2 s1 j+ k5 }" O' {, h            y=j;

, [- T2 r) B/ Q, I' D, n        }
% c( @2 s. r+ [- ^3 l2 a% k, v    }
   
    if(a[y]>0)
    {
        c[x]=y;
        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
( P$ y6 m9 P) [7 `: f6 }$ q        {
3 y" |' ]2 b7 ^$ _1 k& A0 M            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
% X3 b6 q6 k5 Z- V4 r    }
    else
5 T% h8 g% V( ]  R) m    {
        b[x][y]=0;
    }
   
# i+ K1 F7 h& W. T: c; r% y$ v9 [    return sum;
}
7 L0 I+ w; m3 T0 d- a! cint main()
{
   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
2 K) @* u8 u9 m/ O; n# [    {
        cin>>a;
9 G! O* |2 B2 ]/ O) I    }
( Z* i) B1 {7 X* ?  i/ W    cout<<"input 3*3 actangle:"<<endl;
- B% m0 q0 `8 c$ E7 d    for(i=0;i<3;i++)
" I9 n) T" M7 e* \7 }  k    for(int j=0;j<3;j++)
    {
+ `& N1 |  Y  h' |* K+ B        cin>>b[j];
9 y# x9 d+ P1 ^3 t, a9 V    }
' C  S) a$ r& `% v/ Z& ^    for(int k=0;k<9;k++)
    {
1 @' J/ h% W  a0 d* `7 R- l        max_num();
8 n* V: h/ h% `6 k& s6 H9 R    }
   
    cout<<"sum="<<sum<<endl;
- V% M0 W) I( h5 n    cout<<endl;
& E7 J- ^$ @9 J  M2 j9 e    cout<<"reslut:"<<endl;
6 j3 s( s' z: k; K: W    for(i=0;i<3;i++)
! ?9 \0 O! y6 \4 F8 [    {
0 M6 ?5 }) O. J" @        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
    return 0;
}

厚积薄发

编程代码二：
  x3 H! A3 T+ R8 @" w#include<iostream>
5 c- K  O% _/ {& H) g, F#include<cstring>
. ?( `* _$ C; ]% q+ [8 g#include<ctime>
using namespace std;
class ifo{//矩阵的元素
  r2 u  v; ^3 n/ y    int clerk;//员工号
    int area;//区域号
& \% a' [. f6 B6 x& H6 f    int per;//爱好度
public:
    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
! {3 h( A% x* M+ J+ {/ p+ l* b, m    int getclerk(){return clerk;}
! k4 e7 n" V- ]# G! ?2 B( X8 ?    int getarea(){return area;}
. e6 k2 m0 w1 I. B0 |3 V9 C8 w! G+ T    int getper(){return per;}
    void setclerk(int i){clerk=i;}
    void setper(int p){per=p;}
    void setarea(int a){area=a;}
};
class area;
class clerk{
    int areanum;
3 L' w, U- f6 K: v; ^    bool isin;
# \% x6 g6 s3 Y1 T    int inarea;
2 K( s- z  l2 Opublic:
    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;}
};
class area{
    int num;
    int max_num;
: g3 ~! [: A% Q: s5 c. n. M1 }public:
    friend void set(int);
    int getnum(){return num;}
    void setnum(int number){num=number;}
    int getmax_num(){return max_num;}
6 _8 I3 q0 B! u7 H' g    area(int number=0){num=number;}
5 g0 F' [/ K8 m7 c4 w+ H    int getclerk(){return num;}
    void addclerk(int ps){num++;set(ps);}
};
void getorderbyper(ifo array[]);
$ ]3 G/ G7 i4 R3 G1 W* gint areanums;
, T  ^0 U8 I) Vvoid main(){
8 Q( ~$ \; a/ ~. N    //input
4 G: R; y+ f* A, r3 n% @    cout<<"输入区域数：\n";
5 P6 j7 _; w2 q* }$ j    int area_num;
    cin>>area_num;
    areanums=area_num;
' J- H+ C. ^) t" u$ r+ g) L2 J    cout<<"输入员工数：\n";
  J1 n6 Z- ]& C( Z* S/ ^  z    int c_num;
) ~2 P) F" C% `; Q6 k    cin>>c_num;
    cout<<"依次输入每个区域能容纳的员工数:\n";
8 T5 T) V; p$ i- c    int *max=new int[area_num];
    int nownum=c_num;
0 }2 U( G' P7 f, h    while(nownum){
% w* K  g, P& g! a; q& r        for(int i=0;i<area_num;i++)
        {cin>>max[i];nownum-=max[i];}
2 N% e4 L1 _  i: [% P& C5 J        if(nownum>0){
            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
            nownum=c_num;
! G/ _4 t* V0 j        }
        else nownum=0;
    }
. ~  |2 ^7 d1 p/ u( o    cout<<"按行输入每个员工的偏好：\n";
' i  u0 L7 ~; d1 f) d    ifo** per=new ifo*[c_num];
7 f6 w: T6 I& _8 h; V    for(int j=0;j<c_num;j++)
" H( A! F1 k6 ]0 r, G! ]3 `# G        per[j]=new ifo[area_num];
    srand(time(0));
    for(int c=0;c<c_num;c++){
6 b8 X# i7 r! @; K        for(int a=0;a<area_num;a++)/*
        {    int p;cin>>p;per[c][a].setper(p);
! o+ w( c' B5 V( Y% {( N3 Q            per[a][c].setarea(a);
' |2 U: H9 R, X& V* `% W( V            per[a][c].setclerk(c);
        }
        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
        {    per[c][a].setper((rand()%60)+40);
            cout<<per[c][a].getper()<<'\t';
        }//测试时懒得输入，故以60-100的随机数代替。
( _4 Y5 d" O  U% E' h-    cout<<endl;
    }
    //output
0 ^$ U3 j9 R- O        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;
        for(i=0;i<c_num;i++){
            for(j=0;j<area_num;j++){
            if(areas[per[i][j].getarea()].getnum()<areas[per[i][j].getarea()].getmax_num())
+ \# O- M; a+ v1 i( x& r2 W                people[i].set(per[i][j].getarea());
0 s! P. c! R9 r2 F; X, L, F: s                people[i].setisin();
* ^0 r) j& I* K/ f6 s, [" D                int number=areas[per[i][j].getarea()].getnum();
                areas[per[i][j].getarea()].setnum(number);
) Z  w% c9 ^1 ~" i/ l                totalper+=per[i][j].getper();
; q  y7 w+ r* }                break;
            }
        }
        cout<<"能达到的最大喜好度为："<<totalper<<endl;
/ j# }  J' d+ Q% O2 U}
- B3 _# e& S( t* a- W; ]void getorderbyper(ifo array[]){
) g9 G* ?; n' ~5 W( e    int max=0;
    for(int i=1;i<areanums;i++){
6 Y2 m8 M3 q7 t5 |  D8 k& c" |: V        for(int j=0;j<areanums-i;j++){
        if(array[i].getper()>array[max].getper()){
4 _' l& F7 s: q+ [! X            max=i;}
        }
        ifo temp=array[max];
6 Z" W- j: `4 A9 _' `        array[max]=array[areanums-i];
3 ^+ P& e# Y' k# i3 x7 L6 J        array[areanums-i]=temp;
        max=0;
    }
& P! @+ ?* L) U  U! t2 y7 e}

厚积薄发

代码3：
/*
# N' t! c3 }6 c算法思路：
6 x/ Z6 J+ }0 n% _0 Y; f2 a1 d（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
再加，该人的所有喜好度设为0，
: t( g' F0 \! [' b: R+ f' Y（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
, g3 |* o5 \7 P（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
* B+ e, p4 R5 J9 K: v, @& Q* F(4)最后输出总喜好度。
*/
4 @& {# g( E% V/ @# T. a2 v+ T( o#include<iostream>
' G: E1 x1 D% l& lusing namespace std;
4 @3 R( o" c& _% j: Mint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];
int temp[3];
int sum=0;
int max_num()
1 f) Y# O% E" C$ F" [{
    int max=-32767;
) K1 {- k- V# d7 a4 q    int x,y;
    for(int i=0;i<3;i++)
' V8 N4 i# \3 l9 l7 c2 _; Z    for(int j=0;j<3;j++)
' V; z# z3 [! c- |9 ~    {
        if(max<b[i][j]&&b[i][j]>0)
, v% A5 {/ C0 y6 @        {
            max=b[i][j];
            x=i;
) a0 o9 G: F3 `( g4 P) ^/ x, D            y=j;
/ l& v' d3 C7 o- E1 T( q
        }
    }
   
$ ^1 x4 u7 M. t    if(a[y]>0)
  v7 O4 k7 b# n    {
0 \# [- d' q) R* h( H0 H6 w        c[x]=y;
        //cout<<"c["<<x<<"]="<<c[x]<<endl;
2 K% Z9 k- L/ Y5 w' S9 ]        sum+=max;//总喜好度加上添加
        temp[x]=max;
        a[y]--;//区域上限人数-1
    }
# j0 x# |8 V  c1 Q    for(int k=0;k<3;k++)
    {
5 s5 H/ ^: s* h4 [- z5 `        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
7 u' D- `5 \/ H6 Z( `7 p* n1 [& A3 I    }
: e- L9 H9 ^% a( w  j$ W0 Q    return sum;
( z( t+ `5 G; N1 z( g4 J# ]}
8 ~7 i% r; [2 m. |! hint main()
{
( U8 I/ `+ t$ I, ]- ^   
* O$ A8 [0 h  P6 |    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
/ E5 y1 [0 C0 \; i( [, c$ b- E    {
        cin>>a[i];
    }
. Y4 W' A; G* r' w$ }! y* Z$ N! ~3 T    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
0 F7 f# Y1 U4 T6 Z    for(int j=0;j<3;j++)
    {
. r& D7 x/ K0 ~  y7 u        cin>>b[i][j];
3 W% R) @" [$ S    }
0 Q# {; \) ~' m9 P    for(int k=0;k<3;k++)
    {
8 Y. D- @2 b4 o" q# H2 W8 H! `; O( {        max_num();
    }
    //cout<<"sum="<<sum<<endl;
$ N3 o8 X6 T6 D6 \, i4 |, O    cout<<"sum=";
( |; p' P+ H  p% M    for(i=0;i<3;i++)
    {
        cout<<temp[i]<<"+";
. @# {5 v( l9 S( K1 K    }
    cout<<endl;
# J) A3 b* L5 ?. K" N6 ^' a6 \# e    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
& p" i$ @- z$ w0 _& H    }
    return 0;
, ]$ @( b/ P2 t}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
数学中国社区分享快乐！
6 Q6 K) N* K  c) `8 p% S$ @

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！