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

厚积薄发

座位调整
& M: u5 e1 ~# D* I2 i+ m3 y
) B3 \- q9 K: d题目描述：
" W% O' ?. d  s# r: p' z8 i; J- O
' Y8 \. E. M, M+ z百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。
3 c* d0 o- _2 o! r( I: F
调整的方法如下：
: j  ~- V6 c9 p- I$ R( _; H5 v" y3 t, r
4 Q1 ]& F# }: Z5 j+ g1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。
0 y& W" e" M9 z" Y+ J6 R* w9 u
2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。

* {/ e% w/ U! D1 x# r5 t, W' P3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。

8 T0 [% z8 V5 c/ T8 x0 p数据输入：
5 A8 ^) l- U% u0 d3 ^3 t
第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。

9 X" L3 T, V% D, t! g. f( H第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。

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

* E( e7 D: `0 c/ u  a答案输出：
/ v9 u0 M9 Z6 |: c+ m
# b9 @& w/ F' O2 j/ y8 _对于每个测试数据，输出可以达到的最大的喜好程度。

输入样例

' A  a: E6 z/ x) L3 3
8 N0 B1 S$ G0 H/ x2 s
+ g6 o! T& A5 z1 1 1

100 50 25

100 50 25

* N5 g5 t1 E8 m7 s& f% N( U100 50 25
* f1 F0 r7 Q6 W0 Y) w

! L- I& p1 C5 \. i* @0 P输出样例

+ L3 ~4 Z6 m* g4 ~- i175

; t: V* k+ @9 h! N

$ j; k6 s0 Y; }0 u$ G
数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175

厚积薄发

3 ^& s* d- h3 w7 s
9 R2 |& u0 f* Z& r2 X/ F( M) Z#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
/ P  E7 p# Y- T: Tint a[3]; //区域人数上限数组
$ h; N; k: [' W+ ~3 mint c[3];//记录某人i去的区域j
int sum=0;
int max_num()
{
    int max=-32767;
    int x,y;
. ~& ~0 \0 i& e- o& C7 K/ m    for(int i=0;i<3;i++)
+ G7 f3 y+ s6 M9 ~4 A; m8 R# w& S    for(int j=0;j<3;j++)
. J; ]5 z* z2 {( |6 G0 }% H1 L    {
        if(max<b[j])
        {
            max=b[j];
8 ?* w% M( C; w/ w9 r            x=i;
            y=j;
9 l+ N  o/ k. ^, u$ I4 M+ ~  Y
* Y; m  n& u) l0 a$ O! y# X        }
    }
8 Z+ ?% d( u- Q   
    if(a[y]>0)
    {
        c[x]=y;
        sum+=max;//总喜好度加上添加
# j7 D6 v4 d# E" [/ f) w; |. q) Q        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
        {
3 ^$ K; o6 I) J9 j% r& L# w9 D7 t! \            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
8 [3 c/ C% R& A0 t$ u    }
1 G! ]4 D/ E2 G/ M6 l    else
    {
1 G/ J; S, f8 U3 Q        b[x][y]=0;
& I; u4 ?4 h9 C/ ^    }
8 E8 v' u$ E8 ^3 ?" {   
    return sum;
; m6 o9 [" Z2 }6 @7 @+ f1 ~6 f}
, p# Q  E% V: h; t  X- L# Bint main()
{
) ^0 b6 H5 R$ @6 R7 s   
9 \0 Z- {; U+ z3 p6 ^( S" a    cout<<"input 3 zone's limit:"<<endl;
1 e- O8 z+ L3 ], y    for(int i=0;i<3;i++)
: |1 {8 [* S, w9 s    {
        cin>>a;
) ?; o2 v- e& T: `    }
6 d" p; A* w$ E) q    cout<<"input 3*3 actangle:"<<endl;
/ @2 A/ Q1 |" w$ C+ I& T    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
4 S5 h0 c; X' H4 I2 b" N        cin>>b[j];
) L& m7 o9 A. O" G- ?: R, U    }
    for(int k=0;k<9;k++)
/ L" h$ }+ E0 t# h& h+ X# i    {
        max_num();
    }
% b4 m! ~* C) l   
    cout<<"sum="<<sum<<endl;
    cout<<endl;
: }: q- n; {8 ~# c& ?    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
1 R; C6 A/ ]& `' k. W    }
* H+ p9 a" s1 \* L7 D9 g. z5 b5 s    return 0;
}#include<iostream>
4 Q! ?$ b- m  T; k4 {using namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
% ?# O" A$ @, U! B- z: vint sum=0;
! Z! A. w5 V0 [: R$ x+ Cint max_num()
{
. o6 I8 F" m$ |9 y    int max=-32767;
/ K8 S1 g# q" ]: i  i( T2 u9 w1 W4 S    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
. V" {0 I1 l$ v/ E: ~. `$ H    {
% D; j6 \3 J( h% u9 k/ g        if(max<b[j])
        {
            max=b[j];
  s+ ?; e# E: {* i+ @            x=i;
            y=j;

+ k1 F' ?* w1 @$ _0 A0 c8 f        }
3 |, }1 z2 ]" H' I/ \) t3 J% I    }
, t/ V. e2 x2 `  L   
    if(a[y]>0)
    {
, U) q# I" W2 D6 q% y        c[x]=y;
7 ~$ \' E6 i0 ~! w- p) i/ Z$ Q) n        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
1 G$ R; u) @9 A( u        for(int k=0;k<3;k++)
. F9 K6 L# c2 G  H/ f( h/ V        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
    }
9 Q& l  k5 e& \    else
: \% V# }9 X) T% [9 M5 }    {
        b[x][y]=0;
    }
   
! Y0 E/ f  _4 x' \# w3 ]3 |    return sum;
}
! {. T# N5 A5 M- \5 x( C9 ?2 Xint main()
" x8 J3 q% A' q* f{
   
. G" g+ ~; J& q% ~    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
7 M7 s. \+ k" l    {
: Z& X) s1 Z' u  o8 X        cin>>a;
( m- q1 G$ Y% J    }
/ ?- U% G# B% s- S! }    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
3 p( |  y+ w% l6 m1 o/ m        cin>>b[j];
1 `, B7 D, n* N  M2 L6 n( b4 @    }
    for(int k=0;k<9;k++)
    {
0 ]6 ~. m& y5 N. E2 J# o: G' l        max_num();
! A' u2 L$ S6 Q' M8 T8 F    }
3 T1 j9 ^) @' J. h+ Z) i) R1 z   
    cout<<"sum="<<sum<<endl;
+ Y1 m. ^, ~0 N2 [% `7 t6 w  L4 x' f0 h    cout<<endl;
( r  b, `6 l& L% `  S    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
. x' i3 w" X: p5 {6 s' x0 d+ o    }
    return 0;
}

厚积薄发

编程代码二：
#include<iostream>
#include<cstring>
#include<ctime>
, X" O9 v! v' ^$ }$ D% i, S# C" E, j& Nusing namespace std;
' ^8 t2 \7 \6 N8 H: kclass ifo{//矩阵的元素
0 |7 N7 K9 v# ?, l: Z5 s& y    int clerk;//员工号
    int area;//区域号
    int per;//爱好度
% b/ o: y) ^/ b! J+ G: \% Upublic:
' p1 g% C& I) i" }    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
9 G) Z0 M4 J) N# C% F. Z    int getclerk(){return clerk;}
    int getarea(){return area;}
    int getper(){return per;}
& Y+ Y4 u3 e# Y/ `    void setclerk(int i){clerk=i;}
    void setper(int p){per=p;}
2 L* i1 v0 ^. h, f. r# M: N    void setarea(int a){area=a;}
% x6 x9 \+ X6 R0 @};
% C9 r3 V. @. A. Uclass area;
class clerk{
    int areanum;
    bool isin;
1 x  d& P, \* z) v9 Y( {, s    int inarea;
. K# S# _  S2 B" G! F  mpublic:
    void set(int num){isin=true;inarea=num;};
    void setisin(bool b=true){isin=b;}
) I+ x; H& j$ h2 D+ x7 ^    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
8 o2 n8 u) G: \};
9 r$ }/ Z6 x( D1 P6 aclass area{
    int num;
    int max_num;
, T6 D5 c; ]' |; E- r$ E( ~public:
    friend void set(int);
( P0 V! Z# U: a$ B# V  X& K8 w    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;}
* ]* D5 U) g. W) q5 n5 G  U    void addclerk(int ps){num++;set(ps);}
, S6 @% `# r8 ~5 U+ [' @};
) O7 a6 r1 d3 o% uvoid getorderbyper(ifo array[]);
4 a7 ^: K( ~, G- P( s) G& qint areanums;
% `; N! W& m& C, g  p5 yvoid main(){
    //input
    cout<<"输入区域数：\n";
    int area_num;
) j: o2 I3 @4 c; F9 W& x    cin>>area_num;
    areanums=area_num;
    cout<<"输入员工数：\n";
% R! E0 M3 ?5 {    int c_num;
    cin>>c_num;
    cout<<"依次输入每个区域能容纳的员工数:\n";
    int *max=new int[area_num];
* j7 x" z& }8 _* W    int nownum=c_num;
    while(nownum){
        for(int i=0;i<area_num;i++)
        {cin>>max[i];nownum-=max[i];}
. t+ m5 p+ v# |: L        if(nownum>0){
6 ~! ?! E8 Y: F6 @            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
            nownum=c_num;
        }
' B. }! S' d. V4 _6 k: ]8 s& F        else nownum=0;
6 n) h7 w$ d: {, k    }
' i/ Q1 \( Z) F' }. z    cout<<"按行输入每个员工的偏好：\n";
* @3 b4 F1 E, P& o    ifo** per=new ifo*[c_num];
. {" X/ ^0 ~* K. l9 v" j    for(int j=0;j<c_num;j++)
        per[j]=new ifo[area_num];
    srand(time(0));
2 ~# c6 y( H; w$ d5 X* o! U    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);
$ j9 r6 k: _+ j8 e% b            per[a][c].setarea(a);
! ]: N8 s) h" P. W, M            per[a][c].setclerk(c);
        }
/ Z# Z# y$ ~8 u; q        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
        {    per[c][a].setper((rand()%60)+40);
. q  M3 I3 ~5 |$ ^+ m            cout<<per[c][a].getper()<<'\t';
1 @1 v% |+ C8 u+ u/ m        }//测试时懒得输入，故以60-100的随机数代替。
-    cout<<endl;
    }
- O  |" @2 p3 O8 U  S7 q    //output
0 g6 A0 w7 N% k% @! @4 ]7 Y! e        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
        clerk* people=new clerk[c_num];
, E5 M. V) X, ^/ Q3 c  Z: y  D- O        area*  areas=new area[area_num];
3 q# m# D/ ]3 |; s; ~, G        int totalper=0;
0 C; u2 `" S; V$ S8 g" d. r        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())
( W# @% D/ A3 L                people[i].set(per[i][j].getarea());
4 F# r; ^9 R# t5 @/ J6 P  Q                people[i].setisin();
" m- M; o/ [5 V9 c                int number=areas[per[i][j].getarea()].getnum();
                areas[per[i][j].getarea()].setnum(number);
  K0 p4 Z$ ]: s- B" Y5 d  K2 K                totalper+=per[i][j].getper();
                break;
& w4 J3 C  i* P0 K; T4 _1 O            }
  E" q9 o( f8 b* @  B. e1 }        }
        cout<<"能达到的最大喜好度为："<<totalper<<endl;
}
void getorderbyper(ifo array[]){
    int max=0;
    for(int i=1;i<areanums;i++){
: t/ z: g- W! P6 Y2 d  b/ U6 e        for(int j=0;j<areanums-i;j++){
        if(array[i].getper()>array[max].getper()){
4 x- Z& e) e6 f4 o( C; T7 U2 b            max=i;}
& P7 C: f  n! L: ~        }
        ifo temp=array[max];
        array[max]=array[areanums-i];
7 _9 _# g  X) n. [* _        array[areanums-i]=temp;
) P! ?* B& \5 T, {; q6 ?) y        max=0;
( q( B7 P* c3 Z( F& j$ C" Z8 c    }
3 V* R0 i  v; L8 ?}

厚积薄发

代码3：
/*
0 F( a7 C2 W, B算法思路：
（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
再加，该人的所有喜好度设为0，
* y7 s- r2 L" J3 ~! s（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
(4)最后输出总喜好度。
# o/ ]% z/ c  |4 S*/
#include<iostream>
using namespace std;
1 x* x' l  X% J, w% Z, mint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];
int temp[3];
$ s. G# ~7 W. _+ Bint sum=0;
int max_num()
( K7 F2 F5 d( c8 K! w# y{
* |, [! V9 _7 t4 U: O, F    int max=-32767;
$ R% }6 e* N- j- j, Z    int x,y;
    for(int i=0;i<3;i++)
- G/ G4 C% ?$ n0 ?& j) @* J    for(int j=0;j<3;j++)
1 T: h& s( m- d3 P2 I8 X    {
5 b; s$ z) P9 _        if(max<b[i][j]&&b[i][j]>0)
        {
' S) \; H& H/ W5 ]; H            max=b[i][j];
0 v& K! h3 Y, d$ G. e            x=i;
            y=j;

        }
    }
6 P; r" b4 g3 z   
1 U9 p- u$ \3 l6 z1 p+ ?    if(a[y]>0)
    {
; i0 V/ d! R+ f% F        c[x]=y;
        //cout<<"c["<<x<<"]="<<c[x]<<endl;
        sum+=max;//总喜好度加上添加
        temp[x]=max;
$ V$ p6 d" w$ ?# K, ~        a[y]--;//区域上限人数-1
    }
    for(int k=0;k<3;k++)
    {
- U6 }! P9 N# v2 ^) r$ Z        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
    }
! f' T" }+ L7 ?; H1 A7 ~2 C    return sum;
}
int main()
( }# Y% X* d/ C1 e1 f* f{
   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
    {
& j3 _5 U; d* {  }! S2 C' c        cin>>a[i];
    }
$ t& `. z( Q1 G" d' W/ [    cout<<"input 3*3 actangle:"<<endl;
, j9 p) N4 u' O  r, _3 u* q9 r    for(i=0;i<3;i++)
* Z$ n8 d6 p5 h8 \    for(int j=0;j<3;j++)
) I& ~# V; j* \  ^4 `    {
        cin>>b[i][j];
    }
8 L7 p9 z/ g8 R( X9 k( U7 i0 f    for(int k=0;k<3;k++)
    {
- Q3 W6 y) D, @% B" |1 z" Z) s        max_num();
    }
5 r1 e8 D/ W6 j. K    //cout<<"sum="<<sum<<endl;
    cout<<"sum=";
    for(i=0;i<3;i++)
    {
1 j7 y2 W4 r; g6 J6 _! `7 E        cout<<temp[i]<<"+";
    }
* v3 q2 `+ D5 v6 m9 z: j9 ?) z    cout<<endl;
    cout<<"reslut:"<<endl;
' ]/ J* T2 {( g    for(i=0;i<3;i++)
1 M3 V8 B3 n/ C! D! A    {
0 S+ [2 z9 D5 Z$ x" M        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
  M6 D& b, X+ Q: d* O4 X" B2 `# Q    }
% R  g/ _& h9 C+ i* Q: E2 [. c    return 0;
}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
数学中国社区分享快乐！

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.
7 P$ H' H8 I( p" z2 `

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！