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

厚积薄发

座位调整

3 [9 ?* F1 g. ~8 V( n. o题目描述：
2 O2 o# b' z/ [- H$ V
百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。

+ d, n: q( J2 z" O. G调整的方法如下：
7 J( }! m2 p$ M
1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。

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

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

数据输入：

0 ~+ t8 d6 y! a! S  _9 E第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。

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

6 x) v2 k7 a4 s/ z7 N紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。
2 f# g8 K: J$ X/ h1 h# r. ~0 t% _
9 ~/ H2 d9 y& S( @' @, W答案输出：

对于每个测试数据，输出可以达到的最大的喜好程度。

输入样例

5 w$ @! E/ v8 k, v( b
3 3

1 1 1

/ k$ b/ _+ n: T5 \# j3 T: v100 50 25

100 50 25
3 [3 {) L8 x- Y5 p6 \$ ]0 \. z' m
0 T4 s( q0 i% ?8 z5 N0 i4 n100 50 25
) z1 b  \  I' ^: I

6 a& M( Z& P" @  q( x输出样例

, r9 n6 ~+ j$ q" Z; _175
) M! {8 R; \8 f
  P+ i! a2 {( L6 H$ J( ]

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

厚积薄发

9 w% }8 G  s' B# N& N8 v& I- o; r4 j
& k  w4 ?2 \6 c8 I* K% a#include<iostream>
# P6 p4 x6 m6 G/ ]+ husing namespace std;
6 b# K. M  c& jint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
! q$ U& z0 d5 A3 Gint c[3];//记录某人i去的区域j
int sum=0;
6 H2 \  G/ x) t. Eint max_num()
- u/ T" p3 d( y7 O6 q9 S: n{
$ ^7 w" d2 }1 v    int max=-32767;
    int x,y;
, D4 w/ O* N" c- Z+ [1 z  F' h9 R9 E    for(int i=0;i<3;i++)
' S; L  ]4 I6 y2 E+ p, `  z! ^    for(int j=0;j<3;j++)
9 V* d* V/ B, w- D3 w$ @    {
        if(max<b[j])
' F9 o! J5 z8 B+ a        {
/ C6 N8 ?: R' z% Z            max=b[j];
3 X+ ^; F: b4 x# R            x=i;
# d& Y/ H# r9 A) I            y=j;
- ^1 D% s8 K+ [
        }
    }
   
% n3 |5 A* V# L7 s2 B% b0 [    if(a[y]>0)
    {
# j" S5 P( W: j) V& `) P        c[x]=y;
/ [# E" I7 b+ n+ `  l) g& B% q/ B# S        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
* |) m' [! H* g7 d1 X& Z        {
2 k6 Z7 F  z, U% ]) i            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
# q- F0 g2 U/ O1 \2 U4 C        }
    }
! l3 \0 c3 z1 M/ A# c    else
, {( |, o1 ^& A# u% u: o    {
        b[x][y]=0;
4 j  V" `0 b) H" [, _& x    }
; _& f1 n# l$ l  Z- D2 C- ^" @   
    return sum;
3 I4 H9 t2 w4 p% z: t  @}
int main()
{
7 H4 `+ i. o+ H) N   
    cout<<"input 3 zone's limit:"<<endl;
9 L  x! N* R: I( \) p0 W    for(int i=0;i<3;i++)
    {
        cin>>a;
- D- c' }& a1 O/ ]. n( Q- A    }
6 ^/ B! u& f% B: e7 p' t- @    cout<<"input 3*3 actangle:"<<endl;
) t1 X6 ^! R/ |    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        cin>>b[j];
    }
' Z+ W1 V) L- s7 O" J! ~! z3 H    for(int k=0;k<9;k++)
/ D& t! I/ L7 w  @! K- L" l$ f    {
        max_num();
    }
; X( K9 f0 `6 l+ Y1 m, W   
    cout<<"sum="<<sum<<endl;
    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
6 r0 Z# z4 q  d+ O, ~  M    {
( `! f$ n/ Q5 h& z+ A- |" ?        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
. ?& H0 ]# d& I! @: l# t    return 0;
}#include<iostream>
$ c, x% M) o. V- Z" a3 w' O2 lusing namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
int sum=0;
/ {0 X8 w$ B" P) M: V/ C# Fint max_num()
. ]5 a) @: m0 M' y- h5 _; g% v{
    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
- K' U! t$ F% l6 U    for(int j=0;j<3;j++)
    {
1 D& T& `9 o- E! L. I' p        if(max<b[j])
        {
. g# P  A, a. {% W" a4 M            max=b[j];
( w, P! m5 }8 S, y6 E3 H            x=i;
+ l% @4 F4 b5 k  A7 [$ [            y=j;

        }
    }
   
    if(a[y]>0)
" l" d1 O" A& A5 [- e    {
( y' z7 x, \  R5 C: m; y        c[x]=y;
        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
        {
3 a+ d' s) \8 i" _2 l            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
0 y, s! g8 k) S% T+ }: M0 p% e! r    }
" P  o  A, W, H    else
    {
" O. U6 `6 g9 D$ ^- R+ f$ x        b[x][y]=0;
    }
1 ^! |+ u" x2 E- m9 d* p9 |   
    return sum;
}
int main()
% G; |5 G8 E+ O4 Z0 V3 y{
$ O( T% r3 y9 F- j  U% I   
    cout<<"input 3 zone's limit:"<<endl;
* @# @1 H$ Q2 e; b% H    for(int i=0;i<3;i++)
    {
! S  W* N3 f& K        cin>>a;
    }
    cout<<"input 3*3 actangle:"<<endl;
& e, i" g; d: s$ _    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
( W# i1 ^7 i3 |* X        cin>>b[j];
    }
    for(int k=0;k<9;k++)
9 U! \6 L% R4 V+ \9 h' z; w    {
5 V: A3 v3 r% o! V8 }        max_num();
    }
   
    cout<<"sum="<<sum<<endl;
    cout<<endl;
5 V5 y6 }9 [7 F" ?9 f    cout<<"reslut:"<<endl;
) z  S" e6 r8 O    for(i=0;i<3;i++)
    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
    return 0;
( C& L8 M7 p' H( _7 X3 [# g4 z}

厚积薄发

编程代码二：
#include<iostream>
( `" o  W- f) O#include<cstring>
#include<ctime>
using namespace std;
class ifo{//矩阵的元素
    int clerk;//员工号
: G, t3 D+ A9 g- h! S    int area;//区域号
    int per;//爱好度
# \# n; _/ o: p7 r! S2 npublic:
    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
: S0 u7 m. Q) Z. C) j6 R    int getclerk(){return clerk;}
6 t/ H* q4 @8 M' K4 z- o7 W- H    int getarea(){return area;}
    int getper(){return per;}
    void setclerk(int i){clerk=i;}
/ N( B. ~% K2 O& A$ Z    void setper(int p){per=p;}
    void setarea(int a){area=a;}
};
1 X* }9 |0 A( w, o- X$ C. kclass area;
0 J6 W$ b: W( a& Gclass clerk{
% n: `% V$ B( J* g0 c6 H    int areanum;
    bool isin;
    int inarea;
0 _& L! e1 w8 Z7 F9 p2 ^public:
, J3 p6 V3 I2 Q, Z/ k) K7 M5 ~* D    void set(int num){isin=true;inarea=num;};
0 M4 f5 a/ b" W7 v; N( y" ]0 a) H/ e    void setisin(bool b=true){isin=b;}
! u- w' H/ G* C; C$ b! {0 q    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
};
class area{
    int num;
6 t3 K& C4 M# g    int max_num;
public:
9 f6 `. z( @  o/ G  w0 \% B7 _    friend void set(int);
    int getnum(){return num;}
    void setnum(int number){num=number;}
8 L( X) Q  D0 R, n* S  a' G6 }    int getmax_num(){return max_num;}
    area(int number=0){num=number;}
+ p" l" y0 z; h" b    int getclerk(){return num;}
    void addclerk(int ps){num++;set(ps);}
7 W9 e2 l8 Q; P};
, O: V2 C: q8 w" t0 I  ^void getorderbyper(ifo array[]);
int areanums;
- _* l, M( b) X: D8 B1 t2 avoid main(){
    //input
    cout<<"输入区域数：\n";
% t9 |+ }1 A8 ~. ^/ D9 k/ w    int area_num;
/ ^0 i9 |' v6 M. |+ W    cin>>area_num;
% o6 {2 h9 q+ d6 D1 e0 ?    areanums=area_num;
    cout<<"输入员工数：\n";
) [( T" }& F) I" q( Q9 e    int c_num;
    cin>>c_num;
    cout<<"依次输入每个区域能容纳的员工数:\n";
. @* M/ z# Y; U: ^8 {- }- j# }    int *max=new int[area_num];
2 f0 D/ Z$ j' {$ M2 P( K9 D& a2 V    int nownum=c_num;
    while(nownum){
3 `8 q2 M1 C0 g% l! v+ _        for(int i=0;i<area_num;i++)
: l) e* c  S; Y. x        {cin>>max[i];nownum-=max[i];}
        if(nownum>0){
            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
8 y2 g; n4 l+ S6 J6 H. i            nownum=c_num;
        }
        else nownum=0;
$ A5 b2 U6 C3 v" @( \& P    }
) P" b, F. c  V! n+ E/ W. {    cout<<"按行输入每个员工的偏好：\n";
    ifo** per=new ifo*[c_num];
    for(int j=0;j<c_num;j++)
        per[j]=new ifo[area_num];
* P9 {! w" J8 D+ u0 R& k, r    srand(time(0));
    for(int c=0;c<c_num;c++){
        for(int a=0;a<area_num;a++)/*
$ c: r/ l9 H$ r; M8 Z  ~% Y& [0 H) P  T        {    int p;cin>>p;per[c][a].setper(p);
            per[a][c].setarea(a);
            per[a][c].setclerk(c);
        }
& K" {) ^" o9 U4 u# U. h) D+ X        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
( V& {% N7 C. P4 P+ L        {    per[c][a].setper((rand()%60)+40);
1 K: x6 t8 \& A" j6 ?3 _            cout<<per[c][a].getper()<<'\t';
3 t$ m4 `5 \5 A2 P        }//测试时懒得输入，故以60-100的随机数代替。
-    cout<<endl;
' g5 ]' C6 N) |    }
4 U& {7 x* {$ H8 \! s" P5 k# |3 G    //output
        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
        clerk* people=new clerk[c_num];
. D$ c. ]* \, A& |0 }/ D$ H        area*  areas=new area[area_num];
        int totalper=0;
        for(i=0;i<c_num;i++){
' B. D) W8 T1 P            for(j=0;j<area_num;j++){
8 X$ v5 D: k, b* i  K$ D* U6 M            if(areas[per[i][j].getarea()].getnum()<areas[per[i][j].getarea()].getmax_num())
$ ^$ F+ W- }5 W0 F7 P6 C# c5 W                people[i].set(per[i][j].getarea());
                people[i].setisin();
                int number=areas[per[i][j].getarea()].getnum();
0 A0 r7 B4 Z4 j; P7 E9 s                areas[per[i][j].getarea()].setnum(number);
                totalper+=per[i][j].getper();
4 n) M2 M# b/ `4 p3 l; m. @                break;
            }
        }
        cout<<"能达到的最大喜好度为："<<totalper<<endl;
1 Z7 e" H' X1 {, z' H) `}
void getorderbyper(ifo array[]){
    int max=0;
    for(int i=1;i<areanums;i++){
+ l. c" l# p8 U4 Z1 W1 X: s/ g        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;
: E# N- c# H, t' w4 h        max=0;
% S: {; d3 G! N3 _* R& C    }
4 i- ^; X+ m0 H8 L* y: s}

厚积薄发

代码3：
/*
: F" H& O: J, s- \+ ^* H算法思路：
（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
2 E6 Q/ P# O8 c, f再加，该人的所有喜好度设为0，
) {, K4 M4 U5 K" B) t; l  l& j: B（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
. Y7 B8 G' z* S7 f9 T（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
(4)最后输出总喜好度。
4 a) I: o/ y; S! J. _& b5 w) n*/
#include<iostream>
( F( x0 u5 s/ }  O- U) q9 ausing namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
9 [$ [$ I) O( O. N  y, Dint c[3];
int temp[3];
int sum=0;
int max_num()
# V5 c5 [+ h4 N+ c- m, q6 c{
$ L& f+ F; b  p    int max=-32767;
* X& M' B' r* d% s6 P" f& {8 K    int x,y;
    for(int i=0;i<3;i++)
& o) j/ t& v" W# q    for(int j=0;j<3;j++)
6 D8 o4 G( T- I( |  ], x    {
        if(max<b[i][j]&&b[i][j]>0)
0 S& J, Y9 c% z* H  G- s6 _        {
            max=b[i][j];
            x=i;
            y=j;
. ^6 b, E1 z/ m+ O  {3 w
        }
    }
   
& x0 J+ ^4 c( {. ?( V  m; w    if(a[y]>0)
    {
        c[x]=y;
+ F  n+ m8 O. I6 L  L        //cout<<"c["<<x<<"]="<<c[x]<<endl;
2 ?! G+ J+ N5 i5 w% `0 T. M        sum+=max;//总喜好度加上添加
! t+ @6 \1 W3 P7 U% _        temp[x]=max;
        a[y]--;//区域上限人数-1
    }
: m. h# b  D9 U! j3 |0 r3 R    for(int k=0;k<3;k++)
5 B0 Y: B+ i3 ~+ Y$ ]6 H0 c    {
* R" S% A" v) U) p! G        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
, C0 H, b2 u0 a! s" e. B  I. m    }
    return sum;
}
) U: F/ [- J- qint main()
" H" |  }2 {4 z" h* w4 P7 V{
& V3 K" k) a! t   
    cout<<"input 3 zone's limit:"<<endl;
: e. m" [- y* r2 a" E    for(int i=0;i<3;i++)
    {
        cin>>a[i];
    }
9 M6 a! r/ |% b- m    cout<<"input 3*3 actangle:"<<endl;
  ~6 B' P7 |9 Q7 @6 J    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
+ R, o! w) G5 s' ~$ o        cin>>b[i][j];
    }
    for(int k=0;k<3;k++)
    {
        max_num();
1 V# ]2 S  I% {3 F- j& n    }
) J2 C+ e1 D) {, N% Q6 ~5 o5 V# k    //cout<<"sum="<<sum<<endl;
    cout<<"sum=";
+ \: y. X$ r7 |  j' h' B    for(i=0;i<3;i++)
4 K' V; P5 ~* O    {
        cout<<temp[i]<<"+";
, U9 l& `4 {, f% o' j    }
    cout<<endl;
% Y) s0 `5 }2 ]: T+ I! a4 r    cout<<"reslut:"<<endl;
# P0 e* _7 `* K    for(i=0;i<3;i++)
+ e& M* b' @4 k% f' b8 X    {
        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
. Y! P( s" e: Y6 B+ H/ `    }
    return 0;
" J: p6 o+ u% J7 D  a}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
& C* T% a' P9 _' k) u3 P8 q$ f+ Y数学中国社区分享快乐！
; x, b; N. X' l' e" {

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.
: k! X5 O8 S; a5 O  e+ w- W

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！