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

厚积薄发

座位调整
, h' [7 J5 ^9 J# n2 }' j
7 v7 Q  q% e7 s. s& S题目描述：

1 \* C" Z0 t0 y1 F0 @+ O百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。

调整的方法如下：
9 _, k; G* F$ V) x1 p
1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。

2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。

3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。
- E& }  j' a" K9 A: z' q) D
数据输入：

. W/ o2 U; r$ f' P第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。
) s" {/ W% ~5 R7 [2 G3 r
- e' r' Y9 J" x2 K$ L$ ]% o第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。

7 `2 B/ S# y3 z" R紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。
9 O8 q  W: x" Q) T$ Q* M4 O* T7 r
7 n2 T& g, f( {* v( z答案输出：

对于每个测试数据，输出可以达到的最大的喜好程度。

输入样例

3 k( h4 n9 o9 Z" R: ]
3 3
* {% g, D2 z8 j* h+ [
9 ]' p+ d' Y0 Q% z2 ?1 1 1

, h6 E% d8 R) A100 50 25

100 50 25
# N" Q( C- ]' R1 v8 q
100 50 25

0 L- S- p+ B; ~: `9 p' t
输出样例

0 Z$ D0 e/ E9 E0 V5 i( U6 x* F2 d1 u
7 z! r. v4 E& d* ?# `$ c175

) G( g8 m' H- h$ i  w

7 t5 u' h- i( U9 ?# {
数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175

厚积薄发

#include<iostream>
. U1 w* C  h1 ^  V+ ]% h& Wusing namespace std;
int b[3][3];//M*N矩阵
# o/ a* i. F6 r/ Iint a[3]; //区域人数上限数组
( Z3 c+ k( e! H3 aint c[3];//记录某人i去的区域j
& S; i- Y5 ^2 Zint sum=0;
( t  J& M& f  C; R( {int max_num()
  r" b' V2 U6 D7 l( i* j{
    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
/ E+ l1 H; ^& H9 T& Y5 @* g$ w# n    for(int j=0;j<3;j++)
    {
2 ]* G4 ~$ v% Y" P        if(max<b[j])
        {
& G) {: z/ V2 P" ?3 a4 V2 b            max=b[j];
            x=i;
            y=j;

        }
    }
   
    if(a[y]>0)
' G: X# k) E7 r  J/ D1 H  j    {
        c[x]=y;
+ V& S- i1 r$ m! }# g. R1 H; R        sum+=max;//总喜好度加上添加
        a[y]--;//区域上限人数-1
5 N& g8 ^; i0 f0 Z        for(int k=0;k<3;k++)
5 W( j5 E- j( i9 g, n        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
& P8 B6 ?2 z- @$ K/ f. p        }
    }
+ i5 ]! m; o2 ~3 V* c    else
    {
! [' w/ G6 v: O7 o        b[x][y]=0;
    }
   
3 g3 X  `( e  B7 E0 J    return sum;
# D& W" ~0 ?- d+ x) ^' e' g5 G+ {6 d}
7 O0 w0 J8 Y' a! sint main()
! {. w5 |' W. n{
   
* ?$ d+ l2 ^1 K* I. Y" t+ G0 e+ `    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
. _& C: O" D8 U* _+ C0 V3 f+ q    {
# G& K' ?% w" `% c        cin>>a;
% |9 F  J2 `3 |- `    }
    cout<<"input 3*3 actangle:"<<endl;
5 l/ E8 q  l0 y: |    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
# X" h3 l& {5 f" ~/ Y3 S( D        cin>>b[j];
5 c+ o& e* }/ S9 _7 O; B1 J- F    }
+ D1 @3 c3 Y& \    for(int k=0;k<9;k++)
( x5 b4 T' l6 _2 V6 ?. {    {
: K8 F+ x  s3 y+ Q$ F. @' O7 [7 w( `        max_num();
    }
: M7 G) `: a4 }   
    cout<<"sum="<<sum<<endl;
& v/ \9 ^% ^/ Q' n    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
/ g) b7 [% X4 G1 i3 l+ M: t        cout<<"people "<<i<<" go to zone "<<c<<endl;
0 T, {1 w# s0 O1 r9 K    }
: m, M4 w% V* ]4 t- ]! D    return 0;
}#include<iostream>
" B- n' a6 }6 v4 j1 x7 susing namespace std;
/ q+ i( k+ c. D# ]5 N& }' Hint b[3][3];//M*N矩阵
4 C% p/ G, o! G* e' Dint a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
int sum=0;
' q7 X1 l, @  P2 T7 V/ bint max_num()
* \3 G* B2 c: W7 _' c" v{
. p7 {" P- g; S    int max=-32767;
% M- C. ^4 u9 W/ Z/ o: ?- B: U) i( U    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
! J, b9 G) X! ]2 T7 N        if(max<b[j])
2 u9 Z* |/ r; g' [3 X& t- ~- {2 {" N        {
            max=b[j];
            x=i;
            y=j;
  e' y! ~' q1 a- C7 x4 C" \
        }
    }
   
    if(a[y]>0)
7 H" X, W: j+ l& w  A$ r8 o    {
        c[x]=y;
        sum+=max;//总喜好度加上添加
) W7 O0 l( U% l( d. R/ C$ S        a[y]--;//区域上限人数-1
0 a# y! D0 m& z6 h4 ]        for(int k=0;k<3;k++)
- K' X, K! x7 ?/ D  M        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
7 i& k: T5 K% a# d' K3 `+ J/ _) \) h        }
    }
! Q) _. A# v3 e  k3 w- `    else
    {
        b[x][y]=0;
    }
: f# u; F8 ?: g' u! j: E   
$ `% j' @2 @5 |! U: m    return sum;
3 K, I# q2 a; V. d}
int main()
{
   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
    {
* Q2 P# [# m4 S        cin>>a;
8 b' S7 Z+ E- {" b: V    }
/ [* C7 }8 o6 t. y2 N6 }, X; l5 ?    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        cin>>b[j];
    }
5 d/ n) z' p) t; C3 n4 N1 g    for(int k=0;k<9;k++)
    {
        max_num();
    }
& X! h, x; t, B7 {& g; [   
. b, l. F8 k7 q2 r5 V# E6 u    cout<<"sum="<<sum<<endl;
* ~; `5 W: n% W) w( w    cout<<endl;
" y7 e, c1 A9 M8 C8 U5 {, p( K    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
        cout<<"people "<<i<<" go to zone "<<c<<endl;
& I. ]/ b( E0 n! |; v    }
$ T! J' R2 w3 e  H" D3 ~    return 0;
}

厚积薄发

编程代码二：
#include<iostream>
#include<cstring>
0 _' X" m( K+ o) N4 W( k#include<ctime>
1 l  l  N. X7 Q" I/ Y$ Rusing namespace std;
4 Z+ T5 ?* c9 a% T& w. X4 B. e: Xclass ifo{//矩阵的元素
    int clerk;//员工号
# f. S( s, h2 ]% o6 G    int area;//区域号
, l* J0 U9 g  I9 C. u    int per;//爱好度
public:
    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
0 @" A+ G. q: P8 s    int getclerk(){return clerk;}
; r, x1 h) R8 G2 l: g! k- \    int getarea(){return area;}
# ?6 X, X7 s9 r: T5 A2 r    int getper(){return per;}
; I. ~6 S- u, J0 h7 l    void setclerk(int i){clerk=i;}
/ M) }5 u, d! G1 p# l; c% g    void setper(int p){per=p;}
    void setarea(int a){area=a;}
1 o! s0 U. E: x, y6 G" [};
4 j. e& }6 @$ {& M5 |class area;
. E' z5 Y  R8 R. Z+ H. e# eclass clerk{
$ \  t, J/ C' x9 a    int areanum;
    bool isin;
    int inarea;
% l: d+ g" O3 N% ypublic:
    void set(int num){isin=true;inarea=num;};
( y$ L& S# y+ Q+ n    void setisin(bool b=true){isin=b;}
+ c4 a4 b  j/ b* x    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
};
class area{
0 U  ?: N5 r- K6 f3 {! j    int num;
    int max_num;
1 ]& I# H& }& C2 Kpublic:
3 k4 g1 `0 N: F* o! B+ s    friend void set(int);
- P+ \  q: L6 M! U( N$ |    int getnum(){return num;}
4 H7 u; I" l$ X, g0 f! Z    void setnum(int number){num=number;}
    int getmax_num(){return max_num;}
' s& D3 w4 O# g  O, N1 l    area(int number=0){num=number;}
) I- |* j. u/ K+ @% d9 w    int getclerk(){return num;}
    void addclerk(int ps){num++;set(ps);}
};
void getorderbyper(ifo array[]);
9 z. Q2 z+ f2 T: i* dint areanums;
void main(){
    //input
    cout<<"输入区域数：\n";
: R! B0 x7 B1 \. f: H% S    int area_num;
3 ~+ l0 @: {; k& T- n: E    cin>>area_num;
    areanums=area_num;
2 I# y. F; g# a9 U    cout<<"输入员工数：\n";
- O9 Y" ~4 F& n8 P: o6 w    int c_num;
# s, F1 I! k- M5 P! R    cin>>c_num;
6 U6 M! K% J! ^    cout<<"依次输入每个区域能容纳的员工数:\n";
    int *max=new int[area_num];
    int nownum=c_num;
  A* p. L; u6 E1 R! m' c    while(nownum){
        for(int i=0;i<area_num;i++)
        {cin>>max[i];nownum-=max[i];}
        if(nownum>0){
6 v; N0 Z2 w. c$ z            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
! `& I( L! M& s% k            nownum=c_num;
- w8 z) Y9 H" d        }
  m& M8 B% C0 ~- x9 q7 A) y5 P        else nownum=0;
    }
    cout<<"按行输入每个员工的偏好：\n";
    ifo** per=new ifo*[c_num];
$ j3 l4 V  \+ O* ^- Z    for(int j=0;j<c_num;j++)
; @$ t4 J" Q  v- Y% M# A9 [9 ]# y        per[j]=new ifo[area_num];
    srand(time(0));
    for(int c=0;c<c_num;c++){
! u' I' ?( x& Q5 z6 c5 m1 v% G        for(int a=0;a<area_num;a++)/*
! d/ {; e, L! f' m& D        {    int p;cin>>p;per[c][a].setper(p);
: v5 f) R9 o. q            per[a][c].setarea(a);
/ p; d% v: d3 u7 o            per[a][c].setclerk(c);
        }
        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
        {    per[c][a].setper((rand()%60)+40);
5 k; c9 C- s; M5 J; g( Q7 ^, W! V4 }            cout<<per[c][a].getper()<<'\t';
        }//测试时懒得输入，故以60-100的随机数代替。
-    cout<<endl;
    }
. H4 g# L0 D, X) v    //output
        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
& G1 `, H7 C% w6 X9 D3 R' I        clerk* people=new clerk[c_num];
2 ]# c( U$ t# P, i% F        area*  areas=new area[area_num];
5 W$ g+ V) g2 a' l: B) m        int totalper=0;
1 ~% B' h! D3 A        for(i=0;i<c_num;i++){
, I0 }/ k- C/ z7 k; [" k            for(j=0;j<area_num;j++){
            if(areas[per[i][j].getarea()].getnum()<areas[per[i][j].getarea()].getmax_num())
6 b5 D6 n; f. r! S3 A+ n                people[i].set(per[i][j].getarea());
                people[i].setisin();
' K0 a) s0 l  S                int number=areas[per[i][j].getarea()].getnum();
                areas[per[i][j].getarea()].setnum(number);
; T6 ~; P: j) E( N; p6 |                totalper+=per[i][j].getper();
  M  z6 O/ Y, n                break;
            }
        }
6 G: I- t# Y7 n! F2 i) A% ?        cout<<"能达到的最大喜好度为："<<totalper<<endl;
% N* S1 L& i  d}
/ s. q7 d( g& }' cvoid getorderbyper(ifo array[]){
    int max=0;
    for(int i=1;i<areanums;i++){
. j3 H1 U$ m- a! P9 j( G        for(int j=0;j<areanums-i;j++){
" G/ w% u7 Z  P4 v& E( o        if(array[i].getper()>array[max].getper()){
            max=i;}
        }
        ifo temp=array[max];
, b5 |/ a) j: w! L        array[max]=array[areanums-i];
; t- D, f* x; }1 H& x5 g4 l        array[areanums-i]=temp;
        max=0;
& T0 h. k& w8 O  W4 \0 W    }
1 T" v& r* v( `$ f! q  T: E: J}

厚积薄发

代码3：
; F- v: Q+ X$ f5 A. l/*
算法思路：
9 h  S% k5 a* a$ i& ?" Y; O（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
再加，该人的所有喜好度设为0，
' \0 A' R! s6 n$ k9 ^（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
(4)最后输出总喜好度。
*/
#include<iostream>
using namespace std;
. }2 R" m5 ~1 ]3 N6 Fint b[3][3];//M*N矩阵
# `5 [) s: y% l' x' }2 J+ ~! T) Q. Zint a[3]; //区域人数上限数组
7 R% T- o. B: z( ]int c[3];
6 \8 x& X* f0 Aint temp[3];
int sum=0;
int max_num()
% @% N' G) k3 `( U( w( g{
- K4 H% a5 f7 n: N5 O# O/ R    int max=-32767;
    int x,y;
. u  C: D/ h' k    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
: x! G  q* q( L  o, u* X3 @    {
' d* p! `8 N+ a9 P  I        if(max<b[i][j]&&b[i][j]>0)
        {
            max=b[i][j];
            x=i;
3 y9 B+ F* W5 `            y=j;

        }
    }
   
% c- v  Q9 j6 e3 I    if(a[y]>0)
* z: m6 X5 i. M  X    {
5 A1 j& K0 F" K1 S        c[x]=y;
        //cout<<"c["<<x<<"]="<<c[x]<<endl;
% c2 S1 i' O, z6 `' j        sum+=max;//总喜好度加上添加
        temp[x]=max;
        a[y]--;//区域上限人数-1
    }
5 o9 j" i4 q- o  ?; {" n    for(int k=0;k<3;k++)
    {
. M& e$ ~! d; Q- c) N3 k, @$ B        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
    }
- o/ ]4 d& G  s' i" |8 Y    return sum;
) n  r; C% h; u* X: u. T# `2 ?}
int main()
{
9 t4 P. j; k" G9 c: Z   
1 }4 b  `( ~# G' B9 n    cout<<"input 3 zone's limit:"<<endl;
! p: w8 }6 L! K$ I# r0 e1 u    for(int i=0;i<3;i++)
    {
        cin>>a[i];
    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
" r2 b# i0 R$ a) u6 w" x  P5 ~, `. k    for(int j=0;j<3;j++)
    {
        cin>>b[i][j];
    }
    for(int k=0;k<3;k++)
    {
0 O% g1 P5 t/ w7 P        max_num();
    }
    //cout<<"sum="<<sum<<endl;
    cout<<"sum=";
    for(i=0;i<3;i++)
  f( K7 }9 t; S/ T    {
        cout<<temp[i]<<"+";
4 Q. T- c" q; d  A* s8 h    }
    cout<<endl;
    cout<<"reslut:"<<endl;
% j( [7 g& j9 [    for(i=0;i<3;i++)
    {
        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
4 O4 \9 c! L4 I) A0 O  c' I. M    }
    return 0;
}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
9 L7 U1 O) j: b4 _0 B数学中国社区分享快乐！

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.
  e2 @2 I: F6 t' Y! X+ P

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！