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

厚积薄发

座位调整
9 r1 \- Z5 s$ x- F3 j' z
题目描述：

3 V/ V9 j1 y: f, |3 f百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。
. H3 W; ^2 G+ `$ h
调整的方法如下：
  T, p& t6 a" k% f" O
1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。
- k$ e7 _# d! u
2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。
  {$ |8 k, Q% g& n/ C7 O" x
3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。

数据输入：

! l) F% @$ S% U5 X7 M) i第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。

' L' `- j  G8 H8 z; G2 m9 ]& }% ~第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。

! H7 t  I5 T/ g' S0 _紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。
0 u0 N/ t  z9 z3 K" l
答案输出：
9 W1 P5 S! W+ V' v4 H- i
- J! E) j' @* l) S& `对于每个测试数据，输出可以达到的最大的喜好程度。

输入样例

1 l4 S' |4 R4 O3 3

1 1 1

& B5 p# p8 I. t100 50 25
! _- t* @% V; \/ \3 F1 U
100 50 25

: e5 l5 r" ?" V* p$ k# @$ l100 50 25

$ ?3 D8 S9 q4 I% q+ K" |输出样例

2 R! V" @. e1 b
! `" c- s# n5 s  O% n175

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

厚积薄发

( b% n5 h3 F4 x; ]#include<iostream>
using namespace std;
6 Z1 I% d& n; J) z- z, M8 K9 L# xint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
* ?% P- I% b2 {9 C( h( |int c[3];//记录某人i去的区域j
int sum=0;
int max_num()
" n& D( x/ [; e: i, b{
    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
; O- [' V8 e4 i! j* E$ l0 R+ ^    {
        if(max<b[j])
        {
            max=b[j];
7 U. [$ }( d% W' ?8 |( t: w            x=i;
            y=j;
! l2 q+ w: P' x) E) Q
        }
    }
   
    if(a[y]>0)
0 v3 v; ]# n9 P5 H  e+ I    {
        c[x]=y;
        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
- r* ^, G% ^; f2 ^, H4 y    }
    else
, z5 k0 }' e4 j6 X+ D    {
        b[x][y]=0;
2 Y/ x6 {& c8 ?; f    }
2 F5 W) M# E$ {$ _3 u8 j* b   
  G9 f$ e5 W% {" r5 p3 e! ~# H    return sum;
! |( p* d% u$ m6 ^! d9 G" m}
int main()
' O. p* ^* R# r% g1 ?7 G" Y{
  }3 y! I. ~2 ~) n7 V9 w$ X. D$ |8 \   
    cout<<"input 3 zone's limit:"<<endl;
& F/ P  Q4 }% A0 h+ i6 s- Y    for(int i=0;i<3;i++)
    {
        cin>>a;
    }
    cout<<"input 3*3 actangle:"<<endl;
/ N- O& c/ ]! {' j8 x( N2 I    for(i=0;i<3;i++)
; Q! s3 H. k" I! ]; i" U    for(int j=0;j<3;j++)
    {
- r& ~3 w9 [7 C7 G* a+ x- Q        cin>>b[j];
+ `: g. e  O+ t    }
    for(int k=0;k<9;k++)
! n7 @' z  c* j% T    {
        max_num();
    }
   
3 s, ]; h- r; a2 U3 C: V; s# D    cout<<"sum="<<sum<<endl;
0 i* N3 D8 P+ P; n- g# n$ [; z    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
- V+ v9 W+ W$ e) I        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
5 d4 A5 z8 g# K5 i+ C+ A    return 0;
9 _. p) H: L& e! Q}#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
" W/ O+ }: l+ W4 B. G! O) tint sum=0;
int max_num()
3 Q0 _2 L% P& Z3 a/ T2 r! @{
    int max=-32767;
    int x,y;
* O9 @2 f: m9 b6 s+ V% x  T    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
" m2 h" I7 x7 J# r, S+ k        if(max<b[j])
( }# Y+ l1 |. C. H        {
            max=b[j];
            x=i;
            y=j;

        }
    }
+ ?1 \# ^* H* w# F- @& b+ Y   
' c2 B' T9 U' g( p+ l    if(a[y]>0)
    {
        c[x]=y;
% s+ A: H  l1 j3 U, D- Y- D; Y, m" y        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
/ T& n2 K; }, i2 R4 ~% U: R        for(int k=0;k<3;k++)
8 @1 A" A! N9 I" U9 T- X        {
# H( l) l8 B  c/ e' B8 t            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
) A' A7 f+ K: O$ z( S/ j    }
! {) f' c3 E( e* t3 Y    else
    {
        b[x][y]=0;
    }
   
    return sum;
) l0 K' m- H3 J! y1 q, y# C( R4 D}
int main()
- g' e1 K" e! Z{
   
/ w) j. i! e2 [' w. R3 y    cout<<"input 3 zone's limit:"<<endl;
% N6 q/ F9 g7 |0 O+ z    for(int i=0;i<3;i++)
6 g: Y8 I( Y. B* ?6 Y: C) P: F    {
0 u# t! w& ?: u6 _! ]        cin>>a;
    }
    cout<<"input 3*3 actangle:"<<endl;
. i/ G' v) t5 d) E' E% b    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        cin>>b[j];
4 b6 h' f8 s) q) Q+ }- u    }
9 c( i+ [+ k) n/ q  w    for(int k=0;k<9;k++)
. u7 y5 G# B7 R+ x( g* j2 f    {
        max_num();
    }
0 t% V; o& ?5 a# Y( Z. X$ E   
4 p7 j: E: Z7 x4 `( p4 r  J    cout<<"sum="<<sum<<endl;
' d, h; ?* o. M$ G    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
4 K6 h: n" f- D% A$ P; K        cout<<"people "<<i<<" go to zone "<<c<<endl;
; s$ k. o1 J& ]8 y# ?4 q7 R    }
, x' e" N) Y8 ?  U" q    return 0;
' G0 m! Y& d1 K+ |9 S, Z0 U/ ~# Y: O}

厚积薄发

编程代码二：
#include<iostream>
$ B: I! P7 B$ w$ [7 R8 p#include<cstring>
#include<ctime>
using namespace std;
4 L7 ~5 `0 c: |class ifo{//矩阵的元素
* E, R8 i9 H# Z# h1 `+ q- d0 C    int clerk;//员工号
5 n; D0 U* P! w' ]# |3 |8 ~    int area;//区域号
8 I2 ?' u& q. a* X    int per;//爱好度
public:
! x: {8 K# J1 n1 S    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
5 m0 }$ b+ [0 I3 x4 e5 @- c1 g. Z    int getclerk(){return clerk;}
    int getarea(){return area;}
    int getper(){return per;}
. d5 d, X/ D2 I* e% U: D- ?    void setclerk(int i){clerk=i;}
    void setper(int p){per=p;}
9 U1 D& v! [: s6 n" o; Z    void setarea(int a){area=a;}
, U! r! J6 r* H# c5 `};
7 Z% f$ a1 Y2 L% bclass area;
1 j: n+ r( p+ W5 U; Iclass clerk{
    int areanum;
    bool isin;
+ N: K2 P  D! C* a% `* W2 r    int inarea;
public:
1 g; U6 @5 j$ z    void set(int num){isin=true;inarea=num;};
2 p! \7 P: ?. T4 S    void setisin(bool b=true){isin=b;}
    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
4 f3 V: P; G, s$ V" Q& X& {};
; ~; q5 G% b# c- m4 Rclass area{
2 C0 R& r. |, u9 X! t3 o    int num;
! R/ j7 X* c$ ]: t: G- a2 A7 p1 h    int max_num;
public:
    friend void set(int);
/ ?+ J' m2 ]4 d, Z* _' k  h    int getnum(){return num;}
    void setnum(int number){num=number;}
# Z7 _: u+ M" |3 v2 i' i    int getmax_num(){return max_num;}
8 o; G& l" M( |, k) `6 f  V! E" [    area(int number=0){num=number;}
; \  g1 X9 y4 ~; @8 ^4 X! f0 H0 o    int getclerk(){return num;}
    void addclerk(int ps){num++;set(ps);}
1 {1 Y  e! |- U/ z4 d$ P* ]};
void getorderbyper(ifo array[]);
. k8 V: `) Z5 ~; Q5 K3 bint areanums;
void main(){
    //input
    cout<<"输入区域数：\n";
    int area_num;
# M7 x: C+ J4 d7 L    cin>>area_num;
    areanums=area_num;
* \5 Q6 p/ J$ l6 Z    cout<<"输入员工数：\n";
" r# Z' P/ j  c: Z" f& A: K    int c_num;
    cin>>c_num;
# S; r  h$ k2 N) d  E    cout<<"依次输入每个区域能容纳的员工数:\n";
    int *max=new int[area_num];
    int nownum=c_num;
( `5 R2 [# `* O* P( c    while(nownum){
        for(int i=0;i<area_num;i++)
        {cin>>max[i];nownum-=max[i];}
5 t' d% r9 C5 f: t. {+ C        if(nownum>0){
            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
            nownum=c_num;
4 u* ^7 |  I. n3 w) k: \/ ^0 T        }
        else nownum=0;
    }
    cout<<"按行输入每个员工的偏好：\n";
    ifo** per=new ifo*[c_num];
    for(int j=0;j<c_num;j++)
6 h" k8 v0 A" @3 s- c- |* E" T! f7 A4 n$ a        per[j]=new ifo[area_num];
2 U" J5 y# R. @3 _! f    srand(time(0));
% G* n  d& e! V5 p: O    for(int c=0;c<c_num;c++){
; j2 N( I6 t* z0 a1 g( C        for(int a=0;a<area_num;a++)/*
        {    int p;cin>>p;per[c][a].setper(p);
- _9 u; S5 k5 u7 g2 p9 G6 F            per[a][c].setarea(a);
            per[a][c].setclerk(c);
$ e7 p  S: z" n. I3 j0 e1 ~+ i        }
0 d7 L% C! u: [9 m( N        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
( T7 K7 s0 t3 M- Z' ^        {    per[c][a].setper((rand()%60)+40);
            cout<<per[c][a].getper()<<'\t';
7 k+ G( L1 ?+ \1 i% Q3 H        }//测试时懒得输入，故以60-100的随机数代替。
-    cout<<endl;
0 x: U% A, l* Z2 @0 F4 `$ O    }
    //output
        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
        clerk* people=new clerk[c_num];
3 Q0 G  r+ N0 [, r8 T        area*  areas=new area[area_num];
        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());
& \; X9 ?& E4 L3 _& e                people[i].setisin();
                int number=areas[per[i][j].getarea()].getnum();
! S& M6 H: Y1 i% M, `5 s' @' S, D                areas[per[i][j].getarea()].setnum(number);
                totalper+=per[i][j].getper();
                break;
            }
        }
        cout<<"能达到的最大喜好度为："<<totalper<<endl;
, c1 S$ |1 k& f9 l}
( u$ m( @1 f( Q% W! cvoid getorderbyper(ifo array[]){
8 F* F! d- h+ F; r    int max=0;
: P( F" L3 |, i! g( n9 ?3 z/ A    for(int i=1;i<areanums;i++){
% N' y7 }/ ^( s% L        for(int j=0;j<areanums-i;j++){
        if(array[i].getper()>array[max].getper()){
            max=i;}
% I2 a+ F" ?+ N' d$ k        }
& f6 @. q+ C3 L( n        ifo temp=array[max];
        array[max]=array[areanums-i];
        array[areanums-i]=temp;
        max=0;
* {/ z. C. w' @& A) h7 X    }
}

厚积薄发

代码3：
/*
3 v% E3 o' Y# }( ~) A算法思路：
3 ]' `5 W9 ~2 q/ Q" o（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
再加，该人的所有喜好度设为0，
（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
2 W, E- O1 C6 V（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
* O1 i- O. J! e5 ~. |3 p- A  X(4)最后输出总喜好度。
*/
4 G' E! }& U3 ]& h#include<iostream>
- [7 D9 i3 q+ C$ {using namespace std;
4 |  G8 h- c( I0 h; g( R; F" uint b[3][3];//M*N矩阵
* o- F, V$ t( ~5 x8 ]int a[3]; //区域人数上限数组
) V0 k( p4 b% g' mint c[3];
int temp[3];
int sum=0;
int max_num()
7 ?* R: a" S0 ], b4 w: ?{
2 T1 ]# {1 U5 ?6 G    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        if(max<b[i][j]&&b[i][j]>0)
. j, p5 @  t- t' }        {
$ G- t& l: t' R/ l) h3 p            max=b[i][j];
            x=i;
            y=j;

0 o& }# m5 D( Q; U        }
    }
   
$ D$ A: [) E) n) `6 Q% c2 e    if(a[y]>0)
$ b/ T6 s& z0 h$ @: h! [) j6 A: v2 [    {
        c[x]=y;
        //cout<<"c["<<x<<"]="<<c[x]<<endl;
        sum+=max;//总喜好度加上添加
& @0 F6 p1 [8 \1 ?4 y3 P        temp[x]=max;
        a[y]--;//区域上限人数-1
    }
( |. Z! O* o. H6 |" Y    for(int k=0;k<3;k++)
) ^0 J7 ~& S9 @, j; ]6 y6 C    {
( E8 q$ N2 j% h        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
: D, n3 m# ]9 q1 a* Z! |, f) s    }
    return sum;
}
int main()
{
4 r, j! V7 r* H% O) [   
/ D  d* a, m/ D, u0 }$ G7 W    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
% V. A0 p( z4 Z  q: u5 G$ ?% U9 _    {
        cin>>a[i];
/ X0 O% d5 \% n1 o    }
' A3 k$ w& Q+ |% ~' u8 m( ]    cout<<"input 3*3 actangle:"<<endl;
" n! \1 y% L2 U' m9 K( f/ t    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        cin>>b[i][j];
    }
    for(int k=0;k<3;k++)
    {
        max_num();
& O$ [# V  F6 h+ _6 U    }
    //cout<<"sum="<<sum<<endl;
1 u: q! i/ Z7 n    cout<<"sum=";
7 b! N7 M7 u9 c) \, s3 R' W    for(i=0;i<3;i++)
" r7 R; W9 d& Q* F6 X: T    {
        cout<<temp[i]<<"+";
    }
* h7 x0 [* A$ k7 a) @/ r& n: }    cout<<endl;
2 v3 F$ S. N0 Q& q( f. W    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
( x2 a, G# c; ?& [, B3 p: ~7 O' g+ m    {
3 m  L* Z7 ?  _' b' L        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
    }
    return 0;
}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
( a% Q; r# Z, f# \) U; t& t数学中国社区分享快乐！
2 |6 _  r9 C! }6 f

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！