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

厚积薄发

座位调整

3 k! p, ]/ W& A3 q- y% d题目描述：

2 H1 f# ^7 k8 w4 S百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。
% }2 \, @5 }4 e9 R
调整的方法如下：

- ~0 w) q: T, n) y1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。

% O; O8 G, O3 _" S9 G2 E* `" f2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。

3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。
0 Z1 ^! ^  C' I9 V
数据输入：

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

# ]+ M; e! s+ k6 Y' x第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。

# a+ K: m: g- F  M' T. M紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。
% b5 m2 s6 v* q- o: o  p
/ ], A1 m$ d6 z+ m; Y% ]答案输出：
/ q; V4 F7 b) \4 p& T
对于每个测试数据，输出可以达到的最大的喜好程度。

) i( T9 i6 g: E8 o! d3 U输入样例

; e& O8 u* Y3 ~' B7 y2 ?
3 3

+ Q: Q( X8 k1 [. X& p6 y1 1 1

100 50 25

100 50 25

4 h3 e, _4 u# W3 a100 50 25
. p: D; q5 [: r- ]9 F4 V

输出样例

175
2 s( l8 w1 @& z8 N2 L  v$ X) w0 s
% V# @) j# b  Y5 B5 r" {+ J

$ s5 |8 t: M& R2 ?) Z5 g! h
数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175

厚积薄发

' o0 |0 V1 W# n8 ]- K' C- R
#include<iostream>
% A( k( M* q/ ?/ Ausing namespace std;
3 v0 b% n& A% p$ u) Sint b[3][3];//M*N矩阵
1 ~# ^* W/ Y1 f; Z5 Mint a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
3 @6 f# i% t1 A8 g. H' ^# L* w9 ]int sum=0;
int max_num()
{
3 D! k4 M% [) N; `6 C6 {2 z    int max=-32767;
4 Z  e, ^; n( J3 x  L0 r    int x,y;
5 ~0 W, B+ t* v; y  ?    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        if(max<b[j])
5 X7 [8 n$ N( \( }  A* j% u        {
            max=b[j];
            x=i;
3 U) B' b# ^/ I; J            y=j;

. C3 f5 @' `) n" y# ~2 F$ s        }
6 }" T2 @% }( a- g# D5 F    }
: s: g7 U3 a8 m& `  r7 [2 G0 G+ I   
6 G' Z2 n5 x$ Z5 I$ D9 g    if(a[y]>0)
9 Q' L8 K: X: E, Y  v/ @( k& W    {
0 B. R8 q9 ?& z, I$ l7 W        c[x]=y;
        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
% i3 h7 B( V4 V4 Y( e( }5 p9 D- w) ^    }
    else
; N! \3 ^/ S. p: d- d" e- i    {
        b[x][y]=0;
4 I! k. F2 }. P    }
   
7 L, W. K4 j. C& V5 C7 w    return sum;
3 ?/ c* z0 p4 k0 E( k2 x9 G}
int main()
5 w! Q. O, S1 @# x. {* z7 l{
# V# U" k$ ~. E+ n" e8 b: B   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
    {
1 k, V; U. T: S, y. j3 e        cin>>a;
1 w1 \1 b3 Z. J, D& e' u, U% ?- m    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
# d. H# m1 E/ j    {
        cin>>b[j];
    }
- x9 O# C5 W. Y0 v! o+ Q    for(int k=0;k<9;k++)
8 n" ?8 k0 F  x  w/ r4 ?    {
& a$ M& |7 m% K( }; K        max_num();
    }
   
6 U+ A  H3 x  A    cout<<"sum="<<sum<<endl;
    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
1 U6 C) T6 m1 f- ~9 i) |3 c( ~    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
    return 0;
+ y# _) _+ K. X0 S# s% _2 {3 Y}#include<iostream>
( t, N* U, [- R: R" s! Ausing namespace std;
; t, q7 v7 e, Jint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
: u. P& P5 R# y% l- Z: Oint sum=0;
int max_num()
6 i9 z* l3 N$ T8 G& I, W7 T{
- n4 S9 d1 \$ B- ~    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
1 I% J  a5 l1 ?! u6 `    for(int j=0;j<3;j++)
    {
        if(max<b[j])
# t% V7 n' K1 v& M- h" f  i" p9 q  K" K* s        {
3 E5 l/ M9 p& W$ C& A            max=b[j];
4 i2 y; m/ n, T  l$ }$ [0 i            x=i;
            y=j;

0 ~/ v4 |8 k+ A0 ]        }
    }
   
    if(a[y]>0)
! z4 _/ \. A* N4 Q! u    {
        c[x]=y;
* W( P4 J6 ^. D" Q        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
9 p7 ^# I# l  i1 V) P- g        for(int k=0;k<3;k++)
        {
" \/ ~* k3 A4 e: }1 x! b            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
    }
" f: l" p+ F4 S1 y7 d% ]5 y$ ~- Q    else
    {
        b[x][y]=0;
    }
: o0 n4 `- I: z) |9 K   
    return sum;
}
int main()
{
   
    cout<<"input 3 zone's limit:"<<endl;
/ F) y) f4 k; t" i: a/ N    for(int i=0;i<3;i++)
    {
% R, H9 @) d! _        cin>>a;
; w, F+ _+ Y+ \3 F  p: P+ r    }
    cout<<"input 3*3 actangle:"<<endl;
4 ?; v. L& E' D+ c    for(i=0;i<3;i++)
/ a# X% t% X4 E" a" |    for(int j=0;j<3;j++)
/ m" Z- h% d2 @1 u, R    {
        cin>>b[j];
2 L& T- x; U4 ?: A5 D0 n    }
    for(int k=0;k<9;k++)
    {
        max_num();
; a! Q. z! H, p0 C: P% _6 J1 u: f    }
' W7 N+ C9 A! ?2 k4 @3 Q: _5 S9 ^" Z   
    cout<<"sum="<<sum<<endl;
    cout<<endl;
    cout<<"reslut:"<<endl;
% B1 P8 {& S) S9 Q* \1 O    for(i=0;i<3;i++)
. U. m! k& M' f! `  ?4 n; B    {
7 l" a0 E; x6 p( j/ \! N; _3 u        cout<<"people "<<i<<" go to zone "<<c<<endl;
( L& X+ q5 K) E, c" h    }
2 x$ K' X# R+ W    return 0;
3 M/ N5 d8 q# K/ G}

厚积薄发

编程代码二：
. i, B  b6 S: R9 B#include<iostream>
9 p+ E! O1 a; L* j9 V#include<cstring>
#include<ctime>
& p% m) y- w  s7 x- g( ?using namespace std;
class ifo{//矩阵的元素
3 E; u7 H- I/ p9 J% a2 F9 X' s    int clerk;//员工号
    int area;//区域号
; o  }) O+ H# _    int per;//爱好度
) X- g3 I) E# \9 O! E0 npublic:
    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
1 ?* [5 {3 n: v/ m4 v, y) ~    int getclerk(){return clerk;}
    int getarea(){return area;}
# J$ {6 W6 e  M/ a; y7 A( ]    int getper(){return per;}
3 r3 Z( ?" y! p: K7 w/ w  V    void setclerk(int i){clerk=i;}
# T  x5 b  [( _$ J* f: Z  I    void setper(int p){per=p;}
    void setarea(int a){area=a;}
};
class area;
& {4 U- o) u% s/ v: e* ~4 e  q( Aclass clerk{
    int areanum;
    bool isin;
    int inarea;
public:
2 `5 p6 m5 r* T* Z8 r( }  R/ A    void set(int num){isin=true;inarea=num;};
" ~0 f5 x* e) r2 \, z7 `    void setisin(bool b=true){isin=b;}
% q7 U: j; K) e  E8 t1 [0 K    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
% `7 \* ]& P% u/ n+ o};
4 ~% B( G6 A  C* Lclass area{
    int num;
    int max_num;
! l' c$ x, T( r  Apublic:
/ H8 _# P( F: T4 m, _$ ^    friend void set(int);
    int getnum(){return num;}
    void setnum(int number){num=number;}
    int getmax_num(){return max_num;}
    area(int number=0){num=number;}
9 D6 @  Q' y2 k7 g% u6 P" A    int getclerk(){return num;}
+ Z- V! W' }" I. A% _    void addclerk(int ps){num++;set(ps);}
3 `5 I% K. c4 |. w};
  N( P0 g9 u/ F  Xvoid getorderbyper(ifo array[]);
9 h5 [4 N. X! {; O+ V3 T" Zint areanums;
void main(){
    //input
    cout<<"输入区域数：\n";
. I5 j" N' G' z  c; H& a    int area_num;
% l6 g# `8 P5 g' ^    cin>>area_num;
9 k- W# T7 N9 p7 w! M    areanums=area_num;
    cout<<"输入员工数：\n";
    int c_num;
2 g$ H0 H4 n. ?/ c; U8 |    cin>>c_num;
    cout<<"依次输入每个区域能容纳的员工数:\n";
    int *max=new int[area_num];
    int nownum=c_num;
! o: ]6 l5 m  t8 q    while(nownum){
$ r+ h; E+ D4 @" C% r' h9 P        for(int i=0;i<area_num;i++)
4 L2 t; Q; G  i' R4 v  N6 `, u        {cin>>max[i];nownum-=max[i];}
) f' O+ M7 d- l0 n. e! T' {$ E- V# R4 [        if(nownum>0){
            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
6 o- K8 e& N+ P! i* C" j% f3 V            nownum=c_num;
        }
4 k( T3 ~$ Z! X. M. E& j# O        else nownum=0;
4 n3 a" c, H7 \  K; P3 [% x3 v    }
8 n6 Z" D, p: o; C    cout<<"按行输入每个员工的偏好：\n";
0 e5 W, S$ z" D    ifo** per=new ifo*[c_num];
4 j. p( [6 f# c! E    for(int j=0;j<c_num;j++)
( c, ?1 X& M; \+ ]0 N        per[j]=new ifo[area_num];
    srand(time(0));
* x0 l+ h4 w" ^" [8 @" o1 J    for(int c=0;c<c_num;c++){
        for(int a=0;a<area_num;a++)/*
$ U. j" R2 {1 b! `( N        {    int p;cin>>p;per[c][a].setper(p);
            per[a][c].setarea(a);
            per[a][c].setclerk(c);
4 I. M2 k3 y7 a0 c        }
0 Z: g$ Z' z+ X. M$ K0 ?        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
; Y, ]2 `' X; y% q. }, {        {    per[c][a].setper((rand()%60)+40);
            cout<<per[c][a].getper()<<'\t';
0 m1 o/ `- u+ j        }//测试时懒得输入，故以60-100的随机数代替。
3 J9 s% s" b& g6 X-    cout<<endl;
+ j+ \6 g; m. z! t, C, y  y* n- V4 f    }
    //output
        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
        clerk* people=new clerk[c_num];
) V3 t! j& N/ a        area*  areas=new area[area_num];
% y0 t3 D: x- J8 ^% A        int totalper=0;
5 u# ]; V- ~  J& i0 D* X        for(i=0;i<c_num;i++){
            for(j=0;j<area_num;j++){
. w( U8 O1 K3 `& L" p/ L            if(areas[per[i][j].getarea()].getnum()<areas[per[i][j].getarea()].getmax_num())
+ d7 i- k" O; t, b$ \8 y% ^                people[i].set(per[i][j].getarea());
6 v/ s+ [1 b: D. H                people[i].setisin();
2 [# U: b7 l% e: L7 c$ G                int number=areas[per[i][j].getarea()].getnum();
6 l) q* \1 x, n0 a2 v* B4 M2 u/ W) S                areas[per[i][j].getarea()].setnum(number);
: \( M" I/ f7 m                totalper+=per[i][j].getper();
+ Y  a/ B; \- N. G                break;
* f+ Z5 x/ r3 H            }
, Q; \' V. v) o" v+ O7 f6 A        }
        cout<<"能达到的最大喜好度为："<<totalper<<endl;
}
, a  E# X; t5 z. avoid getorderbyper(ifo array[]){
9 ^- F7 x. {7 a' k: R/ O% N9 p    int max=0;
4 ]( w. J; @. `    for(int i=1;i<areanums;i++){
        for(int j=0;j<areanums-i;j++){
        if(array[i].getper()>array[max].getper()){
            max=i;}
- e$ U( y5 D8 F8 T- V4 R( a        }
        ifo temp=array[max];
        array[max]=array[areanums-i];
% J! n$ i5 T" x8 p& k: ?. z9 s# b        array[areanums-i]=temp;
  _4 P3 U/ l! n        max=0;
$ R* c, a1 @# u+ Q* x$ t9 t    }
}

厚积薄发

代码3：
; Q: T& T' d7 u$ m5 u" y& ^# r/*
算法思路：
( U& Q+ N. ?! x$ g( d, V（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
再加，该人的所有喜好度设为0，
（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
' }( u9 r) D' s/ A9 f; _(4)最后输出总喜好度。
) R" K8 O) j8 W*/
#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
4 g! g' {' g0 L4 H! Iint a[3]; //区域人数上限数组
7 T/ k4 |* `# v& H. W- d# ?int c[3];
" O2 w" b+ W7 Q- L$ V: Y" o% Oint temp[3];
int sum=0;
int max_num()
+ W) ^) M! u8 U. i7 a% O- ~1 |{
+ R5 A' j9 I# `3 u    int max=-32767;
$ v; k9 ^7 P! y  _* B8 V5 |" C& N2 j, `    int x,y;
; C1 i2 ]$ r, L* Z  }9 _/ ^* @% b    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
5 [1 m$ ^2 R- a    {
        if(max<b[i][j]&&b[i][j]>0)
        {
1 ?* E  ?+ h& |+ ~; d/ r            max=b[i][j];
            x=i;
7 E. q! A, `0 ^: |0 r            y=j;

        }
5 q1 X3 [. C* w: ]% }( {    }
   
    if(a[y]>0)
7 n! U9 h3 T: W+ Q4 E    {
        c[x]=y;
        //cout<<"c["<<x<<"]="<<c[x]<<endl;
        sum+=max;//总喜好度加上添加
. E0 \. W$ }9 E- J2 M2 P        temp[x]=max;
        a[y]--;//区域上限人数-1
, E- ]4 o2 ?' V$ t+ e! {    }
    for(int k=0;k<3;k++)
    {
9 b5 k2 C4 \  v' Z        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
    }
  T& O' f  F/ h    return sum;
}
7 y: v& e5 s0 d: Q! S" g- K6 Lint main()
% Z' V3 X- X5 F* x8 z  m{
6 e" _9 C7 f+ I4 _* u! |% L   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
, [& s, F+ h9 _& ~7 O    {
        cin>>a[i];
" |: s' {! e# m4 O& m- e/ a7 u    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
; h+ m# w0 {$ i    for(int j=0;j<3;j++)
( k: r7 s: c( X0 o7 N    {
        cin>>b[i][j];
    }
    for(int k=0;k<3;k++)
3 l. c! M, I) a1 m& s) j% c    {
/ Y7 y  D- U" c2 B6 N9 ]        max_num();
. q' P5 b4 E& c" V  i6 V. @" e    }
    //cout<<"sum="<<sum<<endl;
2 j3 |3 X/ v3 K: I, ?# d( g: [    cout<<"sum=";
    for(i=0;i<3;i++)
6 w4 Y/ }2 u6 m/ V- i    {
( C& S8 v- Y; x( h+ d) g        cout<<temp[i]<<"+";
5 L' u& n$ w  E6 A1 y+ |0 z7 b    }
    cout<<endl;
7 _( Z7 n- O! Q% f4 w9 y5 G    cout<<"reslut:"<<endl;
& B6 a7 e3 A6 z) W    for(i=0;i<3;i++)
4 }8 E" b/ w" \6 e3 I$ N& s    {
        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
6 F& d( X! S, j" i8 S    }
    return 0;
2 R/ ?  x2 E. C2 s5 ]}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
3 i. r- M* ^. T, O; O5 |数学中国社区分享快乐！

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.
' X/ N& u6 ]$ f$ N

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！