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

厚积薄发

座位调整

! t$ f  Q0 @2 l! T1 o) S2 X题目描述：
+ o# p7 l* y% T( Z- n5 w* a
百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。

) a% ]( g  |, ^8 R( W调整的方法如下：
& K- V+ p) x7 }) N
! e9 O% m$ D2 S# ]- f) A8 w1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。
- c3 Z2 L* k6 _$ e5 S2 n
5 W* O) S- K* t5 Q2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。

3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。
6 N5 |7 ^  y& J4 f. y
+ j+ O% \& t8 \( x+ y# H& W6 X# i数据输入：

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

1 p; c! C5 x$ c/ S2 J3 g第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。
' K$ K  y$ v" ]3 z# l* ^: z% c( O6 j
紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。

答案输出：
" \. [0 D6 \" H' @* o$ B. l, e/ ^8 Q* w
5 H% @7 J$ ^' a( P5 R; `2 y对于每个测试数据，输出可以达到的最大的喜好程度。

输入样例

% f/ X% W2 b  s& V" e! S8 N3 3

1 1 1

! e% f2 N* p  E7 f# @) g100 50 25

100 50 25
0 B  s; A8 ^! H: T
100 50 25

% }  h. i0 O( J+ ]( |7 J) H  Z! n
输出样例

- y* _( \1 p2 z
+ V/ v9 M3 q3 U  x8 r7 J+ w3 J175

: O  l, j/ v4 Q1 Y0 \9 ~, ]+ Z
! l, H, I, J. w数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175

hbdkfk2

看不懂！！

久玖九王

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

schnee

必须顶！！！

ehi28

嗯,不错,支持一下.

_Amy_

程序最头疼

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
5 ~; v+ n) z0 \( ~4 K% I( P3 d! H数学中国社区分享快乐！

厚积薄发

代码3：
5 j7 D+ f5 g% O9 C( h* J3 I  L, o( z/*
# d/ a( Y8 |) V" V, K算法思路：
4 @, [) r; g/ W$ [' E( O（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
" g6 H, g7 b; t9 W$ _$ S再加，该人的所有喜好度设为0，
（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
(4)最后输出总喜好度。
*/
#include<iostream>
4 m& i1 O/ T' Zusing namespace std;
+ V( c, _8 ^1 w5 k+ h- Nint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];
" P& r2 q$ P7 h1 F: p. l7 v' W# oint temp[3];
int sum=0;
int max_num()
# }* W) U# R1 H{
* G& L2 l$ V/ }3 r  t1 z0 e, B1 |    int max=-32767;
2 z' c4 v' e7 D$ L    int x,y;
4 ^. }7 S, B6 k) B3 }: a4 Q    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
8 _: g2 l+ j- W1 C1 _    {
        if(max<b[i][j]&&b[i][j]>0)
) e( X! Z0 K; l+ n        {
            max=b[i][j];
% U9 N" V" T3 O9 R  A' p            x=i;
* @2 t6 S) O- K1 P1 U0 _. b            y=j;
3 a, p( \/ U5 v) k. L. v
( x8 f% O! v+ o3 P4 M        }
1 u( [. D) Y1 l9 R) U2 D    }
2 d: V. X( u5 r: Q   
: D+ w0 R" X' W! D6 o5 M! Q    if(a[y]>0)
    {
        c[x]=y;
        //cout<<"c["<<x<<"]="<<c[x]<<endl;
* Z/ v# [1 j5 P! O+ G. _        sum+=max;//总喜好度加上添加
, P* k) r' h! C3 }" |0 v3 n  k        temp[x]=max;
        a[y]--;//区域上限人数-1
! y# m8 l; }" Q) g. H# g    }
6 g1 I& \" X# l! _! B  h& U    for(int k=0;k<3;k++)
+ B" W, X  k" |" u2 u, V  c    {
        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
    }
    return sum;
}
7 a# I  n1 `( D! ~2 q9 qint main()
; i9 R4 Z4 \, P* o5 g1 {$ c  _{
   
) D4 S/ [/ Q1 q; v( }8 x# m    cout<<"input 3 zone's limit:"<<endl;
; X% L) I# Q' V  Z    for(int i=0;i<3;i++)
* D, @, Y0 \/ H% b3 y    {
# R+ E. h2 b0 {, ]! G- H' o        cin>>a[i];
    }
    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        cin>>b[i][j];
5 }2 m, `+ ]6 D0 T: G! I9 O) ?    }
    for(int k=0;k<3;k++)
    {
0 u2 R( S# u5 S) I4 }6 k+ R/ l        max_num();
% r& o2 u- |0 w2 o    }
    //cout<<"sum="<<sum<<endl;
9 W# r; ^5 i% H+ _) H, x$ m    cout<<"sum=";
6 z+ I1 u9 n1 O    for(i=0;i<3;i++)
    {
8 O& U4 T) ~4 f2 a  W/ J  f5 c$ R        cout<<temp[i]<<"+";
* d  B5 U  b$ t5 z+ ~, e, `    }
  u" w4 ~, w6 @" c- `    cout<<endl;
    cout<<"reslut:"<<endl;
) l$ ?3 q+ d. ]3 u1 v" c    for(i=0;i<3;i++)
' ^# K1 |- x; Z+ s& x  g    {
        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
    }
( a1 ^3 U  b0 q& q; t/ f: k    return 0;
}