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

厚积薄发

座位调整

. w9 F' ]5 Q% K6 ~7 C题目描述：

# z6 h8 k1 a' @2 G# H# i' }/ V( W百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。

/ _( |" `6 M5 Z, Y; G! Y% j调整的方法如下：

2 V( c; F2 E, U, B1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。
. r( O/ d6 a. _
2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。

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

数据输入：

3 v0 d" n) o: J6 Z# Z第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。

第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。
4 h4 P0 u9 X  N# K
7 y4 o! ~2 b  k" Z% O紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。

$ o- ~5 \) m* `+ Y, U答案输出：

, u5 b* x1 f* e, v0 `- @对于每个测试数据，输出可以达到的最大的喜好程度。
* U' W5 z/ i- U* P* r$ u% P
输入样例

0 S. ^& `9 M$ u& g
3 3

1 1 1

100 50 25

100 50 25

100 50 25
; I- \1 o; [9 ]5 Q

! {+ _! u# c1 l& [/ r/ k  e! g
/ @: H' ?, y. O+ b2 F; P; B# c输出样例

/ A; Z/ C. b# [9 q5 G+ s
175

$ H: J) q3 b' ?1 Q  F% u9 Q

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

厚积薄发

+ c  ^" |3 ~* w4 w0 B#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
0 X* T1 o: D% hint a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
int sum=0;
int max_num()
{
    int max=-32767;
# m9 I5 Y& N0 i3 T- ]0 i    int x,y;
9 ]# p$ _9 ~2 N7 E. e    for(int i=0;i<3;i++)
8 ~# O$ O! N* j. r5 N    for(int j=0;j<3;j++)
    {
7 W* B* W7 O+ m2 Z' m        if(max<b[j])
$ Q  i. {! A. X$ a' L9 j        {
$ V2 k. O/ x1 P- ^            max=b[j];
            x=i;
* J! o3 z0 o% p5 Y            y=j;
! b" M) J# I# t/ w% L6 w1 K
6 X! g) y" i( Q$ u% G; _* Q        }
# P( ^, O; D2 J& [- N    }
2 g( n' {! m" x% I/ z* `   
. q# G3 L) Q0 L' T# `. k4 I0 N" o    if(a[y]>0)
$ O: c. y( J" k    {
' e6 t$ _% v; N' J        c[x]=y;
$ u: k6 B# H& f        sum+=max;//总喜好度加上添加
- {. i5 [' E3 ^8 F7 u9 k$ R        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
: ]( _, Y& [4 c& M; D        {
: {$ t6 L6 @; Z# ]. F            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
# {7 Y7 M5 p0 T4 M" K    }
    else
    {
        b[x][y]=0;
0 d/ l: \' t' J8 n1 v    }
( i8 U/ N+ r) ?1 A/ W2 ^   
2 R& z+ |; ^5 |4 [+ {    return sum;
9 g) d8 X! |) V8 O  W! s. _- A7 W}
int main()
% e! f/ Q# e2 p! ?( n7 K{
, ^' t$ I$ K. B! d) v/ `   
    cout<<"input 3 zone's limit:"<<endl;
( y# T1 h1 q! H+ [# t7 [    for(int i=0;i<3;i++)
& d% m4 ]& w8 h! L7 k9 _2 ^+ Y    {
        cin>>a;
    }
6 x" ~5 e! l9 j  v( P    cout<<"input 3*3 actangle:"<<endl;
% N! g6 \. Q: u# ]* O* M5 p, m    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        cin>>b[j];
    }
    for(int k=0;k<9;k++)
4 R" Z+ m) y6 D# F3 ]. q% H    {
        max_num();
* N$ p  z% L/ M/ b    }
   
    cout<<"sum="<<sum<<endl;
    cout<<endl;
    cout<<"reslut:"<<endl;
# |2 b. z/ d8 A5 P  t& v0 d% @6 G    for(i=0;i<3;i++)
    {
' J! ~  ^" J# q. u9 S# p8 L" e        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
    return 0;
7 F  t) w8 o+ {: o) F/ l) X}#include<iostream>
using namespace std;
" T* z# Q9 l7 J; F( I7 W( L7 Vint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
1 I+ N# o  i6 O3 Z0 F- f7 ~1 [: {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++)
    {
        if(max<b[j])
        {
            max=b[j];
  a0 X$ |6 N7 @& }            x=i;
" R1 I/ D/ |0 W; S0 x, d* B6 ?2 |            y=j;

        }
5 o, x4 k$ b( l$ w! x) U: ^% m    }
& B; k( s+ @; I& \   
5 f& D1 d" O! [    if(a[y]>0)
    {
4 E% G1 C7 ?& @- S2 j        c[x]=y;
        sum+=max;//总喜好度加上添加
/ |" R( f# h0 {. \) l$ w  d        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
" ?' V8 J2 A" ?5 [3 L  r        {
  f/ q0 e+ O% |2 S: u: @$ C            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
    }
    else
# l, G! k' N2 _1 c( q    {
        b[x][y]=0;
: ]1 K  _$ J" }, B    }
   
    return sum;
}
int main()
2 Y2 }  T0 P/ p$ e  I{
0 P( U! T; N+ _3 a' Y6 J   
    cout<<"input 3 zone's limit:"<<endl;
$ X) Q9 m9 E! k# H$ U- ~    for(int i=0;i<3;i++)
    {
        cin>>a;
    }
  f2 B/ p# K0 U1 p6 o, }+ `4 s    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
( [6 m' X/ m7 Y        cin>>b[j];
    }
/ w2 o9 c5 v/ }$ S    for(int k=0;k<9;k++)
    {
        max_num();
    }
   
6 a, {& k+ m+ u, Q, ^    cout<<"sum="<<sum<<endl;
0 k, ^0 I- w$ M7 @  x) X    cout<<endl;
9 G1 U  }$ ]8 H9 i% X1 e% k$ Y6 \' M    cout<<"reslut:"<<endl;
8 I: @% I. j8 @3 s$ }2 p6 X; o    for(i=0;i<3;i++)
0 u6 G) a+ g7 H* G) [    {
4 K+ d- ^' O4 f5 Y; O        cout<<"people "<<i<<" go to zone "<<c<<endl;
" j5 p0 b/ n. t: o: }6 c    }
    return 0;
/ K9 d' U, \* Y}

厚积薄发

编程代码二：
8 Z6 K, o! X2 I2 ~  X#include<iostream>
#include<cstring>
#include<ctime>
using namespace std;
% k4 f9 z1 E7 p6 Oclass ifo{//矩阵的元素
    int clerk;//员工号
/ s) X2 M- [& y6 T- T& K+ F3 Y* h+ h    int area;//区域号
# [$ h* O7 I# D" f    int per;//爱好度
# \3 X; E- R, n4 F# kpublic:
    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;}
4 k1 E0 g) ~7 _# t6 L! d    void setclerk(int i){clerk=i;}
' I  l, _6 F/ E# D    void setper(int p){per=p;}
% b: ?( i! y( L; s' m9 k: F0 u# s    void setarea(int a){area=a;}
};
+ ^# w& r8 e% a3 z9 Eclass area;
7 q# x2 e. h/ j% wclass clerk{
    int areanum;
  j! d) p0 E/ y# r4 I" t& [    bool isin;
    int inarea;
public:
# m0 ?& P2 u0 k7 h; Y    void set(int num){isin=true;inarea=num;};
0 {* P" U# {5 i% q8 d    void setisin(bool b=true){isin=b;}
% O8 Y8 N& i) f+ a% d4 a/ ?( \    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
9 B; p& ~' d& I};
; n5 D9 v3 \6 N3 m+ I, H9 Oclass area{
8 o) o9 i2 |7 J1 W    int num;
& R6 k: G+ u, V: b8 i    int max_num;
public:
    friend void set(int);
: d: t, K" K' I9 p, V    int getnum(){return num;}
    void setnum(int number){num=number;}
/ t0 w0 T, S+ i/ y, n4 Y( T# p    int getmax_num(){return max_num;}
    area(int number=0){num=number;}
1 R9 `  Y0 O" |3 @- z2 j    int getclerk(){return num;}
    void addclerk(int ps){num++;set(ps);}
/ x( L8 u3 U7 F. U) [' H};
2 G8 b# ?$ f' |( Zvoid getorderbyper(ifo array[]);
int areanums;
* ?! z# j/ K$ q& T% i) q& wvoid main(){
    //input
    cout<<"输入区域数：\n";
8 ^. Y8 P7 U  d) ?/ j7 q/ X" O    int area_num;
    cin>>area_num;
0 u# Z* A+ |+ d* o2 o: @    areanums=area_num;
3 f$ `% H1 u& I5 H    cout<<"输入员工数：\n";
    int c_num;
- e, l& [3 U0 M2 p    cin>>c_num;
    cout<<"依次输入每个区域能容纳的员工数:\n";
& {) ?6 r, C2 w    int *max=new int[area_num];
. m: f' I$ b( ^' Z. J    int nownum=c_num;
' L- W" m. I- x7 A7 e* M9 M    while(nownum){
        for(int i=0;i<area_num;i++)
        {cin>>max[i];nownum-=max[i];}
        if(nownum>0){
            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
7 t" P& y" f% \- `/ b            nownum=c_num;
4 J2 _' S9 O# \        }
        else nownum=0;
4 `; ]6 L& J: e8 Y9 K  I    }
0 o+ t" [8 R$ \  V) P    cout<<"按行输入每个员工的偏好：\n";
* d6 {0 l+ G0 c! 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++)/*
        {    int p;cin>>p;per[c][a].setper(p);
            per[a][c].setarea(a);
            per[a][c].setclerk(c);
0 z& p8 t6 `8 ^; J3 O        }
        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
        {    per[c][a].setper((rand()%60)+40);
            cout<<per[c][a].getper()<<'\t';
+ G% @- ~, \7 k9 q" T5 I        }//测试时懒得输入，故以60-100的随机数代替。
; t# N* U* J/ G+ v-    cout<<endl;
    }
7 o( J/ }# h8 M6 {- [    //output
        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
        clerk* people=new clerk[c_num];
        area*  areas=new area[area_num];
        int totalper=0;
        for(i=0;i<c_num;i++){
' L) r2 w- q1 u9 |2 ~            for(j=0;j<area_num;j++){
3 h$ B! \" f2 x' B; t6 |            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();
                areas[per[i][j].getarea()].setnum(number);
( @% q( o+ M% B' O! K4 {) H) i                totalper+=per[i][j].getper();
+ O6 f+ G8 _- w$ x/ d                break;
            }
0 Y. V; b3 L  X  M- u; i: e$ o& }; S        }
: H' E! ]: i: \7 ?7 z; u8 H- z        cout<<"能达到的最大喜好度为："<<totalper<<endl;
1 w7 V# }& M# a9 ]3 ?* [}
' r9 B2 D; _' ?: ^  Ivoid getorderbyper(ifo array[]){
+ j& i# v5 _0 Q    int max=0;
" Y2 x. S6 ?" o8 R+ r' {    for(int i=1;i<areanums;i++){
$ b  H  x6 s+ V: Y" M        for(int j=0;j<areanums-i;j++){
1 l: J& E, W: _4 U5 U        if(array[i].getper()>array[max].getper()){
% |8 o8 W  G( s% k$ N            max=i;}
% t: s1 s. E# ^" w6 {        }
, w, r8 e/ U/ v) z        ifo temp=array[max];
        array[max]=array[areanums-i];
+ o. F/ n& R1 N  A5 D; v7 m/ i        array[areanums-i]=temp;
        max=0;
* p) w9 a3 P$ P2 Q' \; a    }
}

厚积薄发

代码3：
- I8 H5 c# f7 l! j8 ]( o6 S6 v1 t/*
$ n6 ^' O. T0 J4 g$ S算法思路：
（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
1 a/ i/ ?, K& D7 ~5 R6 s再加，该人的所有喜好度设为0，
（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
: }3 j" @) ]  M' l0 j# C（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
+ ~) U  A+ H, i8 m) r, X(4)最后输出总喜好度。
*/
#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];
int temp[3];
int sum=0;
1 _% g8 v: `" Pint max_num()
, ]; s# n9 `( v% U: O  @/ @) g) N5 O{
# i2 |+ k6 [1 r( y* F& i    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
! M6 v' f7 f" `  q    for(int j=0;j<3;j++)
3 O6 }+ R% B$ m# g, d- N7 i    {
) W5 S2 I) u- x, r7 p' D, j7 {        if(max<b[i][j]&&b[i][j]>0)
        {
            max=b[i][j];
            x=i;
# O( ]6 b0 e1 {# F$ m            y=j;
4 P( P9 S( Z/ X* f3 B
        }
    }
   
    if(a[y]>0)
# I5 `. P! G, a0 p  e6 c9 F3 V    {
        c[x]=y;
        //cout<<"c["<<x<<"]="<<c[x]<<endl;
        sum+=max;//总喜好度加上添加
        temp[x]=max;
        a[y]--;//区域上限人数-1
1 i, ~( ^1 ^7 \& C9 E2 M6 R, X    }
    for(int k=0;k<3;k++)
    {
0 w. U9 G0 Y1 v" P        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
    }
    return sum;
$ Y; d( a6 Y/ v) p. K, _}
: n2 n! l& k! ^int main()
{
2 Y$ m9 M, A; g' i- Q   
    cout<<"input 3 zone's limit:"<<endl;
6 W. E" u- f/ q6 W) Q8 T! j    for(int i=0;i<3;i++)
    {
        cin>>a[i];
5 B" o8 I- ]/ i$ W  f3 l    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
  Y- w# k3 u2 h/ [0 Q- A4 [* x    {
        cin>>b[i][j];
: z( |+ B& U+ i& j" @6 Z    }
' o7 N( [% }, n" {! ?    for(int k=0;k<3;k++)
    {
        max_num();
$ B7 p8 ^' q9 v6 o5 K$ u    }
6 _5 _; Z5 B& f    //cout<<"sum="<<sum<<endl;
$ f; c8 _6 C- ~    cout<<"sum=";
8 Q+ R  y, P. q$ c3 Z9 @  B    for(i=0;i<3;i++)
    {
        cout<<temp[i]<<"+";
    }
    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
    }
    return 0;
}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
% @7 `# A/ L0 C数学中国社区分享快乐！
+ m" d# e$ \) v- C/ [

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.
/ f4 G) e2 U6 f

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！