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

厚积薄发

座位调整

题目描述：
- g8 m! J5 L- Y" p$ F
百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。
/ ^9 }( S7 q5 C7 M4 V0 x! q! |! M# \
调整的方法如下：

0 f/ L& k/ i6 i$ X7 R9 j- l1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。
( v; ?7 x. z: a  C  }9 R. \
  B$ T6 H( X) K! X% _4 F2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。

( m& c7 Y# u7 @( ^9 F* W3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。
  Y+ h# R- c! M, L( H
% F1 i/ j! v7 J6 }& Q数据输入：
7 w; ~3 m* l+ e, W
5 j" m3 b$ K2 o3 P3 n6 m第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。
; Z4 {  |) V& ^& {. R6 k
: T# j: B: ~; \) p第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。
' ?- v4 q: Y4 Q* E1 C* h) Q+ t, u6 S
紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。
( U% K/ O) A" w& k& ?0 _
6 {( M* ]5 p4 _: ~- u答案输出：

' ^6 N. I$ u- c' D对于每个测试数据，输出可以达到的最大的喜好程度。

5 ]9 J$ A# M4 [9 |* _输入样例

9 ^' X8 b7 y* V$ m% ^7 V3 [3 3
% I( Z- p. D- k) L! S
1 1 1
; H8 D' ~% n, t9 ^  L6 A
100 50 25
+ P- X, e7 N6 [; a6 Z0 J- J4 M
100 50 25
) l3 @( W; V- W6 u+ Z
100 50 25
" H( c# q8 u) L5 \

! p) o8 Q, |: C. u) a
% |% k+ h4 m3 i' |( o输出样例

175
2 r0 s7 x5 s9 C" c
& p6 B" E1 {$ z& B* M# A

  D% k& e1 s, ]0 I* o6 `
& q7 [* `# m7 C/ a5 [* u" T数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175

hbdkfk2

看不懂！！

久玖九王

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

schnee

必须顶！！！

ehi28

嗯,不错,支持一下.
6 V- c/ I. U2 K& D1 _  H( ^" y& m$ f* R

_Amy_

程序最头疼

葉_浅浅

其实我一直觉得楼主的品味不错！呵呵！
% d8 C: c' u/ c1 ]( _, c8 t, Z8 q, S数学中国社区分享快乐！

厚积薄发

代码3：
/*
算法思路：
（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
; x/ u& i( A. h1 z; D; ?$ o2 D- W再加，该人的所有喜好度设为0，
（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
(4)最后输出总喜好度。
4 z) m. Y: I2 q% R6 U& x*/
4 O; h; C" R. x% T#include<iostream>
using namespace std;
int b[3][3];//M*N矩阵
& N: U9 t3 G; C' s2 Hint a[3]; //区域人数上限数组
; Q6 R" @6 o7 z3 Z7 K; O- X2 @/ oint c[3];
int temp[3];
5 H7 U3 f$ ^" r; \7 _( ?; m5 bint sum=0;
% W+ W, }: |4 x9 y4 @" T7 x/ f0 pint max_num()
{
* J" j, r: t' Q: r    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
6 x6 A' C) k0 x        if(max<b[i][j]&&b[i][j]>0)
* m3 U* G. z* \+ N/ w& t        {
            max=b[i][j];
            x=i;
            y=j;
! ]+ u) E2 D* x
        }
, C) D# Y1 B: e. |3 X    }
   
    if(a[y]>0)
; F, V3 [/ A9 P5 Z% ~% |) d9 p5 E    {
; {1 I4 B8 J/ F4 u0 z        c[x]=y;
( }& g5 S+ {, |7 x( x7 o" E  Q  ?        //cout<<"c["<<x<<"]="<<c[x]<<endl;
        sum+=max;//总喜好度加上添加
        temp[x]=max;
8 x' {  c, `  X( I1 j! }# H; c7 \        a[y]--;//区域上限人数-1
" H* M4 A1 q) @: R  n! P    }
: x5 t4 E; B& P$ |0 I: o: D    for(int k=0;k<3;k++)
0 e# n' R) `4 y) O" y# R. @% l! E    {
        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
    }
    return sum;
+ S4 m+ [, k  h7 z}
int main()
{
   
0 Y4 D5 j- _/ C5 f" d    cout<<"input 3 zone's limit:"<<endl;
    for(int i=0;i<3;i++)
0 B, J7 Q+ B* e9 S" t    {
( i0 m4 q' I2 c8 y6 T        cin>>a[i];
    }
6 [0 ?* f0 \- ?4 ]! o& c    cout<<"input 3*3 actangle:"<<endl;
/ q% x9 G/ |. B& s! ~    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        cin>>b[i][j];
) n; s' I' c% A% Q7 e    }
* g8 k& c; m+ Y9 ?. v, k8 t    for(int k=0;k<3;k++)
: \+ B5 c9 Y, v5 {1 C    {
        max_num();
    }
& Y4 i& j! A( w) Y    //cout<<"sum="<<sum<<endl;
3 z: w/ d( b5 k: p4 x( x% N$ o7 O    cout<<"sum=";
    for(i=0;i<3;i++)
( A7 I) Q) U3 ^* u! Y    {
. M6 G) a$ [' H9 Z% n        cout<<temp[i]<<"+";
+ }- y0 a7 _" h, ^! z  {8 L4 v2 I- M    }
" e2 @3 r; W# ~  S$ a& M    cout<<endl;
; j- y+ [( B/ D) u4 u: h    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
" B* f% I8 g9 Q# L; _5 o    {
1 d9 Z' j8 b& [- M$ z        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
    }
    return 0;
  Z: p! Z' o7 k  a9 L0 F1 x}