数学建模社区-数学中国

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

---

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

* k2 z$ ]4 ]" p, |题目描述：

$ N' v8 T2 z# p/ S) V1 w5 A- V) Y百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。
9 I' p9 ^$ P. G* O* \+ F
0 {2 L; J4 m7 I1 b4 y8 A! T调整的方法如下：
. g: K- n4 P* X
3 K8 |9 w/ a6 l0 f$ I: P2 f1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。

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

- Y2 l% z( Q# @# Q( y5 w$ S3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。

数据输入：
& H+ O& w3 a3 G0 m, m6 _
第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。
$ b) g, j+ H1 }' ?2 l/ c: i
: ?- R0 ?1 v4 g, y" [2 [; T. m第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。
; e, s3 S) e+ p. a' ?- O
, W- Q4 B! W/ J/ b2 G" J6 g9 V紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。
5 ?/ l! x* `1 P/ S
答案输出：

+ f; d5 _% h* i$ t对于每个测试数据，输出可以达到的最大的喜好程度。

$ P0 ]/ ~4 h. F: ~$ t' _  M' ]输入样例

3 3
# M( c, w' {0 K- e7 }
9 B- `9 U, O/ Z7 F6 j. X; p1 1 1

100 50 25
/ J! U6 l1 W! X+ p" L
100 50 25
( {0 `) y! C7 j4 |1 E+ {% B' ]9 C
100 50 25

; Q3 E& ~% r' f- U" c$ V/ Y
输出样例

175
; w2 P( W* z" r/ X- |' h$ m

$ L$ Z; `9 t" f' \2 x9 }) W
0 A) I* f4 Q- \" I' r/ T+ V* H( I数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175

---

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

# \) ^+ @9 N* g& Q5 p3 @3 r
. k' y* z$ s9 P4 o: r6 [' R6 L#include<iostream>
" u/ }4 g0 z* W- |5 Yusing namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
- \8 p7 [3 M% N! u) L2 c) Qint sum=0;
# I3 v/ u/ A# U2 Dint max_num()
{
    int max=-32767;
. n( B1 o# k2 }6 u  n8 K8 K    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
* f: ~  i5 f4 i: C  C1 [! \        if(max<b[j])
        {
            max=b[j];
            x=i;
* y' c" [% \: F! F            y=j;
3 B5 X1 f/ h+ d& G  ?
0 @$ b  q+ x. h        }
0 q+ O, a2 Z5 B0 f% _' t& @    }
   
% S1 N2 d2 L4 j6 W    if(a[y]>0)
% _9 \8 a' F; r0 `, k4 f4 `' r    {
4 `: n" L! [% U' }$ f# k; h        c[x]=y;
        sum+=max;//总喜好度加上添加
3 {% G4 v0 A, J: d; U4 u        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
        {
+ d% v, }7 C6 b/ [2 A9 N            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
+ h% ?" ?5 F: q) R: V& L5 a9 u' P        }
+ S( R, P* s% v7 Q0 c    }
    else
    {
3 b; L% Z# n( w$ P        b[x][y]=0;
    }
   
    return sum;
}
int main()
{
   
    cout<<"input 3 zone's limit:"<<endl;
) W/ w/ T5 R# g    for(int i=0;i<3;i++)
' }( ]" o/ \7 @8 X- I  X$ Y    {
/ R1 j* d; l  \) u- R( n3 O9 [        cin>>a;
    }
- m* a  O! X* N$ v9 |    cout<<"input 3*3 actangle:"<<endl;
/ m) G, P' A1 e, W0 G    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
* q1 A6 }5 E# U0 p+ v# ]* ~    {
5 m. b- t% p# M" X        cin>>b[j];
    }
! g, G8 T7 u; `4 X: \9 u    for(int k=0;k<9;k++)
    {
0 F% u6 T3 x; z) N        max_num();
: n9 j% e- P: q  h& H3 u    }
   
' ?( _3 D% X! ?- b1 h    cout<<"sum="<<sum<<endl;
: p4 p5 }0 s  |; R# R  I: A    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
: T" i0 u' _, O# X! Z- {6 U2 J7 ^    }
+ V$ C, i* _2 x4 V" v+ N! q) e- ^    return 0;
4 @8 T/ L7 S7 t& l4 u- e}#include<iostream>
using namespace std;
' J* i! U( x: Z7 i1 Q2 Vint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
7 y- |9 z$ c4 H$ qint c[3];//记录某人i去的区域j
. i4 R* K2 f* S% c6 G3 C- bint sum=0;
, b/ R7 j% U' U3 f6 \3 J2 |$ hint max_num()
{
    int max=-32767;
  |+ u- N- h  K/ ?, @: k* A    int x,y;
- Q; n8 \8 P( D3 e: R    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
  Q' H* j# u% S, d3 |6 R; Z4 r        if(max<b[j])
        {
            max=b[j];
' u9 o" f, o1 e, ]1 _5 _3 a            x=i;
* d; ^1 O! a3 |$ W. B            y=j;
7 y% r' C2 j4 a/ I2 c4 K
        }
    }
   
2 n) Y# J7 s/ l3 }; G    if(a[y]>0)
    {
7 ^! D, `6 u- n$ @5 N        c[x]=y;
        sum+=max;//总喜好度加上添加
1 s  T* ^9 R" B6 H) p        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
    }
    else
3 a. Q2 Y0 Y4 U. s3 `    {
7 V  e4 {8 ]/ U. x        b[x][y]=0;
; r+ `/ }9 C, j# @2 n  b7 {    }
   
6 L  d% Z' M5 k7 Z( H0 n3 k6 p. W7 ?9 s    return sum;
}
int main()
% J& K" v3 C1 H{
   
. V  U# o" f8 M2 W    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
$ O! J4 `; W' V3 [, o8 i" Z6 c    {
7 D: V  `3 i% ]0 I0 L2 C        cin>>a;
0 L' }; L3 B0 U# Y& i9 S( z  P    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
4 P  I. [% n  U; y6 y* g* `+ k    for(int j=0;j<3;j++)
    {
6 d% n, i# G2 B        cin>>b[j];
    }
    for(int k=0;k<9;k++)
( r- G  J* h+ E6 `    {
        max_num();
8 I0 n" p( \( `! f; Y0 Y    }
9 q  Z, E7 `$ V- ~, _   
    cout<<"sum="<<sum<<endl;
4 x& h# X# y" N' E0 p2 R    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
$ ^! @/ f6 n3 f! H) n; E/ _    {
+ Z# V( o' y! ^: J        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
    return 0;
+ w; i) w$ p5 ~) f( @  S}

---

作者: 厚积薄发    时间: 2010-5-6 18:48
编程代码二：
#include<iostream>
#include<cstring>
8 X; v- ^& Y, H* \#include<ctime>
using namespace std;
class ifo{//矩阵的元素
    int clerk;//员工号
    int area;//区域号
    int per;//爱好度
public:
    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
/ W- G5 {4 K" U6 _$ W4 \; D    int getclerk(){return clerk;}
    int getarea(){return area;}
    int getper(){return per;}
    void setclerk(int i){clerk=i;}
    void setper(int p){per=p;}
, |! R+ [+ n/ b" s: z/ B    void setarea(int a){area=a;}
};
* m+ O- W" q% z/ o8 oclass area;
8 [9 v) m* X6 b; J# S% fclass clerk{
    int areanum;
    bool isin;
    int inarea;
public:
    void set(int num){isin=true;inarea=num;};
    void setisin(bool b=true){isin=b;}
, ]5 K5 {7 n' O, N& I+ z    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
( _& A+ f7 }$ A: ]' q: W8 p};
% K# \; J( r3 h5 Aclass area{
    int num;
    int max_num;
public:
    friend void set(int);
$ o) \  U: K( J% y2 ?' R    int getnum(){return num;}
    void setnum(int number){num=number;}
    int getmax_num(){return max_num;}
    area(int number=0){num=number;}
    int getclerk(){return num;}
( s4 h! z) f* d% V! U0 d- p    void addclerk(int ps){num++;set(ps);}
};
5 j$ i  p6 c) C0 k& M# k+ X1 `! Hvoid getorderbyper(ifo array[]);
6 S/ c! T+ D6 X/ V* @% tint areanums;
void main(){
    //input
1 Z$ A) ^; X5 a! Q! d9 D8 _  n    cout<<"输入区域数：\n";
. J$ f. T" g) a    int area_num;
    cin>>area_num;
7 @4 U# k* ~# ?; p    areanums=area_num;
% R3 K2 M4 M) o* S5 ?    cout<<"输入员工数：\n";
    int c_num;
: p  }# F$ p( K+ s    cin>>c_num;
    cout<<"依次输入每个区域能容纳的员工数:\n";
    int *max=new int[area_num];
/ {  Z& ~8 @4 P    int nownum=c_num;
    while(nownum){
        for(int i=0;i<area_num;i++)
        {cin>>max[i];nownum-=max[i];}
7 A9 d  Y- f  @9 F        if(nownum>0){
            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
            nownum=c_num;
        }
        else nownum=0;
+ R$ \) t' \5 v' {( R    }
% @3 o! Q3 v: q    cout<<"按行输入每个员工的偏好：\n";
, ^* |* O- M! A1 ~9 u% f    ifo** per=new ifo*[c_num];
    for(int j=0;j<c_num;j++)
        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++)/*
4 _/ o) W8 D: U' s# M        {    int p;cin>>p;per[c][a].setper(p);
! \# U" P( F4 C3 ]            per[a][c].setarea(a);
            per[a][c].setclerk(c);
8 e" g. y5 ~2 `- O        }
        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
- R0 L' _$ C2 G* ?9 O; h        {    per[c][a].setper((rand()%60)+40);
2 k$ h- g3 D1 i4 k. s            cout<<per[c][a].getper()<<'\t';
/ n- z$ P: {% Y( b5 B2 I6 X, u        }//测试时懒得输入，故以60-100的随机数代替。
-    cout<<endl;
$ Z* d; j; O7 A/ m) u    }
3 C3 o- j- X! {, B& D7 h    //output
3 S1 _- F) ]# w        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
        clerk* people=new clerk[c_num];
( v/ _* q! `3 ~/ K# h0 c4 f        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())
                people[i].set(per[i][j].getarea());
                people[i].setisin();
                int number=areas[per[i][j].getarea()].getnum();
6 x. r1 H6 l$ R1 c1 r  z                areas[per[i][j].getarea()].setnum(number);
                totalper+=per[i][j].getper();
" F& o, u) ?# ~( r* E                break;
* @1 h: S+ U2 K# D8 D            }
        }
        cout<<"能达到的最大喜好度为："<<totalper<<endl;
}
void getorderbyper(ifo array[]){
6 W$ M2 Q$ i# x- T1 Z. G) N2 S    int max=0;
    for(int i=1;i<areanums;i++){
; A9 k4 T+ o. R  Q0 t! v. a        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;
        max=0;
    }
1 F( ^7 w  q# _6 U# |}

---

作者: 厚积薄发    时间: 2010-5-6 18:49
代码3：
. J0 O2 J& C3 n& k" G& ]  q/*
3 G. p2 q( n# B算法思路：
2 n( Z" |& Q/ X! v0 z: V: L（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
' N3 w8 v4 V- ~8 F2 ?" d7 Y. D5 O再加，该人的所有喜好度设为0，
8 G! E/ @& P* h2 s2 N（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
' m( D" k. w# L, M" K(4)最后输出总喜好度。
*/
  V4 Q9 W9 _% A* N" i+ ?: `+ z0 n#include<iostream>
1 V! K% r. l% V& i# Y4 g% d' B' \using namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];
int temp[3];
6 f* d8 F$ `, h7 ?) pint sum=0;
int max_num()
' J# Z/ M$ s% m$ }% ]9 n{
    int max=-32767;
  T6 W4 K$ ~. n) p. Y    int x,y;
0 y5 a. z/ z# |    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
/ D3 j, H6 p7 l  i" @  Y* x8 x    {
2 o' Z, f3 K+ z0 _7 F! n        if(max<b[i][j]&&b[i][j]>0)
/ e; P/ P% ~# r+ @        {
            max=b[i][j];
            x=i;
% h1 i( ]3 j7 x            y=j;

: F7 \0 v* G. @# l, e9 h        }
; i: u7 z' P. L3 x0 g, z. b" J    }
' p" ], V) E4 U8 Y% M   
* ~  Q" C5 G+ N! V7 M; W0 ^$ v    if(a[y]>0)
    {
        c[x]=y;
        //cout<<"c["<<x<<"]="<<c[x]<<endl;
        sum+=max;//总喜好度加上添加
        temp[x]=max;
( d  S$ ]9 H4 J; B  S        a[y]--;//区域上限人数-1
    }
4 E  d  o2 e6 S% B4 I    for(int k=0;k<3;k++)
    {
4 E' E- S3 f7 I        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
    }
    return sum;
}
int main()
1 l2 r0 K7 k+ s9 t$ h5 K{
   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
9 E8 z) l5 W/ A8 q+ `2 k    {
        cin>>a[i];
( K; g, u' L4 Y8 t8 M    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
7 @8 m" G; _4 G6 W8 `: t; i% `2 w+ v    for(int j=0;j<3;j++)
+ r+ u3 N0 w: s$ I    {
        cin>>b[i][j];
6 ~3 Y- R+ Z" _" |    }
    for(int k=0;k<3;k++)
    {
9 m* v0 d$ y* u2 A) h        max_num();
    }
    //cout<<"sum="<<sum<<endl;
5 D$ t; B) n* p$ s: S! n! X    cout<<"sum=";
. P; U/ j* R; s7 V2 Y: u    for(i=0;i<3;i++)
/ n: ~! _  n) h    {
) q; W9 B1 [1 x! w. x0 I        cout<<temp[i]<<"+";
    }
" w$ a( }" F8 o) v2 ~    cout<<endl;
  v8 c: N" L  S5 {9 Z9 e    cout<<"reslut:"<<endl;
) [- {' g# t$ j! q8 ^    for(i=0;i<3;i++)
5 [* w# c" q! ?6 ~' t- t    {
        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
    }
4 O6 a$ }' D* r- c  \$ P3 F- ?    return 0;
! d  e! s- H7 J% x}

---

作者: 葉_浅浅    时间: 2011-2-22 21:04
其实我一直觉得楼主的品味不错！呵呵！
3 q0 I( l. e4 {  Y+ }数学中国社区分享快乐！

---

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

---

作者: ehi28    时间: 2011-12-11 16:23
嗯,不错,支持一下.
) g1 R# f$ [* }0 B7 i, N; m! T% G  q

---

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