数学建模社区-数学中国

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

---

作者: 厚积薄发    时间: 2010-5-6 18:47
标题: 2006 年百度之星程序设计大赛初赛题目 5
座位调整

- P1 d; Q* m, l4 o! H% W题目描述：
* s: K0 k( q5 `* ^" }
百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。

: |9 Q2 A" b9 I9 ^* t0 q' i% V调整的方法如下：

1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。
) w7 T6 D/ o' e
3 S& Z& n6 H) f/ y2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。
$ s, C$ H. d; A& X4 N
3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。
5 n, K+ y# r7 q9 T
数据输入：

, p& K: w" C: m9 h第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。

* m* H' |  d( c: p6 `5 p2 O' v5 R第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。
7 C0 F' u! S) h5 ]4 v. q
! v  ?& P4 _/ K; o& u" z紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。
, |( @0 |, T4 u6 K* [. T: L7 J4 p1 x
5 E& w7 J5 r: E" z3 [- w: F: \答案输出：

对于每个测试数据，输出可以达到的最大的喜好程度。

) I% X  W7 p- I5 s2 ~# X# ~输入样例

5 a/ z2 n* M3 h  E+ e/ H
6 l2 r) }5 o6 i1 F* Y2 u% }3 3
- `, a3 Q8 }* L
1 1 1
) K; h. v. k" ~% E5 M; j% f
100 50 25

100 50 25
% {& T% a! A# {- }- o, Q: ]
100 50 25

) b! t3 u+ P& K# [输出样例

175

2 b  f. T( y! h' b8 o/ z+ c7 i

# @$ c6 l" ~, h
! G% V9 C3 S7 j! r- a1 n/ B数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175

---

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


2 Z; U5 R+ {7 g3 @+ Z+ B#include<iostream>
4 L  F+ _( ^5 {6 e  Wusing namespace std;
" j2 R& e! O$ h  I! tint b[3][3];//M*N矩阵
) s& c4 r' O, M6 g& T) n/ rint a[3]; //区域人数上限数组
8 P8 L$ P8 V8 L2 \& f' t. }- ?0 uint c[3];//记录某人i去的区域j
2 T% k; L9 [5 P$ eint sum=0;
. p9 E0 M! {0 t1 [' ]1 \4 cint max_num()
" t: _+ [5 Z5 v0 U" S; P{
7 ]1 Y/ `/ j* n* M% B  c    int max=-32767;
' t1 }1 S* }- ~, L* C: q# y( P    int x,y;
    for(int i=0;i<3;i++)
- A# b) d6 v$ R0 |( T" A    for(int j=0;j<3;j++)
8 K) s/ f; `* _% R    {
: U7 W( {7 V, M        if(max<b[j])
; {( y+ E  ?# |4 Y6 [) S6 v3 ^        {
            max=b[j];
            x=i;
4 h3 q2 g0 V7 P& }: Q0 s. y            y=j;
" w& ?* G' J' \  A+ {5 r
        }
; p% i3 u% _5 S$ T* k% W( f    }
   
% {) G1 T2 ~6 x4 O% @/ b    if(a[y]>0)
2 A* b  {. x+ k3 d( t    {
: [  f/ \3 g9 F) i% E/ g        c[x]=y;
        sum+=max;//总喜好度加上添加
" s  n+ j8 s' N  q$ h        a[y]--;//区域上限人数-1
0 u0 V8 N! {# i6 L# Q( ], {) K+ {        for(int k=0;k<3;k++)
        {
' R& U2 \# C1 z            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
    }
, q' i; X* g0 H' T6 q    else
    {
        b[x][y]=0;
% Y& v$ S; C3 T' d$ P7 [  j$ J    }
   
    return sum;
1 L1 k3 ^- N! C9 Q4 L}
. R, P# C6 T$ \; Oint main()
4 H$ m& p$ o5 z0 I* P: b! A4 D{
   
' W  l: j- q7 I4 f& [1 r+ J    cout<<"input 3 zone's limit:"<<endl;
- M0 V; P3 U& l+ S6 Y+ J2 |  Q    for(int i=0;i<3;i++)
    {
        cin>>a;
    }
3 Z, c2 B" ~3 X( m0 M: I    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
2 T( v' A# ]$ o& M: t0 M        cin>>b[j];
    }
    for(int k=0;k<9;k++)
$ w5 z9 a7 f1 q( O: [6 K) A# o    {
" {$ E; k" a( W, a        max_num();
    }
   
; ~5 F* b5 N$ G( K& U/ p) r    cout<<"sum="<<sum<<endl;
    cout<<endl;
+ q- {: o6 @( o# P    cout<<"reslut:"<<endl;
& N6 K8 U+ x" c5 \/ q    for(i=0;i<3;i++)
* p" F7 R! O+ q. a- c    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
    return 0;
}#include<iostream>
using namespace std;
0 n+ n" K0 M3 h6 `7 x0 _' Zint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
6 E5 h# T" n# L, F1 D  D, Jint sum=0;
1 k% d5 H! l  _' h7 mint max_num()
6 k" ?4 |7 P! r{
% ?" D. |% H; T' A    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
6 X( {" J  R+ d, ~( ]' N    for(int j=0;j<3;j++)
    {
        if(max<b[j])
' K6 Z) e# o6 e9 z2 y, r& ^/ {        {
- Z9 |  N! `1 J. v            max=b[j];
8 W1 S+ V1 A$ y            x=i;
& l+ f. I* n# `. ^; a2 I' U7 A            y=j;
5 [4 D; D, ]- R7 B- b4 |2 A6 ?1 X
        }
: `& f1 _, S  {    }
   
    if(a[y]>0)
' b; P( J0 P) w5 h& D) l  T5 |    {
4 V6 x" i1 J& d3 s        c[x]=y;
! j- I9 b3 n& W( ~% k        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
7 [9 A1 v. f- X9 _        for(int k=0;k<3;k++)
        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
5 [8 V; z  r$ R; J8 o, r9 H        }
    }
1 i! r3 j8 D$ n8 Y- U! o2 C    else
    {
        b[x][y]=0;
$ r2 S1 |8 ~7 G$ y4 W) q+ w5 @    }
   
    return sum;
  y( X- a( }) G}
, ?! E& I/ k2 R" ~, w* F% N' Zint main()
{
   
) N$ u0 b1 o' r& E& H9 X    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
    {
        cin>>a;
    }
    cout<<"input 3*3 actangle:"<<endl;
: n1 v2 ^; n/ ~% u7 A' [    for(i=0;i<3;i++)
2 {! ?8 M8 J, w! _5 j    for(int j=0;j<3;j++)
    {
        cin>>b[j];
    }
1 K7 i4 y  S. l    for(int k=0;k<9;k++)
    {
" j/ n# v  a# A( P- v& c- {4 F" N        max_num();
% l& }4 \- O9 \    }
   
$ g1 l6 ^/ t) k- F3 X" U' A    cout<<"sum="<<sum<<endl;
    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
; L2 B$ Q" o+ s5 w    return 0;
+ J% l( Q, n, L+ l9 X' @! m* ?}

---

作者: 厚积薄发    时间: 2010-5-6 18:48
编程代码二：
) Q! y3 m' n1 n+ a& n9 ~#include<iostream>
#include<cstring>
#include<ctime>
' W3 w8 [+ J1 f( c+ o4 Wusing namespace std;
- C7 Q! _* R# E) Z5 Y8 r3 tclass ifo{//矩阵的元素
# t8 M) y+ }7 k) ]+ z    int clerk;//员工号
; |8 M0 F: t  n  Z$ u; o    int area;//区域号
9 X. D3 Q/ M9 Z3 W4 `! [    int per;//爱好度
: y+ N0 a5 b8 B3 _! c9 _$ U& N6 M$ d7 upublic:
    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
$ o. G0 @& A0 @0 a; n    int getclerk(){return clerk;}
3 ?+ r6 F" ]3 J0 d4 _' `: `' F. v    int getarea(){return area;}
    int getper(){return per;}
    void setclerk(int i){clerk=i;}
5 j* M( c8 G# T/ S. v( j    void setper(int p){per=p;}
    void setarea(int a){area=a;}
, |" i( s8 h, ~: e+ h/ [  H' `# K};
1 a6 a6 |0 f5 Dclass area;
1 B4 v' `" Y  ?% Jclass clerk{
    int areanum;
0 n) g  \+ s. z9 O/ X4 D    bool isin;
  E$ ^$ m; z9 M6 a    int inarea;
, N4 Y) C) o) u0 Epublic:
9 Q, \* S( Z0 M) v# H& @    void set(int num){isin=true;inarea=num;};
( C- \% D$ R/ q) a    void setisin(bool b=true){isin=b;}
/ N3 [8 O* c2 S, D9 v' X/ W    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
* N$ V4 d) J) s& j  K0 p# J};
4 s. k5 Z1 S: ]! d' i3 _% Xclass area{
  m2 C( {: G$ W; }4 ^    int num;
    int max_num;
; m; e9 G0 o8 Q& j; @public:
. ^$ @; y4 h4 l6 C' _    friend void set(int);
4 f3 h6 @. v. I1 ~' A( c    int getnum(){return num;}
) _2 a! ~0 w% \9 a3 W    void setnum(int number){num=number;}
7 a' f6 P1 v, i8 D, p    int getmax_num(){return max_num;}
    area(int number=0){num=number;}
    int getclerk(){return num;}
, Q+ i& f! D" d4 J* R: V% g    void addclerk(int ps){num++;set(ps);}
};
' _* V3 I1 @& o& d- Z1 _void getorderbyper(ifo array[]);
int areanums;
void main(){
    //input
    cout<<"输入区域数：\n";
    int area_num;
    cin>>area_num;
5 c6 m$ X: a6 `) B6 w8 f& b    areanums=area_num;
' _, s6 c$ M* n1 t    cout<<"输入员工数：\n";
    int c_num;
9 ]. z9 ^/ r- \8 I9 q: t    cin>>c_num;
    cout<<"依次输入每个区域能容纳的员工数:\n";
    int *max=new int[area_num];
  l0 Y; S1 l* Z: I/ v& Z    int nownum=c_num;
    while(nownum){
/ M/ s5 Y8 R* I$ ?* ?        for(int i=0;i<area_num;i++)
. g- z8 Z5 K/ h# o        {cin>>max[i];nownum-=max[i];}
        if(nownum>0){
            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
) F4 m7 E, v2 a+ K- N, |4 q            nownum=c_num;
        }
        else nownum=0;
    }
8 E7 T* o" \9 d% h- g6 e    cout<<"按行输入每个员工的偏好：\n";
5 l# o3 ]7 R% L0 x/ Q    ifo** per=new ifo*[c_num];
( P( `9 X& I0 l& Z4 d, E8 d    for(int j=0;j<c_num;j++)
, a8 F! e$ W/ p- Q: q        per[j]=new ifo[area_num];
9 [( n" U" u' c9 k    srand(time(0));
    for(int c=0;c<c_num;c++){
1 K0 Y) m4 I5 C% y6 v' u        for(int a=0;a<area_num;a++)/*
        {    int p;cin>>p;per[c][a].setper(p);
% N, g( u9 \, C! k& p            per[a][c].setarea(a);
" ?. [9 o9 I' f; W* d            per[a][c].setclerk(c);
        }
        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
        {    per[c][a].setper((rand()%60)+40);
            cout<<per[c][a].getper()<<'\t';
( f7 {& a9 K, N, U( X        }//测试时懒得输入，故以60-100的随机数代替。
-    cout<<endl;
: W4 B0 h8 ^, q" v    }
    //output
        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
        clerk* people=new clerk[c_num];
" \% m2 K7 \) C5 x        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())
$ Z! b8 l4 z3 @" A* i! U# e                people[i].set(per[i][j].getarea());
7 m' m1 W/ t, ~) P. k8 Z                people[i].setisin();
                int number=areas[per[i][j].getarea()].getnum();
                areas[per[i][j].getarea()].setnum(number);
                totalper+=per[i][j].getper();
                break;
3 i% d* s9 Q9 q6 Y1 j! Q            }
7 t: Q- m8 X1 E. j7 }% s% b1 @        }
        cout<<"能达到的最大喜好度为："<<totalper<<endl;
3 w0 @+ }' z  s% j}
void getorderbyper(ifo array[]){
1 a$ Y$ I  r9 Z4 X* t6 |' E" \    int max=0;
! m9 v4 T4 R/ y8 o    for(int i=1;i<areanums;i++){
. f4 A5 ]0 P  m; S/ V        for(int j=0;j<areanums-i;j++){
' X8 D: N' X! X& |; i; r0 B- C        if(array[i].getper()>array[max].getper()){
            max=i;}
! a. C& R- G4 s" {: v$ l/ V* g        }
7 f# E# M. b5 `. E! w. l        ifo temp=array[max];
        array[max]=array[areanums-i];
        array[areanums-i]=temp;
        max=0;
5 w7 A) T/ E" k7 e    }
, a8 j0 H0 C1 E0 Z, Z' x" L}

---

作者: 厚积薄发    时间: 2010-5-6 18:49
代码3：
/*
- [# ~6 Y5 _' m8 w6 u算法思路：
（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
+ G; `  D' h% Y3 e再加，该人的所有喜好度设为0，
（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
8 p2 I4 B; {9 ?* }! ?（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
(4)最后输出总喜好度。
2 E5 X, \# l) o, d*/
#include<iostream>
/ r. i/ ?2 Q- s2 S/ lusing namespace std;
5 l! r: Y) o- S( cint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];
$ ]! Q6 b3 r7 Uint temp[3];
6 n! }8 O9 w+ {) Lint sum=0;
: J- u  v  z5 i& v: Qint max_num()
{
) J3 \$ O0 O  j4 v: Y( ~0 @    int max=-32767;
7 a8 F/ j; Y* g' ^: L    int x,y;
1 k5 ]" K" J0 z6 }' E* T    for(int i=0;i<3;i++)
/ l0 Q4 P! e) |/ P    for(int j=0;j<3;j++)
9 A9 U) l! Z4 n" p+ T, l' A( c% b/ v    {
7 ^, I/ N4 t4 X3 ^" i+ x/ i* d2 W        if(max<b[i][j]&&b[i][j]>0)
        {
0 n7 \. l% E; X' S            max=b[i][j];
            x=i;
            y=j;
6 i% X' K" E& C6 t
8 Z- {. g' ?: i- m% F- [# |: v        }
' P4 M) ^& S2 G' H, M/ c    }
& g& {+ O& b8 t- F   
    if(a[y]>0)
9 _5 t+ j6 I, T    {
7 R) j- a4 a/ `# G0 Y        c[x]=y;
; o& w1 t9 @2 N" @! K        //cout<<"c["<<x<<"]="<<c[x]<<endl;
9 O7 l8 q3 M9 i! @1 s, ]$ w2 i        sum+=max;//总喜好度加上添加
8 O& y# s3 f# c' t% z0 Y        temp[x]=max;
9 _4 C: G# k. i, G        a[y]--;//区域上限人数-1
8 V8 O, f5 r* _: f9 {4 U) c    }
    for(int k=0;k<3;k++)
    {
; M  @: X" p6 b% z. L+ c3 P3 q        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
    }
& I# D6 x# ~: L# y* @& }% j    return sum;
}
3 p1 y5 z+ i* l& G! lint main()
{
7 J: |( N* ~- F2 J1 n9 U0 R  `   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
    {
        cin>>a[i];
    }
    cout<<"input 3*3 actangle:"<<endl;
% B5 _9 Z" |/ b# j  b    for(i=0;i<3;i++)
1 W+ N9 b, G6 F% G* D    for(int j=0;j<3;j++)
6 Q( q! ^0 s( f, e2 ^, K7 J    {
/ P0 i' @$ m5 S; ]6 _, u; c) l# u        cin>>b[i][j];
    }
    for(int k=0;k<3;k++)
    {
        max_num();
    }
% G2 L& Z& A; K* e    //cout<<"sum="<<sum<<endl;
! H- l7 T7 Y6 ?1 \# ?& R    cout<<"sum=";
4 g# I7 W* L5 U' E: ]5 u    for(i=0;i<3;i++)
; x3 Q* ?! F1 Z    {
- l; w" w8 v; [$ o; R8 Q" q6 H' n        cout<<temp[i]<<"+";
    }
    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
7 ?" N, X# T3 R' G' Z        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
    }
    return 0;
}

---

作者: 葉_浅浅    时间: 2011-2-22 21:04
其实我一直觉得楼主的品味不错！呵呵！
: J6 \. e% p1 d% Z# H2 _数学中国社区分享快乐！

---

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

---

作者: ehi28    时间: 2011-12-11 16:23
嗯,不错,支持一下.
, x3 M- m2 F" j

---

作者: 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