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

厚积薄发

座位调整

题目描述：

+ Y( r8 z2 S2 ~: p: H3 O百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。
6 d# b4 Z. D6 V
. _4 u1 ]0 N6 T- _, W调整的方法如下：

; v$ J# @3 @2 x6 w: I4 K; n. i1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。
% W7 O( D' Q# Q( b
, {  e8 @4 q: B" a9 _+ J( c. `- H2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。

. p3 x+ p* w) M: A- {4 @5 ]7 `3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。

数据输入：
. l9 ~, P. K' O/ H) z* ~% w9 r# x) n
第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。

第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。
  J/ {/ t! n2 @( [+ s8 B
% I7 u* Y% I5 s紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。

答案输出：

对于每个测试数据，输出可以达到的最大的喜好程度。
! C" B4 N  U2 u* ]1 d. K; F
输入样例

6 Q3 L- i4 `' q4 O- R9 m3 3
: ~4 T# O! |0 v5 z  B9 J
1 1 1
6 h: P  N5 W' Z8 S3 Q
; c. A% r  K; b! o. V1 F0 t100 50 25

100 50 25
/ G9 r5 L' F6 j! q& _" w- O
100 50 25
3 u6 A, j1 ?; [/ X2 I0 Y

* q# t, o9 y+ |9 O: v" {- T
: O+ S9 s- a# n. h3 Z# p( |0 \  Q输出样例

2 ~3 Q+ _. r0 d
6 X& S- e" m  J0 \$ M8 d4 Z3 ]; ]3 `175

9 T( t/ y, f& E: T$ c, s+ m6 q

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

厚积薄发

* w( a- ?! I( H9 H0 m
#include<iostream>
+ N$ i/ s5 |; \! Y$ busing namespace std;
7 A8 V+ L+ n) l& E- Uint b[3][3];//M*N矩阵
4 J: M5 X" q7 _. ?2 H6 o" @7 Xint a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
int sum=0;
int max_num()
{
' T) e0 S* l* N: d! {. x: O    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
/ Y$ f# B" r4 `8 n" A; T1 W    for(int j=0;j<3;j++)
% |$ _2 s, w0 z' W9 v: S    {
        if(max<b[j])
& p8 l' @+ X; u" O( E        {
            max=b[j];
            x=i;
" a( j8 \, _. G( T            y=j;
5 P. V( u2 X9 E6 K0 r6 u1 b
4 g9 _8 b, p( l4 A& }/ X        }
    }
   
    if(a[y]>0)
$ I7 J3 [" E* j4 g( L' B    {
        c[x]=y;
& l% {- p7 x' [        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
0 n+ V) c/ G; p. @8 W- l        {
0 n( f1 u$ m: _3 b7 @$ k. Z            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
0 I% ^: U! T, O& |, q% u        }
    }
    else
    {
        b[x][y]=0;
' d4 e6 u1 a0 q. D. }    }
/ O* Z* y- D$ n   
$ W* Y0 q/ f6 _    return sum;
}
% l# `. v0 R/ B& ^) @; U0 tint main()
{
   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
2 q3 I& a# b: B8 Y/ }    {
( E  _: i4 h: N% E5 ?1 m        cin>>a;
, M: U- K/ M" E- U$ u& m    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
6 o6 m4 @, T, n& X. j- ~& r; }7 B) r    for(int j=0;j<3;j++)
    {
        cin>>b[j];
3 g; J8 b& d- Q4 i    }
    for(int k=0;k<9;k++)
    {
/ g% h0 S: T& \5 ~! G- a' [& }% E        max_num();
) h/ D/ S0 ~$ d. C2 L, Z4 x    }
8 e+ t+ Z( B; h5 b9 @& x0 F% ~* i: @   
6 j8 E0 u/ @1 x+ T+ a    cout<<"sum="<<sum<<endl;
    cout<<endl;
; L+ F4 x/ o0 a    cout<<"reslut:"<<endl;
2 a3 U! d+ O5 a, G/ j    for(i=0;i<3;i++)
    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
( P1 k, f* k; v1 q- }6 W    return 0;
2 ?6 k4 m% t3 l+ v}#include<iostream>
' Y. `: O+ K( m$ o+ \& lusing namespace std;
" s' @& |: Q0 iint b[3][3];//M*N矩阵
' {  S& {. ?2 Tint a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
0 F, Q$ K" T5 e; ?/ A0 S  E- E. C0 U* pint sum=0;
  \% Z8 I: y% p5 v6 \5 Tint max_num()
% q6 S7 v" o" C) J5 n- {{
    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
4 h" x' F+ q, P5 M1 E( M    for(int j=0;j<3;j++)
5 h9 m+ a4 w2 h; t, Q    {
        if(max<b[j])
        {
* x( e' v0 a, {0 S/ E6 `            max=b[j];
9 w3 v2 @$ y9 g4 [9 p9 U5 @8 Q            x=i;
1 }  M* v+ z! \( n            y=j;

& Y) r5 Q5 b' H2 ?9 F        }
/ M1 r( N' F3 f) A7 b3 |. o8 E    }
   
    if(a[y]>0)
9 r" Y7 ?9 u8 T& J    {
5 U. T1 u/ y# ?/ m" I  @3 z        c[x]=y;
        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
& ^7 O. c& ~; X3 T9 n" c        for(int k=0;k<3;k++)
        {
8 N: H7 j" @5 E  }0 f            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
3 `0 m( ~4 x2 b, ]/ P        }
    }
    else
/ W- F6 g" N, g' v/ U3 g    {
! m; p- [% \: n$ I. U, u! d; @+ a        b[x][y]=0;
    }
   
    return sum;
}
int main()
* p6 ]7 _- [4 ]! r; r( y8 ~{
   
    cout<<"input 3 zone's limit:"<<endl;
$ I; F) L7 a8 Y+ F    for(int i=0;i<3;i++)
    {
        cin>>a;
$ m& f8 }2 |1 m/ d    }
/ }. @$ F6 @9 V  Y; B2 B) j: @/ o    cout<<"input 3*3 actangle:"<<endl;
6 g0 c0 H( i# a: \: a    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        cin>>b[j];
    }
    for(int k=0;k<9;k++)
) J- u$ o: T/ |( ~! B) T+ ^' d    {
        max_num();
. `$ z: c) x, g4 c- V$ {    }
   
    cout<<"sum="<<sum<<endl;
    cout<<endl;
1 a( g) {; ]) S: [    cout<<"reslut:"<<endl;
# G) p1 @( T6 H    for(i=0;i<3;i++)
8 g( m) |; |/ P/ y$ c- m% [+ w    {
0 k* |" `, o2 i$ @        cout<<"people "<<i<<" go to zone "<<c<<endl;
9 `: E! A0 }, [    }
    return 0;
' @1 f' m6 t& a6 E- m  B}

厚积薄发

编程代码二：
#include<iostream>
1 A7 ]. p. p+ t- X6 Z( @: p; O#include<cstring>
#include<ctime>
) X- c( q. x. P, p0 v. _& Q  h5 busing namespace std;
class ifo{//矩阵的元素
0 @6 @, e8 h: ]) f+ w+ i- r  [9 `+ ]    int clerk;//员工号
  v* g, O: `! H2 H    int area;//区域号
1 K: ^$ y/ [8 `* q  W+ x, @    int per;//爱好度
public:
+ \0 C, `5 j/ k, m) B9 d- }4 ~    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
    int getclerk(){return clerk;}
6 K' g: o7 P( S' @    int getarea(){return area;}
' B& r1 K, w# Q$ N2 M9 C    int getper(){return per;}
    void setclerk(int i){clerk=i;}
/ O; ?$ e  P# F& c    void setper(int p){per=p;}
+ @. m9 x" ^! [/ d: j% x    void setarea(int a){area=a;}
};
class area;
5 Y8 |, B# k3 E, K7 Aclass clerk{
    int areanum;
7 h  Q, N7 ~/ x: q3 ~. b    bool isin;
4 z4 C/ E# H1 }+ T6 k    int inarea;
public:
    void set(int num){isin=true;inarea=num;};
7 f% I$ m; E- ]9 S    void setisin(bool b=true){isin=b;}
8 G% R3 I4 A* c# H* T6 H    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
9 B; v5 r: \" r7 `* Y* q4 ~' X. z9 ?};
# I9 @2 F5 U7 K: Q7 j) \, Y9 V/ o1 M# Kclass area{
    int num;
    int max_num;
- Y8 g3 Z; P- [" q) S2 R1 Zpublic:
    friend void set(int);
    int getnum(){return num;}
+ L& y1 m2 e) v8 c1 f) d    void setnum(int number){num=number;}
; Z4 O$ W% G  ^. F    int getmax_num(){return max_num;}
: J2 o. n) p+ g8 e; Q  p1 S    area(int number=0){num=number;}
: n, R8 [! {5 z/ _" H$ c( e( ?0 m: t    int getclerk(){return num;}
    void addclerk(int ps){num++;set(ps);}
};
7 J) \2 {9 d9 ^6 K8 @1 G9 jvoid getorderbyper(ifo array[]);
int areanums;
' v1 N/ K4 H2 S- l- [void main(){
    //input
    cout<<"输入区域数：\n";
    int area_num;
& U) k4 n: m9 |: U0 r    cin>>area_num;
    areanums=area_num;
    cout<<"输入员工数：\n";
    int c_num;
    cin>>c_num;
' V- o# l! g9 G    cout<<"依次输入每个区域能容纳的员工数:\n";
$ f8 G* _, V" |. ^9 }    int *max=new int[area_num];
    int nownum=c_num;
( j$ |* |& P# }7 O' \    while(nownum){
        for(int i=0;i<area_num;i++)
! x0 N/ b, u; Y2 R        {cin>>max[i];nownum-=max[i];}
        if(nownum>0){
            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
            nownum=c_num;
        }
2 {8 Q, F4 M* d/ r        else nownum=0;
    }
    cout<<"按行输入每个员工的偏好：\n";
1 s0 b0 E+ c. c9 ~- z    ifo** per=new ifo*[c_num];
    for(int j=0;j<c_num;j++)
# l" {& O$ G9 z- T% \5 e2 a( w+ T5 ?        per[j]=new ifo[area_num];
    srand(time(0));
    for(int c=0;c<c_num;c++){
7 I1 s1 T. s& k( m+ o5 {        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);
        }
+ v* ]% K: Q: u1 [3 k( i5 Q" i# G        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
        {    per[c][a].setper((rand()%60)+40);
            cout<<per[c][a].getper()<<'\t';
        }//测试时懒得输入，故以60-100的随机数代替。
4 A$ h! D+ G6 g4 F-    cout<<endl;
  M3 {9 y- [2 W- u    }
    //output
9 H% ^  ^) \+ L5 F/ i( m9 x; G        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
1 q; Y& b; K  x  |( L) H        clerk* people=new clerk[c_num];
        area*  areas=new area[area_num];
% u' z5 n/ j( Y9 t, B! L% D' R        int totalper=0;
        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())
                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);
                totalper+=per[i][j].getper();
                break;
" D; ^" {! r$ k8 q8 s% n  X; J/ H2 ?            }
        }
' I" g+ c4 z' K! A        cout<<"能达到的最大喜好度为："<<totalper<<endl;
$ ^8 z) m( y. }2 W1 e}
. b3 |$ F9 w9 F. _3 f  Evoid getorderbyper(ifo array[]){
    int max=0;
    for(int i=1;i<areanums;i++){
        for(int j=0;j<areanums-i;j++){
. N& l; ~$ a) O: z- b+ b        if(array[i].getper()>array[max].getper()){
            max=i;}
! F  b4 v8 M" L" N4 A" T3 u% F        }
( X- r4 @% V7 E# t1 |' D: \; h4 P        ifo temp=array[max];
5 x3 c4 B: d- p. B' W0 c: n, ?! T        array[max]=array[areanums-i];
' |0 t% o: r$ O$ z6 ]/ G        array[areanums-i]=temp;
        max=0;
4 E% ~+ S7 d. E3 H. @    }
}

厚积薄发

代码3：
0 N. \- w% @3 p- y" ^3 S4 I/*
$ c, Q* M2 K5 b# N  e算法思路：
2 ?' s1 |+ K# _8 I2 z9 U* V（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
再加，该人的所有喜好度设为0，
/ ]9 h+ i2 u0 W6 V（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
(4)最后输出总喜好度。
- t6 Q5 t7 M5 _6 B# ]*/
9 h5 S$ r; ~. b2 J#include<iostream>
using namespace std;
! K8 T/ b3 V7 x; {3 L2 Q( R5 R& Qint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];
int temp[3];
. n, f/ n; b4 \+ F( [# u+ k( U8 lint sum=0;
! ?' H0 f7 u- i& r" R2 Yint max_num()
3 k# n7 H9 `( N! g9 J* ]5 T{
+ H2 s; a6 ~, P6 t5 r$ D& Q    int max=-32767;
- a9 {0 W5 G0 L) J    int x,y;
/ S4 f8 l5 Y2 g) W# f3 t    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
+ l" S5 N) _/ q    {
- `; L; k% m* U* R4 Z        if(max<b[i][j]&&b[i][j]>0)
0 L% p& O# @$ ~3 D6 M/ f        {
            max=b[i][j];
            x=i;
            y=j;
! o2 a1 |, N3 \  n2 i: }; \' P
" U) k1 W" Q) g" ]2 d7 p        }
; z; h$ @% g& Y* `5 ~    }
   
; H( g6 ]$ M. W    if(a[y]>0)
    {
        c[x]=y;
        //cout<<"c["<<x<<"]="<<c[x]<<endl;
0 ^- Q% \3 t) Q+ C, P        sum+=max;//总喜好度加上添加
9 Z$ o! ?2 _; z: S* I8 R/ t5 e# D        temp[x]=max;
        a[y]--;//区域上限人数-1
    }
/ F  W0 U' B, |+ Z7 n/ u' s+ X    for(int k=0;k<3;k++)
8 K+ }+ w% ?8 X- }% C6 l- Y( G. ~' t8 {* |    {
# [! P  C# f* M. [6 P        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
6 z) i% [9 j" t& a2 }' K5 R9 s    }
# O7 S: N0 I% e; N1 i& v    return sum;
1 D& ^$ c) W- G8 N% o, D- @}
int main()
9 f9 t/ ~% D( A8 O( d{
   
+ J' V# R( c! R* G8 {6 n! w4 v    cout<<"input 3 zone's limit:"<<endl;
" [; W7 s, D; F& n$ e0 r" E$ }    for(int i=0;i<3;i++)
    {
        cin>>a[i];
$ @* B) C+ S9 n  ]  u    }
4 ?! ]; |5 ~9 y1 a7 J5 I, I* B    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
1 {7 R2 C+ r6 _    {
        cin>>b[i][j];
    }
* x* P9 g2 i6 z! Z- ^: L    for(int k=0;k<3;k++)
  E9 w- Q1 ~5 }# N6 E    {
  o% `, e; Z2 k) N9 x$ I# L0 \        max_num();
    }
    //cout<<"sum="<<sum<<endl;
    cout<<"sum=";
    for(i=0;i<3;i++)
- {+ K& [4 U5 L8 g    {
        cout<<temp[i]<<"+";
& `* L* m! v4 c" d" |6 W    }
    cout<<endl;
9 k) z4 x* F& ^- R    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
4 W6 g1 _; l* |    {
' h: ^- \% T) ~+ f7 `+ T6 Q        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
    }
    return 0;
# U4 S) o* h. P8 l, y( W}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
) d+ T7 Y3 D- E2 W) W数学中国社区分享快乐！
# k( ^% b4 y' h8 H* x2 D  x* G

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.
# N  N- n. I! v3 L9 H

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！