数学建模社区-数学中国

标题: 2006 年百度之星程序设计大赛初赛题目 5 [打印本页]

---

作者: 厚积薄发    时间: 2010-5-6 18:47
标题: 2006 年百度之星程序设计大赛初赛题目 5
座位调整
; V  b/ _. g  f8 M, f
题目描述：

百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。
8 X/ E* F6 n5 W; j9 {$ k
调整的方法如下：
$ g- E/ [7 q/ B" f
& ~0 i3 n# V& p8 f, m8 }% L1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。

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

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

( u  t# o2 ]( X* P1 o6 ~数据输入：
. l  f- C+ k+ |- [! p
第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。

3 z# d) M- q9 p; x% H: Q# e第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。

紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。

& Q' J: Z+ U, d/ b2 p+ q' U1 Y答案输出：
8 Y- E; `. ]* m+ o) Z; M) I) g( a
6 A4 S  C5 r: _9 A9 V$ R' V对于每个测试数据，输出可以达到的最大的喜好程度。
! {0 ^3 O3 I  t# a1 _
- h- i' m5 t# |; g; c/ j' g- ^; V$ G0 ~输入样例

3 3

: d5 t! d8 F$ t/ \: O) ^+ @3 F: I) H1 1 1
6 e: a! P/ s- y1 p) T- S# \
$ @# Y9 J# o9 M7 d. |9 `3 ]100 50 25

100 50 25

. @5 ^2 B# D! F3 |  }$ a100 50 25
0 m+ t! ]2 R/ w, [( r0 b4 ]' \8 @% y

输出样例

- W4 |$ e) l% @* E. t6 a
175

3 k3 p  r; `8 E- K  c7 |8 L: P; v

% x& |; ]1 z' y: x
数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175

---

作者: 厚积薄发    时间: 2010-5-6 18:47


* D; ?/ `% I0 Z" ~( r#include<iostream>
# N( O% l' u" C. Pusing namespace std;
( X& G: `- v- Nint b[3][3];//M*N矩阵
) w; u3 W. b5 j1 Z) j& e3 gint a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
+ V8 m/ [7 B" B/ l1 f+ V$ nint sum=0;
int max_num()
{
    int max=-32767;
  C% B$ l& u: X' E. a- Y    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
. n0 u! @5 i+ g/ Z0 \! y        if(max<b[j])
        {
            max=b[j];
2 b5 |7 D& i& w2 n            x=i;
            y=j;

# m. k5 V$ [' z1 |7 |3 \8 i        }
    }
6 A0 U& {. K: C# B   
    if(a[y]>0)
    {
) e6 F5 g4 W" r2 l: a& ]        c[x]=y;
        sum+=max;//总喜好度加上添加
6 t, v0 V8 |0 f: S% s        a[y]--;//区域上限人数-1
. I" U# `9 l# \5 j        for(int k=0;k<3;k++)
! T  X8 P7 \' Z  Q" ~  u        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
! ?# f/ @# s* I0 T$ o% N        }
$ x. r% o1 [2 M2 t9 r    }
    else
# e7 c; N/ S& u1 P    {
        b[x][y]=0;
    }
   
- {% q) M8 [$ o    return sum;
$ v" S  M- Q; v8 O* T- h}
int main()
{
8 o) Y( x8 d) _+ R6 n3 p1 @   
2 J) V! [3 K( v: s5 Y    cout<<"input 3 zone's limit:"<<endl;
4 q: u* \' M3 m' p9 u, S# F- [    for(int i=0;i<3;i++)
    {
5 y0 w8 Z6 X5 g0 p. D$ @( q$ _0 ~        cin>>a;
9 w2 H7 x& r1 d# s* ?! {. i    }
" A- O/ [. r% O* ^5 {$ J0 D, K; Y    cout<<"input 3*3 actangle:"<<endl;
. w. j4 x: N2 j$ i    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
# @; s4 P& @: E+ ]1 R& S, D# {    {
        cin>>b[j];
- p7 G, |6 v# t7 ^2 g+ K. [    }
    for(int k=0;k<9;k++)
- y0 d2 D( Q/ R# J; v: M    {
        max_num();
/ f1 Q- ]+ K! W* y    }
( }* m# U# B/ u% M) t0 x   
- J% H  i& w) ]3 F" g    cout<<"sum="<<sum<<endl;
" L7 h$ {) E5 j/ p$ e! d$ k. |- A    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
. _2 }) v' V! N% |7 ?# s    }
    return 0;
}#include<iostream>
( ?- v' Y+ M" T, [8 b0 B( gusing namespace std;
$ X# Z1 A% r' O( `3 Wint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
int sum=0;
int max_num()
{
7 c; E* C# {& e# _    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
" F/ Y  ~% q* ?1 N: m! J; w4 d3 D    for(int j=0;j<3;j++)
9 _- Y2 P' M1 H, |: R; r    {
        if(max<b[j])
        {
            max=b[j];
            x=i;
            y=j;

        }
* E7 d3 G: z# v0 Z    }
! b" l2 ]1 c2 @$ n0 Z6 H: w  q   
3 v' q! ?' L* H& U. s    if(a[y]>0)
    {
$ o) j7 C$ E  ~! j/ X+ g        c[x]=y;
# O, M% D# O% ~" q% ^7 U& C        sum+=max;//总喜好度加上添加
: S. I) c0 O* {' f! N7 J. f/ g        a[y]--;//区域上限人数-1
( I: r  j+ O& \8 D7 I" k        for(int k=0;k<3;k++)
        {
" m, M  s) y( q/ o4 h/ o            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
% J$ v5 x+ c( i0 ~. l        }
    }
2 R9 O, u6 i, F$ J+ W7 D    else
    {
! O; y' K' Z# t" J- ^        b[x][y]=0;
    }
5 `3 f3 @. Y% K% y! o( }. I- [) F- R   
7 H& C7 \& v4 l9 i    return sum;
}
int main()
- U. x" Y& x7 Q0 ?- `( H1 ]{
7 {  W* ~! k2 N$ A9 W& H- g   
5 _. W( X; f+ `$ E! ]  R5 N8 k8 ]    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
    {
        cin>>a;
    }
2 V4 ?" T( {' T4 a    cout<<"input 3*3 actangle:"<<endl;
4 H9 Y7 s: }" c1 z    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
9 d* S/ Y; F) F. m5 {' q* l    {
: M0 ^$ N4 `( N        cin>>b[j];
    }
    for(int k=0;k<9;k++)
    {
        max_num();
! P7 l2 n! Y4 E2 I    }
6 Z( K4 M( t1 l" w  G' b   
    cout<<"sum="<<sum<<endl;
    cout<<endl;
8 e" U2 p* P; u3 l, Y; q; }    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
/ b0 |* p# |! O& G    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
$ V  V  @; v$ e; I* W    return 0;
}

---

作者: 厚积薄发    时间: 2010-5-6 18:48
编程代码二：
% u+ I' V7 Z$ a, E3 \#include<iostream>
3 j) ^+ m" Z7 O, _, k# ?! v& t#include<cstring>
#include<ctime>
using namespace std;
: N: ]; J9 t" W) h/ V4 E) ~5 qclass ifo{//矩阵的元素
4 U. [9 @4 n, @0 y; o; e% Q& L    int clerk;//员工号
    int area;//区域号
* ?6 J9 `9 \; [3 ]  a  p  O# e    int per;//爱好度
public:
6 l( @# D4 p4 F0 e; y" r    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
    int getclerk(){return clerk;}
$ Q7 U9 v" ^9 }/ Y; C& a$ ~; r- {% W    int getarea(){return area;}
7 V$ P; Y- p% L0 A. \    int getper(){return per;}
1 a6 K6 f4 M7 e% T    void setclerk(int i){clerk=i;}
    void setper(int p){per=p;}
    void setarea(int a){area=a;}
' C- \8 u; E; J8 |: `};
class area;
class clerk{
    int areanum;
    bool isin;
    int inarea;
8 D7 k* R, ]3 b/ W7 z! N: ~public:
    void set(int num){isin=true;inarea=num;};
: Q$ ^8 |) ^3 @, v* L' X1 i    void setisin(bool b=true){isin=b;}
    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
0 [2 a+ B' I: U& q7 `};
class area{
5 U# s* ]& p& |    int num;
' F* H8 e* @3 E" q& v- A    int max_num;
7 W* f7 }% `# T% h7 Apublic:
    friend void set(int);
9 v6 p' P. s4 ?0 g2 o- n2 z; `0 D    int getnum(){return num;}
8 k7 o2 u- y# l. x8 {9 Y    void setnum(int number){num=number;}
    int getmax_num(){return max_num;}
    area(int number=0){num=number;}
; m+ n& ?# c' T) L, p5 @$ |" v: o    int getclerk(){return num;}
    void addclerk(int ps){num++;set(ps);}
};
/ v# m6 E& M- {( ?* Vvoid getorderbyper(ifo array[]);
$ _' x6 L: C9 X* m8 cint areanums;
void main(){
    //input
    cout<<"输入区域数：\n";
    int area_num;
  D* ^8 H1 b7 i& L4 @- G6 b5 B    cin>>area_num;
    areanums=area_num;
    cout<<"输入员工数：\n";
6 s) z8 u2 y2 }& w* G. z0 ]* A    int c_num;
    cin>>c_num;
    cout<<"依次输入每个区域能容纳的员工数:\n";
+ k; r4 z2 B. A- g. b$ X    int *max=new int[area_num];
    int nownum=c_num;
    while(nownum){
' D% d9 t! C. b7 \3 {        for(int i=0;i<area_num;i++)
        {cin>>max[i];nownum-=max[i];}
& H- G. y9 f* r) K/ ?- `* G, w' i        if(nownum>0){
            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
            nownum=c_num;
3 ?" v$ L9 G; P5 s% h$ W7 `' `3 }        }
' K  s; t% k! w( k5 u  G        else nownum=0;
    }
& Z5 B8 l! I7 j6 ?    cout<<"按行输入每个员工的偏好：\n";
8 S/ f" n8 y( P    ifo** per=new ifo*[c_num];
. v; h$ M6 A( M% M    for(int j=0;j<c_num;j++)
, f$ v( ?7 z: ~+ r9 O) [7 i( s        per[j]=new ifo[area_num];
    srand(time(0));
    for(int c=0;c<c_num;c++){
        for(int a=0;a<area_num;a++)/*
        {    int p;cin>>p;per[c][a].setper(p);
1 S% f5 y, n3 I* C. ^            per[a][c].setarea(a);
            per[a][c].setclerk(c);
; F# v" b3 Y# e  e& j        }
        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
- q. B0 j# _3 ]        {    per[c][a].setper((rand()%60)+40);
: I9 w/ L' Z" q1 s" z" c3 z            cout<<per[c][a].getper()<<'\t';
        }//测试时懒得输入，故以60-100的随机数代替。
-    cout<<endl;
. d& w/ q+ Y/ o    }
  g1 ]: }' w' |    //output
1 ?( k1 u( }* U( K3 @3 V" d% z* v        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
        clerk* people=new clerk[c_num];
0 Q! d8 l+ y4 H  O+ u# j        area*  areas=new area[area_num];
2 k* g3 Y" p# i! x9 I        int totalper=0;
        for(i=0;i<c_num;i++){
0 L/ t7 {0 k9 a/ D* g2 G            for(j=0;j<area_num;j++){
7 G% w) I1 E  O6 @            if(areas[per[i][j].getarea()].getnum()<areas[per[i][j].getarea()].getmax_num())
                people[i].set(per[i][j].getarea());
( L6 \- x3 G& R' |7 i7 h                people[i].setisin();
                int number=areas[per[i][j].getarea()].getnum();
: m; N$ J  E( M" Y                areas[per[i][j].getarea()].setnum(number);
& o" a, F% i* m- g6 x4 p                totalper+=per[i][j].getper();
. _4 X% k8 I+ H2 U  L- \                break;
            }
! k# ?1 ]! ^+ g, s; @* g* o" p        }
        cout<<"能达到的最大喜好度为："<<totalper<<endl;
}
void getorderbyper(ifo array[]){
* Y) `. [" Z6 [0 d1 t    int max=0;
4 h' b9 D4 R, R8 u    for(int i=1;i<areanums;i++){
        for(int j=0;j<areanums-i;j++){
) s. s+ X- u) O: _' z7 z0 }        if(array[i].getper()>array[max].getper()){
            max=i;}
8 X& c: s9 ^. O8 X4 }/ J) T8 q1 o5 C        }
        ifo temp=array[max];
        array[max]=array[areanums-i];
0 l8 U/ p4 q' k8 c9 u        array[areanums-i]=temp;
        max=0;
    }
}

---

作者: 厚积薄发    时间: 2010-5-6 18:49
代码3：
/ b# L' q  x& P, n0 h/*
算法思路：
' C% v# y3 {4 Y/ N0 P+ ]（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
1 F& {4 l/ Y! D" E% r; P再加，该人的所有喜好度设为0，
& ^% {8 g+ [3 p4 {/ a! Y4 r（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
% C8 F6 c5 L& X2 b(4)最后输出总喜好度。
, r& a6 r3 d- W9 h) n( e" Z0 t1 a! E*/
) y) \% I$ h7 F& n# N#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
9 r- q3 }' F: w# d" O1 hint c[3];
int temp[3];
9 y( n* O9 v* Eint sum=0;
int max_num()
* H/ `5 q8 X5 U& m+ g1 ~{
! a2 d( ]6 j. q. f, a4 d1 ^    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
  m: N7 C! C& J8 t7 m0 m    for(int j=0;j<3;j++)
    {
7 @3 \3 J* a' v4 `" P9 r1 _        if(max<b[i][j]&&b[i][j]>0)
        {
            max=b[i][j];
. g+ X4 ]2 L+ a' d2 C$ G            x=i;
9 P# N, n5 Z: C% z            y=j;

        }
& N: S7 K/ |$ @" w8 T5 p    }
' I$ p, a$ V2 @- ?% x   
    if(a[y]>0)
    {
        c[x]=y;
1 y9 {: f8 l2 V% a        //cout<<"c["<<x<<"]="<<c[x]<<endl;
        sum+=max;//总喜好度加上添加
        temp[x]=max;
, c) H8 {4 R! K+ y+ j. k        a[y]--;//区域上限人数-1
    }
& f0 W8 S7 K, |( n    for(int k=0;k<3;k++)
    {
        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
1 j' L' Y) e/ f, X    }
    return sum;
; {  G9 g* h- l3 u( I* h% n}
" n+ \: X* _- x8 x6 }int main()
% U- u* Q4 P3 L5 Z1 f6 f  M{
0 {0 f6 I4 h, d" O   
' e9 d; X; ~4 t8 n' W& @  b. T! P    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
    {
% E1 m$ A0 ]: P! L5 m4 d. ?        cin>>a[i];
    }
    cout<<"input 3*3 actangle:"<<endl;
6 G! g& l7 Q+ F* _5 U3 B8 t( B    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
- I- J1 O; `; S( i2 r    {
- T! Q7 b& w3 H" l) ~        cin>>b[i][j];
/ U, f' h' j% b    }
- b' M' D8 I, S- a! P! b    for(int k=0;k<3;k++)
! Z3 D+ H; S6 [/ o# o8 q5 L! [    {
        max_num();
    }
3 Z( }0 ?& N) d; b7 v    //cout<<"sum="<<sum<<endl;
    cout<<"sum=";
: Q+ P( k0 T- v2 e$ t    for(i=0;i<3;i++)
3 }9 |' t+ @$ v1 W5 Y/ c    {
        cout<<temp[i]<<"+";
4 i5 `* |7 P6 k( z* R2 t7 H    }
    cout<<endl;
    cout<<"reslut:"<<endl;
' f: }/ l3 h) k    for(i=0;i<3;i++)
1 `  M8 Y. s3 t2 T) X/ j    {
' T( D  l7 a- J0 `) e        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
    }
0 I' C! H0 X, c9 h, h! S8 u    return 0;
0 D5 e/ r6 h# _5 O6 Z4 d, d$ F}

---

作者: 葉_浅浅    时间: 2011-2-22 21:04
其实我一直觉得楼主的品味不错！呵呵！
数学中国社区分享快乐！
5 S  g; s  v2 }" N1 ^

---

作者: _Amy_    时间: 2011-7-3 14:01
程序最头疼

---

作者: ehi28    时间: 2011-12-11 16:23
嗯,不错,支持一下.

---

作者: schnee    时间: 2012-1-28 21:30
必须顶！！！

---

作者: 久玖九王    时间: 2012-10-1 20:18
C++,可是我喜欢c语言的，只是现在还没有到家

---

作者: hbdkfk2    时间: 2013-1-14 10:05
看不懂！！

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5