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

厚积薄发

座位调整

) n8 C( V( p5 d题目描述：
5 ?% c/ s& O7 n5 r
百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。

: l" [0 j4 r$ y& {调整的方法如下：
5 l; S: v+ L( }; a* L) A+ U
1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。

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

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

9 O( X! p6 O- A3 x/ @数据输入：
& T' z1 V. _" l# r; b3 Z
- o) U! d3 D5 x# c- p第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。

第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。

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

答案输出：

对于每个测试数据，输出可以达到的最大的喜好程度。
: Q* u4 }: N* O" B
输入样例

3 3
3 U% M, ^$ v) m9 F: n$ d9 b
1 1 1
9 v; g2 V3 |# {: X3 E& l
5 P, b& |/ r2 l" U0 s100 50 25

100 50 25

9 Q' o; Z  ]7 P3 i7 K/ P100 50 25
$ @8 o* ]" Q7 O/ W' [

输出样例

+ N+ H' V( D( U  y2 b175
" o4 C: a2 T( P2 ^$ i) H
! S# X$ t. J: h3 {

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

厚积薄发

#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
int sum=0;
6 b0 p* _" |) h' G8 Nint max_num()
) y! O! Q9 E0 G{
    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
# M6 Z$ C  X/ m9 _- _; r$ t    for(int j=0;j<3;j++)
    {
        if(max<b[j])
        {
+ f$ Q+ Y  n# M# r% w" F* @3 a" L            max=b[j];
            x=i;
            y=j;

        }
$ _" K2 J4 p, c6 L8 ?    }
$ Y; z, a8 W$ V! n3 e% c2 r9 t% m   
    if(a[y]>0)
' S$ O- F" c. S, B7 N    {
$ V5 @9 w) [9 u        c[x]=y;
3 p  U7 f( @7 \) J- M        sum+=max;//总喜好度加上添加
* F! t3 D8 F3 C9 h* }        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
% U, I+ ]! {; @        {
/ f! D9 @2 b( ]8 P            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
    }
+ ^' Y, c5 X3 r* Y0 @  x4 y    else
    {
% C3 _- ?$ D- J( K        b[x][y]=0;
    }
   
    return sum;
}
int main()
{
   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
    {
% Q! z5 e- [6 @6 r7 m6 {) R" }4 z5 Y, [        cin>>a;
    }
9 L8 D$ l  O/ U2 i' I, _5 F    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
% [' s- s$ s' m1 Z9 F. i, }7 |8 q    for(int j=0;j<3;j++)
    {
        cin>>b[j];
! Y8 A7 t) R; Z' D. r7 Y    }
/ `+ G+ p# G( A5 B! ]$ c    for(int k=0;k<9;k++)
    {
        max_num();
    }
; U9 `7 C' R* L   
    cout<<"sum="<<sum<<endl;
; R7 J8 Z& i2 `8 K1 x    cout<<endl;
    cout<<"reslut:"<<endl;
4 e4 N) x7 }: A    for(i=0;i<3;i++)
# Y' I2 E! S( f" L2 H! U. V    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
' U+ v1 Q# O- T( F% `8 q    }
    return 0;
: |+ G# c7 B6 w5 j+ u. P}#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()
{
    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
0 B" @; s- g, V6 ?9 |" [3 h    {
% Q4 I4 y! C: l; o7 ~+ {9 e. v        if(max<b[j])
5 ?! E  l% H0 J5 I9 G+ {        {
7 P2 P% M9 {6 a3 k            max=b[j];
1 U) p* S( W" y. `+ W            x=i;
3 Q+ a+ U4 k, v  o* P$ X1 z; q            y=j;
- p: b) t& R" q" j3 a' C5 S7 l
        }
% {4 R3 V) O$ G) C; `    }
) r/ L# c2 q# O3 M% b3 }   
    if(a[y]>0)
$ }4 m& N+ o3 G4 s6 X; L    {
        c[x]=y;
& j6 h3 J! s/ Z  z* N        sum+=max;//总喜好度加上添加
; Q; J2 u: Y9 C, M        a[y]--;//区域上限人数-1
: X1 q3 s9 s. V7 Y3 f5 ^6 U        for(int k=0;k<3;k++)
; ]% B2 l8 K; u2 p        {
! s0 R. Y% Q" m8 ]' T+ j            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
    }
# q# o5 H% A( K$ H0 f    else
    {
        b[x][y]=0;
    }
   
: i$ Z8 f2 l- a* ?& O7 G) ^6 s    return sum;
7 d$ F. s/ L; {% `8 ~6 N}
int main()
{
   
- @/ v- d4 f  }  L( L    cout<<"input 3 zone's limit:"<<endl;
/ ?- ]0 x& T, G; k    for(int i=0;i<3;i++)
. ]7 B1 w: O* a: r( P0 p% M# ]    {
# [6 R. H9 M) @8 T: |/ ~        cin>>a;
6 \+ m. F0 c( {) A    }
    cout<<"input 3*3 actangle:"<<endl;
* b$ r: k+ [# R- ]: Q8 R0 i( N4 A    for(i=0;i<3;i++)
: [# L. ?7 A/ Q3 c- ~    for(int j=0;j<3;j++)
, F$ I2 _* I/ }( q! J    {
' ^$ @9 X/ X2 Y" p  g  }        cin>>b[j];
    }
3 X. S: K" K- u; P/ ?# ]    for(int k=0;k<9;k++)
    {
        max_num();
    }
, ~& f  F7 v5 Y2 g4 x   
7 i! j! F( @( h2 c* J% h' s    cout<<"sum="<<sum<<endl;
    cout<<endl;
0 u4 S0 W+ X! g, E- F. J; w    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
7 T" `* I+ l) O' K; q    return 0;
7 k. Q% X9 m" B* w- X}

厚积薄发

编程代码二：
; h9 V/ ~. E3 F5 v8 W1 m#include<iostream>
' p3 v" U9 {( Y#include<cstring>
#include<ctime>
3 ~2 U* G! ?" G* T& D2 gusing namespace std;
( z& ?- R3 ^: d* `class ifo{//矩阵的元素
/ W8 f3 e: h3 t9 z" [, G) A    int clerk;//员工号
8 T9 ]; s6 M; m4 R1 k- [2 _# Q    int area;//区域号
9 m; Y% X: i( h% s    int per;//爱好度
$ f" Z: f. t4 [% u! M+ Q3 W, P# {, bpublic:
3 Z- j' q  w3 ]& b. m    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
    int getclerk(){return clerk;}
( [! q: q+ }' J  ~+ d5 p& @$ d! r    int getarea(){return area;}
    int getper(){return per;}
    void setclerk(int i){clerk=i;}
    void setper(int p){per=p;}
    void setarea(int a){area=a;}
};
class area;
+ F0 k9 _3 M  ^  Q2 W1 t( i4 \6 k0 E  Dclass clerk{
    int areanum;
    bool isin;
    int inarea;
public:
" U/ C1 ?( D. C* ^    void set(int num){isin=true;inarea=num;};
0 s+ e2 h! n7 q# i& Y" C2 E* ?    void setisin(bool b=true){isin=b;}
    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
};
4 y# K6 Z8 z- u1 P; [& l  d6 k" Yclass area{
- b5 g+ \% a* r+ h7 V! U- O. s    int num;
# K# [2 ^6 d+ e    int max_num;
. O7 m7 v( p# ^8 H+ u+ Wpublic:
' J2 U% v/ l0 q& N  z% s    friend void set(int);
* o; ?  c, G2 l    int getnum(){return num;}
    void setnum(int number){num=number;}
9 M2 W# x4 Z$ K. j/ V    int getmax_num(){return max_num;}
/ ]% J+ o: N5 j" V! y2 v2 G    area(int number=0){num=number;}
    int getclerk(){return num;}
, ~7 k- z0 t6 t9 q- N% f    void addclerk(int ps){num++;set(ps);}
' {: T) S8 v+ E- j};
2 N" I! `; _9 E0 S  m0 Lvoid getorderbyper(ifo array[]);
int areanums;
void main(){
    //input
    cout<<"输入区域数：\n";
$ P+ ^1 q/ |9 Q' l: h/ J* b    int area_num;
    cin>>area_num;
; a3 Z& D- F* S1 }, u+ `- _    areanums=area_num;
, _5 ]- P* v6 \2 K- X6 n    cout<<"输入员工数：\n";
    int c_num;
    cin>>c_num;
9 E" @  g% f  \. K5 F    cout<<"依次输入每个区域能容纳的员工数:\n";
    int *max=new int[area_num];
    int nownum=c_num;
    while(nownum){
- C3 E- j# O9 h, }& ^: H        for(int i=0;i<area_num;i++)
        {cin>>max[i];nownum-=max[i];}
* I9 f2 ^3 \9 C  c0 p+ h/ q6 _7 G        if(nownum>0){
            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
            nownum=c_num;
5 d) C3 z- J" c        }
2 Z  G! F5 \* R+ [+ n; @3 m5 ?* V        else nownum=0;
% @8 ~8 J, J6 F7 x5 \% C# _    }
    cout<<"按行输入每个员工的偏好：\n";
    ifo** per=new ifo*[c_num];
    for(int j=0;j<c_num;j++)
        per[j]=new ifo[area_num];
" }4 F5 e$ g, W    srand(time(0));
4 {. h& t) q5 g9 w( K# e7 u    for(int c=0;c<c_num;c++){
        for(int a=0;a<area_num;a++)/*
7 C8 o3 p  N  [. x: [: ?9 b        {    int p;cin>>p;per[c][a].setper(p);
            per[a][c].setarea(a);
            per[a][c].setclerk(c);
        }
        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
# P9 Y8 y% n$ \. x        {    per[c][a].setper((rand()%60)+40);
' U$ s: H! P% B/ A: c            cout<<per[c][a].getper()<<'\t';
0 I4 n. \. J) a0 ?        }//测试时懒得输入，故以60-100的随机数代替。
-    cout<<endl;
    }
9 ]( ^) Z# B  m9 |# `    //output
        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
  T2 h; ~1 ?/ `: m" \+ k        clerk* people=new clerk[c_num];
+ G  T* q$ w6 B        area*  areas=new area[area_num];
5 {* O* A5 i4 K! y5 P        int totalper=0;
        for(i=0;i<c_num;i++){
( _& d0 l- A) Q$ k% {3 [' t- v            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());
- b1 l( X5 D- ~, U! U                people[i].setisin();
% T( ^5 f# [( S- y                int number=areas[per[i][j].getarea()].getnum();
                areas[per[i][j].getarea()].setnum(number);
                totalper+=per[i][j].getper();
                break;
            }
        }
/ Q8 v9 ^5 ]4 [( d' ?        cout<<"能达到的最大喜好度为："<<totalper<<endl;
' l/ a' M  G8 D, B% B0 I) C}
# `; y1 d5 S" C$ [& Cvoid getorderbyper(ifo array[]){
2 a$ n' ?0 l3 F& M+ D    int max=0;
& k7 o' [' [8 _' j$ U# u% X    for(int i=1;i<areanums;i++){
        for(int j=0;j<areanums-i;j++){
        if(array[i].getper()>array[max].getper()){
            max=i;}
2 D9 \' z# r' R" ~* G        }
        ifo temp=array[max];
        array[max]=array[areanums-i];
3 u7 F0 X4 x% D" x3 u        array[areanums-i]=temp;
5 P( x/ m5 }9 f: r5 |        max=0;
* C9 a  m0 w. r: F% m    }
}

厚积薄发

代码3：
; O) ^' {* S0 s8 V/*
: i: H6 S/ G: q# p% t算法思路：
（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
再加，该人的所有喜好度设为0，
（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
1 J9 Y3 Z- s2 M& x2 _$ b% _（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
9 ]& M1 M" e- Y$ f(4)最后输出总喜好度。
$ v+ O% o( k9 ]- x* c! F7 b9 |8 d( `*/
#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
4 U+ N3 r; c' g+ B( Qint a[3]; //区域人数上限数组
5 F- ]- R4 ?7 h+ oint c[3];
int temp[3];
int sum=0;
  z$ T9 W! l8 Nint max_num()
3 m* Z& F% o( ], s1 `& f{
    int max=-32767;
5 h5 \- C( Y2 d! T    int x,y;
    for(int i=0;i<3;i++)
6 h" D. W  w, C8 u1 R6 z    for(int j=0;j<3;j++)
; D0 L) p8 W7 h    {
* t) D3 s5 u4 N        if(max<b[i][j]&&b[i][j]>0)
        {
            max=b[i][j];
& q4 w- u0 ?8 G; ?            x=i;
: ~% q  J; H5 s5 E2 D            y=j;

$ W9 \6 u. z% g2 a2 {% v4 z' u        }
    }
   
/ y8 y5 V; D' E' l. L3 }. i0 s. ?    if(a[y]>0)
- |3 E; [7 `! j) k; x( L! N    {
* c# T. O% x1 D& _! ~9 r        c[x]=y;
        //cout<<"c["<<x<<"]="<<c[x]<<endl;
        sum+=max;//总喜好度加上添加
7 G+ P8 |, a) S( {% W& c  n        temp[x]=max;
        a[y]--;//区域上限人数-1
    }
    for(int k=0;k<3;k++)
: ^, `( K: _3 a0 D1 n) L    {
2 C( e* F/ ]. h2 K7 n% d) J+ V3 c        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
    }
3 b% `! Q# U- b" j& Z    return sum;
* c5 s* r4 [; u# |! p0 |  I1 I}
% j2 Y/ @  G8 K6 T9 l; o% Xint main()
{
   
9 V) }8 h$ x) l3 F, O  g    cout<<"input 3 zone's limit:"<<endl;
) H2 H( X$ ~9 H. Y) k  K9 Y1 a    for(int i=0;i<3;i++)
; D; h9 ~8 v4 e5 B' Y, Q    {
        cin>>a[i];
4 t6 B" p5 t4 T3 F5 b    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        cin>>b[i][j];
    }
    for(int k=0;k<3;k++)
- W8 t2 p) t* [! A& C) t4 z    {
0 W2 |3 U5 q3 h( |. V: \1 V        max_num();
    }
) }# h2 g0 j, A6 q2 ~; F    //cout<<"sum="<<sum<<endl;
    cout<<"sum=";
    for(i=0;i<3;i++)
) c) E& i. o5 c5 G    {
        cout<<temp[i]<<"+";
# Z: n% Z$ a6 Z% E2 u. z+ U3 I    }
    cout<<endl;
6 x! L( B( S+ K    cout<<"reslut:"<<endl;
! h. t+ X' d3 ]4 ?    for(i=0;i<3;i++)
    {
        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
/ M. N# E" I1 I6 S5 H) C    }
# q+ L" v$ S$ B* R2 F% E/ `    return 0;
}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
1 b6 }6 q" H4 @8 z- `数学中国社区分享快乐！

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！