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

厚积薄发

座位调整

题目描述：

! s- u- [! |, U百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。

调整的方法如下：
$ Y* t/ i! C' C/ A3 T1 B( j
0 D- e3 V$ p+ Y% C/ V1 ． 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。
9 q* _0 n: U9 S! I" r5 l8 T
* x: ^' X& t8 N% D  F2 ． 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 — 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。

3 ． 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。

数据输入：

第一行包含两个整数 N ， M ，（ 1<=N ， M<=300 ）。分别表示 N 个区域和 M 个员工。
$ F1 w7 U4 |  W2 C4 x7 v  x) s* R
第二行是 N 个整数构成的数列 a ，其中 a 表示第 i 个区域可以容纳的员工数， (1<=a<=M ， a[1]+a[2]+..+a[N]=M) 。
. K$ U8 m! b! j2 z) _% u
紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。

6 k0 [7 Z+ o+ X* V3 |& y. c答案输出：
) B* z7 _. c5 \3 u" y0 C
$ L& Z) j: r0 [9 j, m* u对于每个测试数据，输出可以达到的最大的喜好程度。

1 b& d* J! q2 z输入样例

3 3
0 n' ?, z  E% {: {% N7 U! h
# F5 Q, @1 w$ Y: y1 1 1

$ ^. B, ?! d* M0 a100 50 25
& K7 C: `! l1 e/ l' Z( u  t8 A4 o
; o( ?/ d+ G% n) R( ]) L100 50 25
$ k3 g4 v6 l' E, ~7 W- p
100 50 25
+ C: d% I3 W4 m1 S

  v( X9 m+ g( O/ Z- }# y) I输出样例

2 @! ^5 D$ W/ z2 x175

" l4 ]0 B  H- {- F% _% q

1 r; x* C% r3 A3 k# |) V7 }% X
数据解释：此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为 100+50+25=175

hbdkfk2

看不懂！！

久玖九王

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

schnee

必须顶！！！

ehi28

嗯,不错,支持一下.
! T+ h$ a* f% X

_Amy_

程序最头疼

葉_浅浅

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

厚积薄发

代码3：
4 i2 {2 N) z8 [; f. n/*
算法思路：
（1）在输入的M*N矩阵中找出最大的一个数（喜好度）,然后试着把他加入到所喜好的区域中，该区域如果人数未满，则可以加入，如果满，说明不能
) l5 X) Z$ P6 @+ Y* a* _再加，该人的所有喜好度设为0，
（2）在后来的矩阵中找出最大的一个数，同（1）一样进行操作
/ Z( X, M! r/ T4 @( b7 d（3）设置一个求总喜好度的变量sum，每加入一个喜好数，进行sum+=喜好度;
2 c+ c4 C4 f6 a, q(4)最后输出总喜好度。
9 i3 y! \( X/ P% L  s*/
2 X% S9 B4 Y; Y( m$ x) `#include<iostream>
2 v& V2 ?% z8 r: S6 C0 K( zusing namespace std;
6 [/ b3 P8 W! C' e9 W( Oint b[3][3];//M*N矩阵
int a[3]; //区域人数上限数组
int c[3];
int temp[3];
$ `( b  s) h5 f! Z% W) B  i' Cint sum=0;
int max_num()
{
# b! s% E5 _" R9 d& p4 y# {    int max=-32767;
    int x,y;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
) Y, j' L; p6 z0 M! P% F    {
, v$ I0 }- G1 A        if(max<b[i][j]&&b[i][j]>0)
' M3 F7 V; x, s        {
            max=b[i][j];
9 U2 `: h; j1 U: i$ U7 e! |            x=i;
# a) \* ^. i) t/ Z( a  E' @4 J+ f            y=j;
; a, ^( g2 }9 a0 b
        }
    }
   
    if(a[y]>0)
    {
2 V9 e8 S! h3 }% ?        c[x]=y;
$ c/ t7 |% ?9 c3 C: Z, W  P( b/ w        //cout<<"c["<<x<<"]="<<c[x]<<endl;
9 i$ Z4 K2 G; h2 [        sum+=max;//总喜好度加上添加
/ K/ s2 N+ y% f$ n        temp[x]=max;
        a[y]--;//区域上限人数-1
    }
    for(int k=0;k<3;k++)
    {
        b[x][k]=0;//设为0是因为以后这行的喜好度用不上了
3 `8 s5 h* ~# E( ~3 N8 s    }
# q7 k  c6 g7 x    return sum;
8 ~+ g6 F  x+ F, Y! \) x$ ]6 i}
# Q. J! R2 L* Y! G% y0 F3 Pint main()
2 R5 d% @# W7 u) N0 l& T. S2 |/ k: c* S{
6 e/ Y; C$ }6 Y' H& v3 S   
    cout<<"input 3 zone's limit:"<<endl;
% C# G& p2 _" ?; ~    for(int i=0;i<3;i++)
# E6 L! C8 f5 ^( E2 ?& _  h! f7 ^    {
2 ~! q( s0 G( T" R        cin>>a[i];
  Z8 E5 ~$ h2 f% ?' A    }
$ i: d/ U, N7 }7 d7 ]4 z" `" w    cout<<"input 3*3 actangle:"<<endl;
    for(i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
/ ^7 x3 G# R0 l; m# D        cin>>b[i][j];
9 I( o. s0 \* }8 `    }
( T- f5 l1 b+ a    for(int k=0;k<3;k++)
    {
        max_num();
  I# Z% s) @# u0 S" Y    }
4 @) W) L9 c6 }7 h( @    //cout<<"sum="<<sum<<endl;
) L5 v  {5 B0 y" ^" ], ~    cout<<"sum=";
7 H) c# V2 O& L7 U# }    for(i=0;i<3;i++)
    {
/ y' A% ]; l1 Q5 [; e  B        cout<<temp[i]<<"+";
    }
    cout<<endl;
    cout<<"reslut:"<<endl;
    for(i=0;i<3;i++)
    {
        cout<<"people "<<i<<" go to zone "<<c[i]<<endl;
    }
    return 0;
}