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

厚积薄发

座位调整
* v( a! A5 M" E9 W' S
题目描述：
/ S. F* z" B, [0 q
百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。

调整的方法如下：
  |1 {# K/ v0 \! j3 w
1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。

9 q- a" g# U& z1 Z1 _2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。

3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。
5 x$ Q2 f- `' i( I
& U1 G) A, p" M# q8 j数据输入：

第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。
& ]) j- E) Z( W- W* T& K
( j7 L& @' g- p# O第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。
2 U- T6 G% |: }" S/ R
紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。

答案输出：

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

" {, b& _& w- o) Z- J输入样例

+ {, r8 F! r/ j) ^+ [
3 3
+ q1 F6 v+ ]4 `' _
1 1 1
- ?! M+ ~. G; \% ?. s/ {8 H
100 50 25
, _  N3 E4 X( X/ O4 H$ V6 ^
# B1 q$ G9 i" d100 50 25
  w9 M- v& n0 ?5 c1 v3 u; t) c
100 50 25
9 M) ~0 |1 s  C+ s

- _0 x; e/ x) ]) l
输出样例

175
$ p( I; L9 i* k+ F& v1 q
: c- ]# Q. L" Z2 t, e! b: r; J! z7 U

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

厚积薄发

0 N* t2 w1 x. m( t5 J#include<iostream>
2 F: v3 Q% B9 N0 u* xusing namespace std;
- v" q5 v; H. E  |* hint b[3][3];//M*N矩阵
% I2 F3 t! x5 Y, Nint a[3]; //区域人数上限数组
int c[3];//记录某人i去的区域j
int sum=0;
int max_num()
{
    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        if(max<b[j])
7 Q* V) p* `0 j) K: ~4 w$ `        {
            max=b[j];
            x=i;
" @; J+ g# T$ d# z6 t            y=j;
0 Y' @- s9 _, Q* d' J( G
, m* T$ c' }) W6 ~: z( U        }
+ ]7 l  n& [1 G2 O1 E    }
% x2 T% k& t6 Z5 {# L: d   
    if(a[y]>0)
    {
        c[x]=y;
  c8 {4 M1 L# ^) q4 N6 ]/ a        sum+=max;//总喜好度加上添加
4 H3 Z+ i6 b$ \" I  N1 |        a[y]--;//区域上限人数-1
  m8 x2 W# Q5 \& L        for(int k=0;k<3;k++)
- v0 h! h; r, |        {
            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
        }
    }
. _) @5 z* ~/ y. X7 H6 E    else
    {
        b[x][y]=0;
    }
5 Q1 B  b% n& I: S; r" H   
. S$ y: p5 G" t& T' y' ^: u8 I    return sum;
5 W; P  f6 P" P6 E, P3 y/ s: O' x}
2 R- K7 J+ T; O( }int main()
{
0 U. ]1 U/ S9 f) o' |   
    cout<<"input 3 zone's limit:"<<endl;
0 ]. ^% J& M. L. \    for(int i=0;i<3;i++)
    {
9 M: _( m% o5 q( a+ x        cin>>a;
4 t7 M' h6 Y9 |' `! I. m    }
8 _. O# g* ^6 t. \0 o    cout<<"input 3*3 actangle:"<<endl;
2 x0 K2 \- `/ V% n6 M    for(i=0;i<3;i++)
3 [/ b  W% A1 S/ V, H    for(int j=0;j<3;j++)
    {
8 q8 V& A7 v& _  B4 u        cin>>b[j];
- E  T# N% j6 R& Y% ^/ v  E7 r/ G& g7 I    }
    for(int k=0;k<9;k++)
+ H  o9 u3 ^0 i4 r    {
        max_num();
    }
   
    cout<<"sum="<<sum<<endl;
    cout<<endl;
/ l* S& I, J: z    cout<<"reslut:"<<endl;
- ?( w, m  Z* J    for(i=0;i<3;i++)
- M0 _: L3 K: F1 z" K    {
* K  M. z" L# M5 j        cout<<"people "<<i<<" go to zone "<<c<<endl;
    }
    return 0;
}#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
5 X. L2 A& R/ b* ^; u: ~; ^# W6 _# Uint a[3]; //区域人数上限数组
. E" O$ r. ?; Cint c[3];//记录某人i去的区域j
int sum=0;
$ }, L6 q0 j. s' Uint max_num()
$ ?; M/ }' M1 M5 ^{
    int max=-32767;
    int x,y;
+ }; C5 T6 E& |# `    for(int i=0;i<3;i++)
8 {- D; G1 G) f  G    for(int j=0;j<3;j++)
: b( t; \6 ?8 A- A: c, R    {
        if(max<b[j])
2 H! k" i" _- Z* K+ ~        {
7 n7 m/ ~' N5 Y! V2 ]% @& Z% \5 M- i% S            max=b[j];
            x=i;
9 y; R6 c+ n' C8 j            y=j;
. Z8 [  l4 l% }6 r& F
5 B- z& z) w- @9 @2 ^0 i$ h( j* ?; D        }
    }
   
  W* g/ ?. X+ b* Y    if(a[y]>0)
    {
7 Y1 j" o* e  G: d9 s' H* {. u        c[x]=y;
        sum+=max;//总喜好度加上添加
" T' V" i. K) D4 F* {        a[y]--;//区域上限人数-1
        for(int k=0;k<3;k++)
% K9 L' D( I! ?1 {        {
- M8 m4 r* P6 l            b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
' h9 ]" o  Y3 `( Q. V! ^0 ~        }
: I3 |9 j; L! \9 K+ T7 C: j5 E3 P0 j    }
    else
    {
        b[x][y]=0;
    }
( Y* U' ?1 K# T   
    return sum;
8 k6 `) N. d$ M6 Z( [}
int main()
{
   
: M( m( E; d3 u+ ]    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
% D# P3 A4 Z: X: h, o    {
& D: y" y- B) @# D        cin>>a;
    }
5 i& K0 P0 l5 V2 o8 b* X* w2 g    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        cin>>b[j];
2 d- G% D8 |7 ?  k1 p; Y7 n6 V    }
: p0 s  v( c3 G) v+ _9 V2 z    for(int k=0;k<9;k++)
    {
% P0 X; {- D5 x0 o        max_num();
: o* `. q6 f7 j, p4 z    }
" V+ m& g$ V* `9 M   
4 J6 o3 M! n$ c; s    cout<<"sum="<<sum<<endl;
    cout<<endl;
( [! ?6 i) P  H' u/ ]    cout<<"reslut:"<<endl;
$ r: }# ?& h! c0 f    for(i=0;i<3;i++)
  W5 h1 U: Q. u* f    {
2 Q- O' K" C  Q$ k% d/ A1 {        cout<<"people "<<i<<" go to zone "<<c<<endl;
/ u% d; e) e/ c    }
1 g! C$ N2 [1 \( B/ ~; G    return 0;
$ j1 Q# B7 ^) |  b5 l- ?) V, i) D}

厚积薄发

编程代码二：
" m7 j) U# ], `1 v#include<iostream>
#include<cstring>
#include<ctime>
2 _5 [& G' W6 vusing namespace std;
class ifo{//矩阵的元素
/ N( z3 `8 E# `( `: B    int clerk;//员工号
    int area;//区域号
    int per;//爱好度
4 c8 \+ N7 [8 J8 s6 U) k7 U- cpublic:
    ifo(int c=0,int a=0,int p=0){clerk=c;area=a;per=p;}
3 k: y9 t* S* Z    int getclerk(){return clerk;}
    int getarea(){return area;}
! y1 B' |+ i. V7 C' j    int getper(){return per;}
: e1 i; j: J( l6 d/ R    void setclerk(int i){clerk=i;}
    void setper(int p){per=p;}
5 e1 A7 \& s0 d) C" a+ b, G    void setarea(int a){area=a;}
};
class area;
5 S. E. Y( _* U. D% Gclass clerk{
; d! R# q& z/ o( m    int areanum;
    bool isin;
    int inarea;
. O. w. P) C) F+ mpublic:
    void set(int num){isin=true;inarea=num;};
    void setisin(bool b=true){isin=b;}
' i" {0 ^0 V0 N    clerk(int a=0,bool is=false,int in=0){areanum=a;isin=is;in=0;}
/ P0 e2 p! v1 `7 S% L  E0 e};
4 O; p- F" w: M4 ?1 v# R9 zclass area{
7 X+ x  |& E- F, {1 x    int num;
- h& j6 S* E$ G7 d  {! A7 q    int max_num;
( ]2 P5 ]2 P3 Q# t. ]$ `public:
    friend void set(int);
    int getnum(){return num;}
/ ]6 s# z9 Y' |6 }' ?: Q% _* G    void setnum(int number){num=number;}
7 w& `2 Y2 |& H9 `# C' W& Q    int getmax_num(){return max_num;}
    area(int number=0){num=number;}
    int getclerk(){return num;}
    void addclerk(int ps){num++;set(ps);}
8 r1 p+ z( g* u( l- I6 F- p; M& w3 s};
void getorderbyper(ifo array[]);
int areanums;
void main(){
    //input
    cout<<"输入区域数：\n";
" L; s; Y2 _- ~+ q8 O    int area_num;
: @6 G: w4 g* F3 Q8 Q    cin>>area_num;
+ n$ t; @% C. Q1 G    areanums=area_num;
    cout<<"输入员工数：\n";
: h* k% ~6 k) E    int c_num;
    cin>>c_num;
    cout<<"依次输入每个区域能容纳的员工数:\n";
( x6 r0 u% j6 C9 Y    int *max=new int[area_num];
6 f* t/ H; d; c5 n5 q5 m8 w6 y    int nownum=c_num;
    while(nownum){
7 b) a! \8 @: `9 J, K        for(int i=0;i<area_num;i++)
6 @7 e' ]; l6 f3 Y" H1 M5 _        {cin>>max[i];nownum-=max[i];}
8 x: n) ?6 G' K5 j- f/ d        if(nownum>0){
+ t0 w: N" H$ [: a+ i' L            cout<<"有的人没地方去咯!请检查是否有输入错误。重新输入：\n";
            nownum=c_num;
' y, s( i. L# _" ~  ~: `& B+ K% Y        }
5 _+ x1 }1 y* ~        else nownum=0;
    }
8 n) M" b: c, f! R+ ]    cout<<"按行输入每个员工的偏好：\n";
    ifo** per=new ifo*[c_num];
# q. a9 p  l) d  Y0 `; E    for(int j=0;j<c_num;j++)
9 W) R. D# Q2 V, ~6 K* x" q0 j        per[j]=new ifo[area_num];
* ?' h& k: R0 @( v' h" w    srand(time(0));
    for(int c=0;c<c_num;c++){
        for(int a=0;a<area_num;a++)/*
  R1 {$ ~/ o0 p2 s% n        {    int p;cin>>p;per[c][a].setper(p);
" M/ U; h+ w; V1 P( s1 }            per[a][c].setarea(a);
- T0 Q) M4 V1 p            per[a][c].setclerk(c);
! y2 m( W# [6 i' l        }
% s. e4 O' |$ O, [2 e        cout<<"现在是输入第"<<c+1<<"个员工的偏好度：";*/
0 b. S% |5 _5 l: P) h        {    per[c][a].setper((rand()%60)+40);
            cout<<per[c][a].getper()<<'\t';
2 e4 N: ?% G5 U: }) X        }//测试时懒得输入，故以60-100的随机数代替。
-    cout<<endl;
( h, t% m7 z  B) m; d    }
( D# K# |4 E* z( Y) D; S    //output
) j( M2 }3 q5 r/ @        for(int i=0;i<c_num;i++)getorderbyper(per[i]);//将每个人的喜好排序
        clerk* people=new clerk[c_num];
; m' {$ V# I8 M/ Z& C. Z6 s% ^" z( n$ F9 Q        area*  areas=new area[area_num];
8 c+ U8 ]! W7 i        int totalper=0;
        for(i=0;i<c_num;i++){
5 u) Q5 {5 c* x1 n) a3 f/ u            for(j=0;j<area_num;j++){
8 B; I5 m0 C7 R; y. d& u' w            if(areas[per[i][j].getarea()].getnum()<areas[per[i][j].getarea()].getmax_num())
                people[i].set(per[i][j].getarea());
% d5 }6 y- y# m- N* |1 k7 o3 R                people[i].setisin();
                int number=areas[per[i][j].getarea()].getnum();
9 P! h$ m' W6 Y8 m8 [                areas[per[i][j].getarea()].setnum(number);
7 H' _9 U4 n8 r9 [9 S& P/ C# m, J                totalper+=per[i][j].getper();
                break;
            }
* z+ j- |4 V- N) P        }
) ]1 \2 ?6 B( O. o" f9 \        cout<<"能达到的最大喜好度为："<<totalper<<endl;
}
' d, A, N6 ^' q; q' cvoid getorderbyper(ifo array[]){
1 h8 s4 A( T) Z& f    int max=0;
; @. u# j" D; L/ w    for(int i=1;i<areanums;i++){
/ T( e5 r# f, ]5 K4 K& e        for(int j=0;j<areanums-i;j++){
! n7 V5 ~5 m- H. q; O) i+ r4 w        if(array[i].getper()>array[max].getper()){
            max=i;}
        }
# ^8 P5 F' `: p% X# y! }        ifo temp=array[max];
        array[max]=array[areanums-i];
        array[areanums-i]=temp;
8 e. q2 H% a. b* F/ Q        max=0;
    }
}

厚积薄发

代码3：
/*
算法思路：
$ x* z) o. y  S) _$ M/ s1 u) F（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
6 ]4 A$ V0 \4 V2 u2 z( M再加，该人的所有喜好度设为0，
（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
# |* K/ Z3 i7 u4 D6 l（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
(4)最后输出总喜好度。
*/
  p2 o1 i# T/ H. _9 e#include<iostream>
9 e7 H2 v5 Z" T5 R2 Uusing namespace std;
8 F; N$ R6 T. J, X3 q3 d8 q  Qint b[3][3];//M*N矩阵
7 c& a9 p7 U) u3 ^3 a9 wint a[3]; //区域人数上限数组
int c[3];
( j( t9 U6 q& k) |; l2 ]) @int temp[3];
4 A' i2 }; V) u; _: Mint sum=0;
5 i& L4 }2 u! F1 n- q% `int max_num()
{
    int max=-32767;
    int x,y;
* {- J5 I3 y* |: J. b    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        if(max<b[i][j]&&b[i][j]>0)
        {
            max=b[i][j];
            x=i;
3 E6 x% @% L( f% F* z: P            y=j;

        }
- H" i+ c2 ?: R: E, d2 _4 O    }
4 c* ]+ v; _2 `. g. S   
1 ^% F- |! `3 L, Q    if(a[y]>0)
    {
        c[x]=y;
        //cout<<"c["<<x<<"]="<<c[x]<<endl;
; c: I' F1 `* \: X& m4 N$ f        sum+=max;//总喜好度加上添加
$ ~% w8 R; ]6 m8 l& z1 ?        temp[x]=max;
8 E" F9 x( F, e        a[y]--;//区域上限人数-1
    }
    for(int k=0;k<3;k++)
    {
        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
. J- \5 M% F3 h: g# v    }
    return sum;
( r& ]; b& r, P, r' m9 b5 M}
int main()
{
$ t% J4 r$ Z8 k' U   
    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
0 G4 |& K3 s- X/ l7 ^    {
        cin>>a[i];
( ~/ }3 u$ _+ T0 _/ d- e- v    }
) m& a( f0 |5 X    cout<<"input 3*3 actangle:"<<endl;
* \' L2 B( M! u" W% Y8 S0 G    for(i=0;i<3;i++)
$ \( }9 r. J' g8 R& @    for(int j=0;j<3;j++)
    {
- P4 B" t7 l8 P, }# M9 j" w        cin>>b[i][j];
    }
# C" X, i0 e* n0 O% C    for(int k=0;k<3;k++)
    {
) @4 X2 R; w: O3 L) L  T% e3 i        max_num();
    }
. h# J# |7 D5 F2 k( ~    //cout<<"sum="<<sum<<endl;
    cout<<"sum=";
    for(i=0;i<3;i++)
( H8 I3 _8 u  F7 B    {
1 x1 w0 [5 ]% K% Z. e4 e        cout<<temp[i]<<"+";
! R# q$ j+ c4 v6 S2 }( Y5 D) s7 Z    }
    cout<<endl;
: A6 P4 e8 F( Z    cout<<"reslut:"<<endl;
) ^- F/ J9 o1 R( y4 B( p" X+ H0 t    for(i=0;i<3;i++)
0 T- N9 V) H0 R; o( h  s) u    {
# o7 @! i4 `2 L        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
$ T( v- r7 i; y( J    }
4 C3 }6 E& y0 z! D& z3 H: U# v$ h    return 0;
}

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
数学中国社区分享快乐！

_Amy_

程序最头疼

ehi28

嗯,不错,支持一下.

schnee

必须顶！！！

久玖九王

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

hbdkfk2

看不懂！！