数学建模社区-数学中国

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

---

作者: 厚积薄发    时间: 2010-5-6 18:47
标题: 2006 年百度之星程序设计大赛初赛题目 5
座位调整
, j2 Z) M& X3 A! r2 t) a; a9 w1 O5 u
题目描述：
/ X7 ~; I" A0 p. B0 @" o3 C" ?2 R
百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。

. p7 ~; Y6 y  T# E调整的方法如下：
$ i/ K( w4 C! u1 {
* Y( X9 ?" |% V9 R- B1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。

, a8 v. V4 p1 W% ~1 P2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。

# d* w% ]' N2 `* H' V! C+ O3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。
9 l$ c$ S/ S+ T7 z# W% M: l( D
数据输入：
$ n% S; _1 b' z
6 |* A% @8 Q) z6 b第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。
" d) L; L% G0 b/ U$ X5 h
第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。
. Q! ?7 i3 _8 J
紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。
  o: |: J1 V6 B
答案输出：
! h# O# X% x" E& E6 ^
对于每个测试数据，输出可以达到的最大的喜好程度。

9 C' {% |8 \0 W$ R  C' F6 y' g& a输入样例

' t. h) N2 _; e* R* e: J3 3

1 1 1
& o9 E' h1 i; R+ v7 J/ j
1 B% H2 L& P% J5 Q! J100 50 25

7 V( j" d; o0 P5 r100 50 25

100 50 25

, F* m; M0 U& K  u$ d
2 ?: L# M0 m/ O9 j2 p输出样例

175
. l1 |& q+ \, x! Z0 j
( t, n2 |5 D1 m

: I: R5 d  o( ]4 S) j# F- `数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175

---

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

. J$ V! f8 i4 f3 \, V; d$ i
#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
" e  b& H+ t' c8 m0 b2 ]! Yint c[3];//记录某人i去的区域j
int sum=0;
1 ~( c. i1 h2 u9 H- }int max_num()
3 r1 U" z# z7 {* A{
    int max=-32767;
4 ]" x' x% W0 r+ j% P    int x,y;
    for(int i=0;i<3;i++)
' y& q# p3 Z, v. n! q% S. N' n0 [    for(int j=0;j<3;j++)
    {
* t6 }8 B1 F  c2 Y! H        if(max<b[j])
. f$ N3 d) C; q5 J, O        {
            max=b[j];
            x=i;
7 J- E; f5 S2 P2 w            y=j;
& f+ W' P  S! a
        }
    }
   
! ]6 n& {3 Y* K, e    if(a[y]>0)
    {
        c[x]=y;
        sum+=max;//总喜好度加上添加
# R: A3 r7 e1 X$ g: P        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
1 g( t. L, w# ^8 n$ ?" I4 y        {
: Q6 }  B7 J: d3 c% ]            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
1 H1 a/ V  E7 R! E) t* {% i7 ]8 ]    }
7 s2 u. I0 y# q* F    else
    {
- v/ L; |9 k& M        b[x][y]=0;
    }
2 H% \# ?* `5 S, B( b, j1 C   
6 p: @% d% E# L3 Z" ]    return sum;
}
int main()
9 ^2 |  I& W: h# i$ ^! f{
6 H% V7 `' z/ o' \" [   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
5 N3 b2 G" W' _+ ^: O) i+ V+ q: ^    {
        cin>>a;
    }
    cout<<"input 3*3 actangle:"<<endl;
# q+ S- e( H2 w  [; ^5 s1 T    for(i=0;i<3;i++)
1 j  b: g6 c9 p- q3 a    for(int j=0;j<3;j++)
    {
        cin>>b[j];
    }
    for(int k=0;k<9;k++)
    {
        max_num();
. }4 Y" S: I4 r; `% E    }
/ {4 l. T4 v7 ]! ~; ]   
    cout<<"sum="<<sum<<endl;
& t% O1 S8 Z7 w' o  u4 c$ }; o    cout<<endl;
+ S. ]+ y( z0 j    cout<<"reslut:"<<endl;
9 {" b6 U4 r4 l4 f    for(i=0;i<3;i++)
: A; N0 o* x" }9 f& U    {
+ g) H# }( f) b        cout<<"people "<<i<<" go to zone "<<c<<endl;
% `" `" _+ a+ x    }
. F* R- c  w$ \    return 0;
}#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
int sum=0;
int max_num()
  R0 x( a8 t4 [% }- }4 A{
6 ?8 y; R$ A" q+ O  i    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
2 v7 p% ^9 M5 e3 W/ [: i; V8 e    for(int j=0;j<3;j++)
0 g# n  h" u1 u5 b4 H    {
        if(max<b[j])
        {
4 V. F( X+ J9 L5 X7 p            max=b[j];
) y# R* D8 I5 ^' ^, X9 I$ C5 K            x=i;
! V+ g! ^" n8 P            y=j;

        }
- q" k( v. p0 a: I    }
  q2 t: K$ t* s  f7 i( Y# s   
9 I6 `9 ]3 B; j& j4 [2 z) i    if(a[y]>0)
  B3 n! q1 J( @# q6 K    {
        c[x]=y;
# S! X2 B; s  ?* [8 V        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
/ S6 m! T) t) O/ B4 O. L7 ?9 V        for(int k=0;k<3;k++)
        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
1 m7 \, D" W: a9 m" i; |5 e    }
    else
    {
6 F  S0 |. y8 H5 T9 a! v2 a        b[x][y]=0;
    }
" s/ L% @$ ?9 w( i! H8 s   
. g1 |* e, O1 ?  B) N    return sum;
}
int main()
# g: y. E, k) k* X; t6 f% c{
   
    cout<<"input 3 zone's limit:"<<endl;
' p7 r6 f( @9 T3 F& }4 o    for(int i=0;i<3;i++)
9 B) P$ f* D: B( Z4 u    {
        cin>>a;
    }
    cout<<"input 3*3 actangle:"<<endl;
( M) g* O) j1 }4 s; s4 J, W, U    for(i=0;i<3;i++)
" a. O. _+ @: \& U    for(int j=0;j<3;j++)
% m4 \& r. c6 s: P, _    {
/ {9 X3 K) N# \8 d! H/ j' ?9 R9 w3 `        cin>>b[j];
    }
    for(int k=0;k<9;k++)
    {
        max_num();
    }
   
    cout<<"sum="<<sum<<endl;
    cout<<endl;
    cout<<"reslut:"<<endl;
( S1 O, g/ t0 V  p/ U- u. d    for(i=0;i<3;i++)
0 P2 q" T( u7 _  Q  p6 t    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
! b0 [, E( U5 G8 w( P! m, s    }
    return 0;
1 S% ]! \% [7 J) U, `) i+ _}

---

作者: 厚积薄发    时间: 2010-5-6 18:48
编程代码二：
#include<iostream>
#include<cstring>
1 r" _; c! e( R#include<ctime>
using namespace std;
class ifo{//矩阵的元素
- G2 Y; x1 F+ S9 Z9 U4 H$ i2 b0 |+ W    int clerk;//员工号
    int area;//区域号
    int per;//爱好度
public:
    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
    int getclerk(){return clerk;}
    int getarea(){return area;}
    int getper(){return per;}
1 \- N( \; G5 v5 d    void setclerk(int i){clerk=i;}
9 L7 ]& c2 P9 E" ]9 K7 d    void setper(int p){per=p;}
0 S: c8 J* u/ G5 [    void setarea(int a){area=a;}
+ V3 O% l6 C- h};
7 n( f0 U# B  m; q& S; X2 xclass area;
class clerk{
    int areanum;
( b# i8 o0 ?$ T' m5 M# a$ f$ j    bool isin;
8 B; F) w  o+ q    int inarea;
public:
    void set(int num){isin=true;inarea=num;};
: Q: J6 M: w; G* b  u    void setisin(bool b=true){isin=b;}
0 \$ d# i+ d1 K; n1 |; m7 W2 @    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
};
class area{
    int num;
# V+ z5 u) I  J5 c    int max_num;
1 K* ~5 H2 O3 q$ p! i" P+ {) q) Vpublic:
    friend void set(int);
4 ~  ]: A+ ], H' B4 t& v    int getnum(){return num;}
* E/ s( R, L8 e& k8 D    void setnum(int number){num=number;}
% y7 T1 }% K6 [0 ]" N' V- h    int getmax_num(){return max_num;}
- K9 x- |/ T; ?6 U0 y    area(int number=0){num=number;}
3 `: T# h  \3 ~  T+ q5 y    int getclerk(){return num;}
    void addclerk(int ps){num++;set(ps);}
  o) V/ |# j/ p7 O6 ~& q# _};
9 p) W+ N  w0 Z  Qvoid getorderbyper(ifo array[]);
int areanums;
) W8 h& ?* p" j7 \void main(){
    //input
% ~" v+ q7 X9 v$ g    cout<<"输入区域数：\n";
    int area_num;
    cin>>area_num;
    areanums=area_num;
    cout<<"输入员工数：\n";
7 q' a& ?" L: p3 E5 r8 G    int c_num;
    cin>>c_num;
1 I5 |0 L* p+ H2 L5 c: D+ `0 a    cout<<"依次输入每个区域能容纳的员工数:\n";
    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];}
7 c( [9 h3 h7 j% d2 ~        if(nownum>0){
2 x% H1 r7 M! A            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
) w/ z( {' C# K. j$ r) g6 J' ~2 Q            nownum=c_num;
        }
        else nownum=0;
    }
. W4 A) Z4 T7 ?7 d2 `    cout<<"按行输入每个员工的偏好：\n";
    ifo** per=new ifo*[c_num];
+ Z, J$ Y( S8 o% V$ y' f$ D6 v+ C    for(int j=0;j<c_num;j++)
        per[j]=new ifo[area_num];
1 I+ q( P/ V- ~" E6 ~7 n    srand(time(0));
    for(int c=0;c<c_num;c++){
. r0 n- F- `( w+ g/ ~% Y# d* F        for(int a=0;a<area_num;a++)/*
        {    int p;cin>>p;per[c][a].setper(p);
            per[a][c].setarea(a);
/ K/ Q* c! p0 C            per[a][c].setclerk(c);
5 D# ~5 F: C- D9 V        }
        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
# U: e( V/ V3 r; l. {        {    per[c][a].setper((rand()%60)+40);
/ ~9 {1 S/ T4 j" p- x            cout<<per[c][a].getper()<<'\t';
, t( B5 g, m9 p! j* e& G/ q( d4 E        }//测试时懒得输入，故以60-100的随机数代替。
-    cout<<endl;
    }
    //output
) I- @4 C8 D( w+ D: T) e* @        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
  h! L4 }! Z+ O& h. X* h        clerk* people=new clerk[c_num];
        area*  areas=new area[area_num];
        int totalper=0;
. e% q0 G$ o# w9 W4 B1 Y$ t        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())
& L5 v2 e- R* V, @8 w5 k0 V2 a                people[i].set(per[i][j].getarea());
# j+ `& Q, W6 L0 F$ _                people[i].setisin();
8 q# u' M  ?3 P9 f! `8 V" |, f                int number=areas[per[i][j].getarea()].getnum();
                areas[per[i][j].getarea()].setnum(number);
0 g6 [# g6 M$ W) G2 i& M                totalper+=per[i][j].getper();
                break;
            }
" Q; D9 l4 j- i; \) w& l0 m9 ?        }
        cout<<"能达到的最大喜好度为："<<totalper<<endl;
}
void getorderbyper(ifo array[]){
$ [: {: [7 ~/ ?+ D# j0 [* x    int max=0;
    for(int i=1;i<areanums;i++){
/ \' h- ~3 Z; b) L: J        for(int j=0;j<areanums-i;j++){
5 i& J: n+ R. v4 T* W        if(array[i].getper()>array[max].getper()){
            max=i;}
2 t. U3 Z9 @) ~5 X7 X, w        }
        ifo temp=array[max];
        array[max]=array[areanums-i];
        array[areanums-i]=temp;
+ L* X+ P1 w: {0 K9 n, {        max=0;
/ k+ w7 g7 R7 O/ G' L    }
5 Y, n9 l7 j  a1 B3 _}

---

作者: 厚积薄发    时间: 2010-5-6 18:49
代码3：
( p" ]9 i, L3 w( I/*
算法思路：
  z' [8 I5 m" s9 d0 S! R# c: S（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
9 s% h4 E9 `% s6 p0 z6 G. i再加，该人的所有喜好度设为0，
! a0 k5 J: O# w) \/ J5 }（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
(4)最后输出总喜好度。
*/
#include<iostream>
using namespace std;
( p( ~% H/ u3 [9 R0 Bint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];
5 B- U5 [: N& V. e" Rint temp[3];
int sum=0;
3 I7 S# P. S0 c/ [int max_num()
{
    int max=-32767;
5 L0 Z7 J( Z! U    int x,y;
9 P5 q& R: m$ |" O  k/ f% O    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
% u# D; k+ N3 o0 U( }( Y* \    {
        if(max<b[i][j]&&b[i][j]>0)
        {
0 I$ N9 C8 B* V" e1 }) }            max=b[i][j];
- W; G6 x: t; w: d( t2 H            x=i;
! I) M0 d' e% A1 [; B  P8 T# u1 ?            y=j;
. [5 X2 s4 S6 J" u
        }
% t+ J9 t  Z1 m& A* e* J- @    }
   
    if(a[y]>0)
" `) I4 |1 ~# j( R' p    {
% j7 Z6 P) S- l# r7 ^& a        c[x]=y;
        //cout<<"c["<<x<<"]="<<c[x]<<endl;
# }: _1 l$ U' i! ~% u; R+ C: _) R        sum+=max;//总喜好度加上添加
- Y# \8 I3 l3 @& C/ a        temp[x]=max;
8 T/ `& `7 a! {- }' |0 L$ B        a[y]--;//区域上限人数-1
3 J6 d2 f' A" v. y    }
, X+ w: x2 |6 }; \    for(int k=0;k<3;k++)
    {
        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
    }
# K, q' V/ x4 ^3 V    return sum;
4 v0 }' c0 M" |" w}
3 g9 o1 I9 }1 {4 q4 ~# ]& zint main()
9 F+ X" b7 W4 _# J5 j{
   
  ]2 L& T: V+ h% {    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
    {
        cin>>a[i];
' ~1 Y& V. \+ k0 y9 G3 M1 J5 s  ]& B    }
" Y- t" q. F4 B3 ^& c! c, e4 x    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
9 c+ ~6 S8 L* Z$ `* K    for(int j=0;j<3;j++)
( e" I) ]9 O$ |: S5 y    {
        cin>>b[i][j];
    }
$ Q0 G9 v  |/ F* o& [, w2 W3 s    for(int k=0;k<3;k++)
    {
        max_num();
/ h, p, I' y0 H( I, z0 l  R0 ]    }
; x4 {5 X" k8 n    //cout<<"sum="<<sum<<endl;
" P, ?9 O0 F+ d$ U    cout<<"sum=";
    for(i=0;i<3;i++)
    {
        cout<<temp[i]<<"+";
7 R# q6 {7 V# S; e' T' M8 p+ r8 y9 r    }
4 r1 M3 B- T  g    cout<<endl;
# K2 j& H  \+ R( y" O    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
  ]$ G# j! w7 J2 D    {
        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
    }
* x3 Q2 ?/ ^; \    return 0;
6 `6 X# d% J# k/ m; i# w}

---

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

---

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

---

作者: ehi28    时间: 2011-12-11 16:23
嗯,不错,支持一下.
' n, h, w6 o* v/ P$ \) i& H

---

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