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

厚积薄发

座位调整

1 o% {4 l" a4 [: ~0 T, o# ~- _" D题目描述：
5 }; S9 b3 @5 _. X' F
2 W8 J$ Y$ d" f" f* t5 T百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。

调整的方法如下：
# M  A4 W! U* D' \2 w7 z9 w
& c/ D/ D! N$ @& |" j8 M3 }0 d1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。
/ d6 c, X$ e6 U# A  g, O
2 m. ^# D& Y# s$ Y+ x% A  B2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。
1 @4 Q0 x, E' H( L& ~: V/ I: j+ o
3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。
) T; u9 x8 _% G: M! M% c
数据输入：

第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。

第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。
- v) s( y6 c" l+ l: \1 Z+ a
紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。

答案输出：

8 _" ]' z/ y9 \% X  g对于每个测试数据，输出可以达到的最大的喜好程度。

输入样例

8 q2 T- [  p/ C* |
3 3
- Q- q5 S/ s( E' X# N
1 1 1
0 C% z1 b/ G! t5 |0 \
100 50 25

; e% L. g& _- d1 s: f1 E100 50 25
2 |/ T0 t# U1 Y7 x( `
100 50 25
8 n' m, S0 e7 Y0 T1 J

5 ^( O1 a; h6 L; p$ Y3 L0 t, m
% |8 ~0 s+ }! m9 w- K/ c4 |输出样例

0 p3 p& J- }+ N8 ^- o5 X1 s0 r
* I1 T+ c% t6 g( K2 {0 Q+ N" A175
% W. h: Z* ^+ O/ v$ ?/ r

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

厚积薄发

#include<iostream>
4 q' \: A' m  v& T# \using namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
( O0 \) T3 F0 s8 Yint c[3];//记录某人i去的区域j
0 b: B# ^/ L9 ?6 kint sum=0;
2 ]7 z: _- Z6 ~( w7 X+ [$ H$ ~int max_num()
{
% L' N+ Z1 D" W    int max=-32767;
  Q9 x3 Q$ H$ x- P1 |    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
7 E8 U. A5 b  A' u    {
+ M$ }4 Z; ~  R0 K4 _& k7 B1 c        if(max<b[j])
        {
2 Y$ }3 h) J" Z0 G; s            max=b[j];
            x=i;
            y=j;

        }
    }
   
, e5 Z. \' t3 n( X, J. A3 Z7 ^5 M, z    if(a[y]>0)
7 K1 B0 F7 {. a8 v4 D6 B/ k$ Y    {
8 K, A: {8 W* }) R; S        c[x]=y;
; j0 B& t. u7 ?        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
6 x8 U4 e  }2 _! m' z        for(int k=0;k<3;k++)
        {
% P: h3 {# ^, h& f# ?9 B7 o            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
6 ?/ ?( ~& Y+ t# O6 L" U        }
    }
7 f" X* C7 X; ^9 L9 T    else
3 Q0 t5 C# S; f- z+ h8 O, I    {
& h# h* k6 b- H        b[x][y]=0;
( G( a" i( E* ^) R  X    }
   
: J- f. A3 p) v" E    return sum;
; M) I: X. N+ O! ^0 ~+ L5 k% j}
- ]' C, S8 C- [4 U- n, P% h3 z  Kint main()
{
   
+ J: |9 V6 r; c    cout<<"input 3 zone's limit:"<<endl;
: F, I0 x' G+ D5 l( n; N( A    for(int i=0;i<3;i++)
    {
        cin>>a;
    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
( b& B8 `/ L" F9 ^! W* i( V5 h    for(int j=0;j<3;j++)
    {
  z+ _' I3 a! G. ?1 A4 Y- q        cin>>b[j];
! H" h8 W9 T. p    }
    for(int k=0;k<9;k++)
    {
+ W5 }1 i" l* {: O9 [3 _        max_num();
    }
! P% c' U* ]. U) U4 q   
    cout<<"sum="<<sum<<endl;
    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
% \$ O2 F/ F# T+ j1 E$ j    {
( H  k: X" M7 l' c0 r) j        cout<<"people "<<i<<" go to zone "<<c<<endl;
  c7 `5 B* b$ C# C- u# V, W7 Z    }
; K; G3 U# p+ h+ E# R% G% K6 t/ E    return 0;
}#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
* I( |3 C- o+ w7 rint a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
% g5 f7 i7 j8 O. Z7 _! N% T1 t' ^- ]int sum=0;
+ j4 P$ R/ y  ]: X, n5 Qint max_num()
# ]1 ]9 }1 d" z9 u$ {{
    int max=-32767;
    int x,y;
4 A, Y6 N# K0 B. G; ~    for(int i=0;i<3;i++)
$ U5 w% n5 b: N. b) _    for(int j=0;j<3;j++)
    {
8 D) B+ z' T8 h. u7 s        if(max<b[j])
        {
$ V7 u( g: r3 z6 X" ~, g            max=b[j];
            x=i;
            y=j;

        }
8 C: u6 ?; X; g8 k' o    }
   
4 X; {+ W# h0 m& x/ u2 G    if(a[y]>0)
% G4 W/ j1 t" p. ]2 J5 Z2 k    {
        c[x]=y;
* I6 P/ ?  z# Z. Q: e% Z: f        sum+=max;//总喜好度加上添加
* A4 H2 ]+ h( l8 W. V. [, ?        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
* q- H/ N7 [; b0 D        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
5 |4 z3 o$ {1 Z& T        }
    }
    else
/ x2 l0 z( ^# v3 u4 w; a& i8 Z    {
2 ]% c7 f7 w5 e& a        b[x][y]=0;
    }
2 y0 G& S/ e- R7 A1 q; {8 V: T   
    return sum;
}
' i6 c0 b5 N6 b& Yint main()
{
   
% w& h7 E" W# l0 q5 w    cout<<"input 3 zone's limit:"<<endl;
  F2 ]+ [5 ~# p% S    for(int i=0;i<3;i++)
6 [- ^2 ]& t, ^) [9 p    {
        cin>>a;
    }
, Y4 p3 b" \; M7 a    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
% F( n, a1 v" `        cin>>b[j];
5 N! E6 F5 v1 Z  A$ u$ v    }
    for(int k=0;k<9;k++)
; x- y0 l) H  J5 j) E. F    {
; C. _1 r. Q% E4 ?) p        max_num();
- u4 I; n' q8 b    }
   
- y8 n: `1 |. ~' Y' L& K' J+ [    cout<<"sum="<<sum<<endl;
: l) q; u! Y; j& }) a9 @, {& ^& q. t    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
+ k5 B- P1 ^5 A9 ^  R    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
, Y+ S4 W- i9 g    return 0;
}

厚积薄发

编程代码二：
3 g5 N" K$ H/ r; K' o# ]#include<iostream>
#include<cstring>
#include<ctime>
& {  B5 T0 L7 \1 xusing namespace std;
class ifo{//矩阵的元素
    int clerk;//员工号
    int area;//区域号
    int per;//爱好度
& v4 i: q/ u$ t' P0 cpublic:
    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;}
3 L' k! d$ A4 y3 J- M    void setclerk(int i){clerk=i;}
9 ?8 }2 u' ~7 {8 o8 S7 {; B. c4 G    void setper(int p){per=p;}
    void setarea(int a){area=a;}
  \5 i4 t8 [+ G) S};
class area;
2 f% y+ A+ n0 r& C# xclass clerk{
1 r( Q2 L) |& p+ B: |3 `    int areanum;
: D* p; y5 E- Q) `) [    bool isin;
    int inarea;
* x/ g" ?0 X8 A* r1 C( o5 k  Kpublic:
( \5 C4 p! G1 g/ d5 `, O( T    void set(int num){isin=true;inarea=num;};
    void setisin(bool b=true){isin=b;}
- P8 J! p2 i* n& [3 K- a* f5 a, B2 ^    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
};
class area{
    int num;
    int max_num;
public:
$ H" q& X! O) y/ u/ P    friend void set(int);
3 L1 ^) B, u% w5 D    int getnum(){return num;}
    void setnum(int number){num=number;}
    int getmax_num(){return max_num;}
6 }2 h" C7 z9 Y- C: l- e    area(int number=0){num=number;}
% f8 T% Z& `# I1 F# r% L' ]6 U    int getclerk(){return num;}
3 N0 W4 ~6 z  C, _8 I* k- ?    void addclerk(int ps){num++;set(ps);}
};
void getorderbyper(ifo array[]);
int areanums;
void main(){
1 m4 I( o& H+ p% \    //input
    cout<<"输入区域数：\n";
. F% S8 [4 ^* w$ E    int area_num;
1 C- Q) b% a% ^6 ~9 g! N! f$ Q    cin>>area_num;
9 o5 p1 |1 X8 o/ b  \    areanums=area_num;
, S7 b0 ~: @3 E    cout<<"输入员工数：\n";
    int c_num;
* g6 [( ~" r5 r* _& L    cin>>c_num;
    cout<<"依次输入每个区域能容纳的员工数:\n";
    int *max=new int[area_num];
1 @9 L# P* U5 P$ m% V$ o5 o* q! ?. o    int nownum=c_num;
    while(nownum){
        for(int i=0;i<area_num;i++)
( v5 H3 j% z! M# c  B- [- b        {cin>>max[i];nownum-=max[i];}
; P) v4 G# l: z$ ^& p0 m% h        if(nownum>0){
5 e# u% k3 }2 C5 A; W4 W( c; a            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
            nownum=c_num;
& T4 r9 p; w6 ?6 _" P        }
7 s  ^/ l: F! C$ d' l        else nownum=0;
$ K6 e3 i' N4 h6 a1 P$ v    }
    cout<<"按行输入每个员工的偏好：\n";
' J& A# _! e1 R3 G) {- U    ifo** per=new ifo*[c_num];
* ~+ ^) X1 K5 v; L* J3 i. B    for(int j=0;j<c_num;j++)
4 N% f5 F) W+ h5 {& t% T' ^        per[j]=new ifo[area_num];
! c! d- R6 p  E7 x    srand(time(0));
( X5 `" G3 I% I; S2 w. N    for(int c=0;c<c_num;c++){
8 P' @- o- i; y& K% s        for(int a=0;a<area_num;a++)/*
4 R( Q6 V* Y- @2 ^! W        {    int p;cin>>p;per[c][a].setper(p);
            per[a][c].setarea(a);
/ |3 ^' v- G. A. h+ M- \            per[a][c].setclerk(c);
        }
        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
        {    per[c][a].setper((rand()%60)+40);
            cout<<per[c][a].getper()<<'\t';
+ ?; E5 N% H2 d8 [) {% r        }//测试时懒得输入，故以60-100的随机数代替。
) c- G$ ?/ N0 ]# A-    cout<<endl;
    }
    //output
9 W9 m/ e3 ~* }6 s7 A1 y: M) N        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
' Z; }( P3 N. W1 F+ P# L4 K        clerk* people=new clerk[c_num];
        area*  areas=new area[area_num];
        int totalper=0;
        for(i=0;i<c_num;i++){
# E7 K; b/ S% g( C% d# H            for(j=0;j<area_num;j++){
& d, ?6 N" I8 G8 l8 s9 j7 L            if(areas[per[i][j].getarea()].getnum()<areas[per[i][j].getarea()].getmax_num())
                people[i].set(per[i][j].getarea());
. g9 m" g) P3 V; [                people[i].setisin();
                int number=areas[per[i][j].getarea()].getnum();
                areas[per[i][j].getarea()].setnum(number);
8 a3 c% ]0 n' d6 N* ]& v5 h. n5 T/ W( d                totalper+=per[i][j].getper();
0 E! {7 h7 Z9 f0 I( n. U                break;
            }
/ D. ^+ W8 @1 @$ Y" i        }
4 j  D9 X" |, W% m        cout<<"能达到的最大喜好度为："<<totalper<<endl;
6 n& n4 w3 _( y1 [1 K  a4 Q}
void getorderbyper(ifo array[]){
0 w$ I, y! k. E& F    int max=0;
4 K& p7 R, W; H' |/ I    for(int i=1;i<areanums;i++){
        for(int j=0;j<areanums-i;j++){
7 j2 J! |3 X# L3 S/ o        if(array[i].getper()>array[max].getper()){
2 M, m6 j% D/ O1 \            max=i;}
        }
        ifo temp=array[max];
        array[max]=array[areanums-i];
        array[areanums-i]=temp;
        max=0;
    }
% R# `4 W# r5 i! @0 H}

厚积薄发

代码3：
% ^0 [! l$ Z  V2 {7 k0 V& t$ f$ \  M/*
" u7 T. D7 Y( w- s算法思路：
) a4 e. s0 s2 J: h8 K# ]4 b% w6 k) j（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
再加，该人的所有喜好度设为0，
（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
(4)最后输出总喜好度。
: U8 H: Q" V# P1 I9 U- F! L- n*/
: H! D2 g9 e, o! X1 R#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
2 U& u( Z2 F( J9 hint a[3]; //区域人数上限数组
/ H- N( K& P1 bint c[3];
int temp[3];
1 F+ A' K+ k- Pint sum=0;
int max_num()
{
    int max=-32767;
    int x,y;
, S/ T+ ^0 ^7 ]2 X7 j    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
8 Q3 q! ]8 V9 O( W& c  R. Y) t( w    {
        if(max<b[i][j]&&b[i][j]>0)
8 T# E' Q' q. r4 ]4 s  Z5 _/ l        {
  {5 q0 `0 q' Z9 \, b4 u* ?            max=b[i][j];
            x=i;
            y=j;

        }
# l- Z( {1 M4 q) h2 m7 ^    }
   
% x; B/ A: r1 ?* W) _    if(a[y]>0)
    {
, L" F* N  T5 V" e1 U, z        c[x]=y;
        //cout<<"c["<<x<<"]="<<c[x]<<endl;
( F! F4 o- {" v2 X' \        sum+=max;//总喜好度加上添加
0 ?  q' r2 B/ q  |3 v        temp[x]=max;
        a[y]--;//区域上限人数-1
, z5 U6 U5 }/ p5 w6 q1 r) |' Q    }
6 l# `- U3 k) k9 }# V' c8 m    for(int k=0;k<3;k++)
! c" @; f0 x- L; t: ~) J0 E    {
        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
    }
    return sum;
}
int main()
/ _4 {+ C  T$ J{
   
6 |+ u8 G, q. v7 ~4 D, j0 _    cout<<"input 3 zone's limit:"<<endl;
$ X/ d5 }& y& R+ u6 k( y: g: G: K    for(int i=0;i<3;i++)
    {
        cin>>a[i];
+ Q2 K# r9 i1 @) a& D! s+ K    }
    cout<<"input 3*3 actangle:"<<endl;
4 O% H& i3 z( O. V    for(i=0;i<3;i++)
% P# x/ ]! s: x" v    for(int j=0;j<3;j++)
    {
3 O+ N# s* C1 Q3 _( m- `& ]        cin>>b[i][j];
    }
    for(int k=0;k<3;k++)
    {
, C! b" q6 I- @7 _9 s2 x3 i        max_num();
* J& F4 U9 k+ _* M    }
    //cout<<"sum="<<sum<<endl;
    cout<<"sum=";
% S+ @; e- S7 @$ \    for(i=0;i<3;i++)
2 X, r. h+ I# N) Q    {
        cout<<temp[i]<<"+";
8 \3 a  n! G5 ?. t7 N    }
    cout<<endl;
7 l+ a' t, E8 x( ]- q    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
/ u3 C, H. ]: G* J3 [; ^2 h+ O    {
        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
) f8 }" O3 R7 p0 w" Y    }
    return 0;
}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
5 P( l+ x- G  h数学中国社区分享快乐！
& ^8 [# y. a; W

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.
( h  R4 ]: o# T$ E5 A' p4 _: z

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！