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

厚积薄发

座位调整

  y# @6 ?- Q/ i2 V+ [) Y& X题目描述：
5 N. e' ?2 f7 X; m: i
' g9 o3 w% p4 O, Y; p+ P百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。

& Z# j  G+ y% t# t调整的方法如下：
; O' u$ \/ S6 A
! C* _$ E. u3 ?' i  A: F. g1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。
$ S2 }- w5 V' {
3 v1 @* s: v  F6 Y+ w2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。

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

数据输入：

第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。
8 y+ k  F1 `% |! S5 I
第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。
& F5 {. x& z8 H7 I
紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。
9 b! V+ f. R! [( h) g0 X' a( {8 Z* Z
答案输出：
1 p+ ]1 s6 ~. h8 o
对于每个测试数据，输出可以达到的最大的喜好程度。

" \: Y4 ^* w3 y) q# q7 |- o) [, Y- k输入样例

' A! [) ]2 j8 {& J, D
) Z7 L+ Y/ [7 A4 g3 3

1 1 1

100 50 25

5 v7 r/ R, ?. y* |  ]1 o- L100 50 25

$ |0 G) |8 \' x/ R: Z: Z100 50 25

$ t+ ?6 \4 G- ~- e  C
3 M6 T; X4 ]$ `9 i( I. w输出样例

6 D3 f* Y8 Q* z# \* o
175
8 x* ?6 W1 j* o, F& [' E9 N

- S4 c# B& P' r( b/ Z6 B5 i
8 h0 m, ^. H2 n6 b- Y数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175

厚积薄发

- D4 j) p2 `2 a, e$ v#include<iostream>
using namespace std;
- T: V. H, _$ a  |' P( ^6 N8 @) sint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
, _* K' x9 x* k0 R( Dint sum=0;
: _! D' n- k: F' V9 aint max_num()
8 m% w& j7 ^. N( u8 E/ w{
    int max=-32767;
    int x,y;
5 ^  S5 `9 r- _; M5 D- L    for(int i=0;i<3;i++)
0 L1 _% ]% O  E. F# }0 E; ]    for(int j=0;j<3;j++)
    {
: {5 t/ ]/ A& I  z        if(max<b[j])
7 ?/ h% G' g4 Q: ~        {
  J+ J4 W6 f+ D" k            max=b[j];
            x=i;
            y=j;

% ^$ G! y; K$ l6 A        }
    }
   
    if(a[y]>0)
    {
# {5 q$ i% V7 f% a/ E. d" F2 V' Z        c[x]=y;
* I' B/ e/ v% Q" E! ^        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
        {
( |% t6 \# ]$ K, r            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
; S, q- J5 q  j4 M# n3 _        }
, E% u4 _" s" k9 K# Z% e1 l9 d    }
* C5 S; A  I; z    else
    {
2 O$ Y' s) L% A        b[x][y]=0;
    }
   
: [# d( t0 Z8 r& R5 ~8 R    return sum;
9 B+ S$ ^  A8 g}
int main()
{
   
, e$ d0 g, f2 q" |2 C# J4 g( U/ T    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
; [% q: Z" l5 z: j/ @# q    {
        cin>>a;
    }
2 {9 h) f3 X1 g    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
# o' P3 }: x3 S        cin>>b[j];
- p: e- y! K- x" W5 o# o6 ~4 x& ~4 E$ A! l/ G    }
    for(int k=0;k<9;k++)
    {
! V/ S8 G6 T% H2 c9 c7 ^! Z( Z        max_num();
    }
$ g% s& F& p/ h+ @$ @" m1 w   
    cout<<"sum="<<sum<<endl;
" ?6 U8 q7 c' M( w    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
: v/ \# b" ?8 O- h    {
3 d7 }: N- ?/ q. T* l        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
    return 0;
# [- I; p. s/ g}#include<iostream>
using namespace std;
6 P( {  ]" [  `1 g7 V7 |int b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
; W# W5 _- |* cint c[3];//记录某人i去的区域j
4 @$ O0 y! X7 rint sum=0;
int max_num()
3 R4 z0 T" V) E% B! j{
    int max=-32767;
    int x,y;
# b' O0 L5 u. n1 s2 ^  b/ b0 r    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
; q: B2 ]7 T1 n    {
        if(max<b[j])
        {
  ^. s8 g5 q4 K$ D9 R! M+ S7 J            max=b[j];
            x=i;
            y=j;

" L& y0 N9 T( [1 Z3 \& @* j+ F5 r' R        }
    }
   
; x! y4 N3 E8 h$ ]    if(a[y]>0)
# F/ A) Z- f  S6 }4 K    {
" i; n2 f& w+ A; l! k        c[x]=y;
  j3 ^* `: Z' |& }+ ?2 ~        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
& e, }1 H3 d4 r2 g8 E: r        for(int k=0;k<3;k++)
        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
% Q/ U+ n* J' m# I; U        }
    }
    else
    {
        b[x][y]=0;
    }
3 p9 b3 M/ G, B9 l8 z: t   
8 p( S4 O% o' L    return sum;
! _/ ?. \. @. K}
int main()
{
' j% S3 ?; `  {7 S) s   
; M  Y& d& i2 v    cout<<"input 3 zone's limit:"<<endl;
# l* ~9 Q1 o( t7 c; _- U    for(int i=0;i<3;i++)
    {
6 N) {( C$ r  d/ d+ W8 Z        cin>>a;
    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
* Y% `5 c1 d+ K& o, ^3 B7 y    for(int j=0;j<3;j++)
    {
3 d* {" H; W6 T4 s7 S& T4 R4 T) o        cin>>b[j];
5 E) H7 k- N: A' ?6 r" a- J    }
    for(int k=0;k<9;k++)
! g# v' u1 y0 i    {
        max_num();
- ?2 n+ ?$ n% T( k& U4 [; [8 c! f8 G    }
   
7 O/ {3 A" v3 w    cout<<"sum="<<sum<<endl;
    cout<<endl;
    cout<<"reslut:"<<endl;
% ]% B3 F. k* g3 G. K* A    for(i=0;i<3;i++)
+ q4 |: a& t5 @: x( A+ n- o! g" r    {
" l; f& Z: h  M. ?! m( V        cout<<"people "<<i<<" go to zone "<<c<<endl;
+ Z; \# R% K& t    }
    return 0;
}

厚积薄发

编程代码二：
#include<iostream>
) W: P+ T; v! g% Q& M6 z& }#include<cstring>
  h% \. O! F8 O# Z  W- n#include<ctime>
: i1 _/ _; ]. l+ ~using namespace std;
1 a, g0 [+ c% ]; k* U+ Z* H- f# Mclass ifo{//矩阵的元素
    int clerk;//员工号
! @( {4 `. {; S    int area;//区域号
; O" {. ^5 `) H# J: @7 [+ c1 Z    int per;//爱好度
" t( [4 K9 @+ r3 D8 W# S: A9 epublic:
    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
    int getclerk(){return clerk;}
( z" ]! A2 R, `  ]/ O  Y& }    int getarea(){return area;}
    int getper(){return per;}
: l8 d/ e, z# Q0 U2 X# a    void setclerk(int i){clerk=i;}
    void setper(int p){per=p;}
( E$ U9 u' d" h0 i* B: f    void setarea(int a){area=a;}
};
class area;
, Y3 v2 N9 I7 e1 Zclass clerk{
( t! z2 q. q  C, \    int areanum;
+ Z: a& D3 K' T3 C! ?1 W7 Q    bool isin;
; O$ Y2 E1 u: d    int inarea;
( h% W' E5 m, vpublic:
2 g8 h. N" Y2 b6 Z6 V  t, Z    void set(int num){isin=true;inarea=num;};
    void setisin(bool b=true){isin=b;}
& s0 {& }5 q8 Y& \: |    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
};
4 y4 p0 c8 |8 l  Cclass area{
    int num;
) b9 O+ V3 F9 h- ]1 r2 B$ q    int max_num;
( o8 ?+ t- f) q" W4 U* npublic:
* M8 T/ |8 k" P3 C8 O- i    friend void set(int);
% p! P8 G9 S% z8 s    int getnum(){return num;}
  ?4 R  E5 I) V6 u7 Z2 S  y    void setnum(int number){num=number;}
    int getmax_num(){return max_num;}
# U8 R+ w" d, ^1 p    area(int number=0){num=number;}
" `* C/ G/ s2 x' Y2 ^    int getclerk(){return num;}
    void addclerk(int ps){num++;set(ps);}
) D9 K' L; `7 E& U};
, f  H4 D" n1 d3 u; wvoid getorderbyper(ifo array[]);
7 w* _/ ?! `" n& O+ Hint areanums;
! k4 @8 l. l! j2 Y* W3 E0 Hvoid main(){
( T; B( [: G0 D" u5 s    //input
    cout<<"输入区域数：\n";
    int area_num;
    cin>>area_num;
    areanums=area_num;
. X# a* R! b4 G# _5 X$ C    cout<<"输入员工数：\n";
    int c_num;
    cin>>c_num;
$ Z$ [7 a! h" H9 \. {    cout<<"依次输入每个区域能容纳的员工数:\n";
! X9 t1 I- k- f+ l5 k, G2 E    int *max=new int[area_num];
0 B+ P+ o  c- |: Z& K# l    int nownum=c_num;
    while(nownum){
        for(int i=0;i<area_num;i++)
        {cin>>max[i];nownum-=max[i];}
. `4 F' Q0 i/ S( W) b        if(nownum>0){
0 x- B! |9 E% s0 k4 j5 S            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
            nownum=c_num;
7 ~8 e0 x4 ?  ^: m        }
        else nownum=0;
    }
4 B/ y# j3 i$ X5 e    cout<<"按行输入每个员工的偏好：\n";
    ifo** per=new ifo*[c_num];
    for(int j=0;j<c_num;j++)
( H0 {' q0 m# r3 m- |        per[j]=new ifo[area_num];
6 U7 d5 V; [4 x1 R* g+ E    srand(time(0));
    for(int c=0;c<c_num;c++){
7 `" S. a7 q: |6 U! m# S8 G3 S2 _        for(int a=0;a<area_num;a++)/*
, u6 [0 o$ ?- W% V/ X- ?        {    int p;cin>>p;per[c][a].setper(p);
0 s9 k3 X/ T1 G0 n$ B1 [            per[a][c].setarea(a);
0 L* Q. d2 f! Q* y  X            per[a][c].setclerk(c);
$ [( m" ~" k% S# M, A+ n0 l8 ~        }
9 l; m9 M5 M/ s8 n! `0 H        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
        {    per[c][a].setper((rand()%60)+40);
* F/ \: i' g; b# [7 d            cout<<per[c][a].getper()<<'\t';
6 E) V% S( d1 y3 X" y2 q) Y        }//测试时懒得输入，故以60-100的随机数代替。
+ ?- f8 [' g4 O, x+ r, l-    cout<<endl;
6 l& [" N4 j/ b    }
! {/ O& M' @* d) _& a9 v    //output
        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
        clerk* people=new clerk[c_num];
        area*  areas=new area[area_num];
9 C1 F7 C5 `5 v" ~9 p3 m9 s0 i        int totalper=0;
6 N  |9 R+ Q' I/ D! P+ c1 e        for(i=0;i<c_num;i++){
9 p5 Q  G8 E5 U, C4 m, D! o: @            for(j=0;j<area_num;j++){
            if(areas[per[i][j].getarea()].getnum()<areas[per[i][j].getarea()].getmax_num())
; ~- N4 g- ?; C3 U# e: n                people[i].set(per[i][j].getarea());
; ]- q8 m3 ^& l                people[i].setisin();
                int number=areas[per[i][j].getarea()].getnum();
- w# `; [9 F! u6 @: {, B                areas[per[i][j].getarea()].setnum(number);
. v) I  `5 {, i1 d                totalper+=per[i][j].getper();
                break;
) u" D! L6 q5 B0 {) H            }
2 ~) Q4 X/ |) ^        }
% u! S2 }6 ]3 z! S# E3 p0 z5 b        cout<<"能达到的最大喜好度为："<<totalper<<endl;
+ z/ ]  \! R9 r+ b}
- p3 a! \$ D  e- H, avoid getorderbyper(ifo array[]){
    int max=0;
    for(int i=1;i<areanums;i++){
5 g) A. D, U4 T8 `$ X% |- O, P        for(int j=0;j<areanums-i;j++){
* T7 S9 s5 o# z2 d& z1 |        if(array[i].getper()>array[max].getper()){
            max=i;}
        }
& q7 _. a; G$ T8 ]' |8 |. s        ifo temp=array[max];
2 S) F9 m$ q  y# d8 T2 a% w        array[max]=array[areanums-i];
        array[areanums-i]=temp;
! a( H* x+ \& J& D        max=0;
7 g8 j- r( ^6 M) L    }
+ a: h- K1 L, F2 D/ [3 _8 J}

厚积薄发

代码3：
/*
3 Y% k1 M2 u4 A$ j* ?6 l+ |; C% P算法思路：
1 p4 Z# D$ g! B1 }7 I: {- G（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
& d8 @' c1 k' U. h0 c再加，该人的所有喜好度设为0，
, V+ S# v# o9 p2 d. d（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
0 k8 V6 B5 y  m, r(4)最后输出总喜好度。
*/
#include<iostream>
9 N, V( J% F) ]2 gusing namespace std;
2 ?0 n4 C- n2 ?7 e/ Zint b[3][3];//M*N矩阵
5 e% u( F9 T' P7 f# `int a[3]; //区域人数上限数组
int c[3];
int temp[3];
6 v# p* d, {* Z' C: T+ dint sum=0;
int max_num()
{
    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
' h: r5 z1 L7 o8 S$ F  Q- @& G0 i    for(int j=0;j<3;j++)
9 R# @# j4 J# v2 p! n' A, ~7 b    {
( s$ r/ i, q5 t4 ~6 C$ s' L        if(max<b[i][j]&&b[i][j]>0)
        {
4 e" D5 M6 N! J9 S7 K            max=b[i][j];
            x=i;
            y=j;
  K) M0 ~+ x1 q; p8 f1 G7 D
: s% y! I5 Z3 L0 a. \5 ^2 N+ E: A7 J        }
2 W) J4 x2 Q/ \! x    }
   
1 O; a7 M% t/ H2 C, u4 w6 W) u    if(a[y]>0)
- G3 D" L6 L/ c, Y    {
2 |3 k7 e7 ]# ~+ n: S        c[x]=y;
        //cout<<"c["<<x<<"]="<<c[x]<<endl;
        sum+=max;//总喜好度加上添加
8 G( U0 n# S( m        temp[x]=max;
2 X5 Q3 [4 [7 Z/ \( |+ S1 l' Y        a[y]--;//区域上限人数-1
    }
    for(int k=0;k<3;k++)
. }: }. p$ Y) E& C0 R    {
. `4 T' z: m& m5 I/ p1 `        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
    }
2 Z4 y4 P3 L3 a. D    return sum;
$ n) C  Q0 {* T3 }9 T* V}
int main()
3 l  ~4 R5 s  Y! y+ x{
   
    cout<<"input 3 zone's limit:"<<endl;
$ I" T! X9 D9 J8 K7 R; X7 v3 ~& |    for(int i=0;i<3;i++)
    {
        cin>>a[i];
( a4 F& x. m7 a4 b1 I/ _    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
/ h8 t+ x) \' _& C0 n8 o+ d% Z    for(int j=0;j<3;j++)
2 U  K, ^- |$ G/ O: U5 p    {
2 W) J" e3 R8 i8 N: f: a        cin>>b[i][j];
* v& `8 u* ?- N, T9 h( l* i0 N; ^1 V    }
$ g1 _" E' n  D" U0 L5 Y" ]7 }    for(int k=0;k<3;k++)
    {
        max_num();
    }
- \4 M/ l) s" b$ j    //cout<<"sum="<<sum<<endl;
    cout<<"sum=";
, H/ o/ O. [* q( X- h  _- `! i. k    for(i=0;i<3;i++)
    {
        cout<<temp[i]<<"+";
    }
    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
# p- a3 M) K+ `8 o. p) }    {
# }8 V/ Y' b+ k% g* X- N9 m5 U0 F        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
. @& s/ v% c" ]& d    }
  N+ o/ ]7 V3 Q    return 0;
}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
+ @0 `  z( \* a0 \( M数学中国社区分享快乐！
) ~4 S. E# Y. ]4 p5 N% O  H

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.
5 V) {7 D) u1 K8 U

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！