QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 12414|回复: 1
打印 上一主题 下一主题

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

[复制链接]
字体大小: 正常 放大

1341

主题

738

听众

2万

积分

数学中国总编辑

  • TA的每日心情

    2016-11-18 10:46
  • 签到天数: 206 天

    [LV.7]常住居民III

    超级版主

    社区QQ达人 邮箱绑定达人 元老勋章 发帖功臣 新人进步奖 原创写作奖 最具活力勋章 风雨历程奖

    群组2011年第一期数学建模

    群组第一期sas基础实训课堂

    群组第二届数模基础实训

    群组2012第二期MCM/ICM优秀

    群组MCM优秀论文解析专题

    跳转到指定楼层
    1#
    发表于 2010-5-6 18:56 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta |邮箱已经成功绑定
    饭团的烦恼
    ' m& Z* e, i! R* g2 _( A# H1 q# g3 c; |: z
    “午餐饭团“是百度内部参与人数最多的民间组织。 7 b7 m) X/ r. u9 M2 v9 w
    + T0 K5 K$ k) y. o3 B
    同一个部门的,同一间大学的,同一年出生的,用同一种型号电脑的,员工们总是以各种理由,各种借口组织各种长久的,临时的饭团。
    4 w5 @; {& @2 U0 s+ v: O
    7 J; q' @- m+ q8 b% U. ~参加饭团,不仅可以以优惠的价格尝到更加丰富的菜式,还可以在吃饭的时候和同事们唠唠嗑,吹吹水,增进感情。
    6 c2 i9 ]6 j8 I1 q
    & D( \- B- u% X2 _; b# [但是,随着百度的员工越来越多,各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口,饭团的点菜负责人背负的责任越来越大。现在,这个重担落在百度之星的肩上,因为,你们将要为所有的百度饭团设计一个自动点菜的算法。
    . F- L, s& L7 n9 {
    ' L! v8 Z. g# g1 X! \饭团点菜的需求如下: ; |. l2 }& c6 v' U" G  ^

    & t6 w+ t3 ?; k5 O0 ?% b) S1 . 经济是我们要考虑的一个因素,既要充分利用百度员工的午餐补助,又不能铺张浪费。因此,我们希望最后的人均费用越接近 12 元越好。 2 q: a4 b' l3 ?: n( X

      [( {: p0 ^. i  }& k5 i, V1 y2 . 菜式丰富是我们要考虑的另一个因素。为简单起见,我们将各种菜肴的属性归结为荤菜,素菜,辛辣,清淡,并且每个菜只能点一次。 / n. u6 B1 w) v8 |

    ( o( [9 I& u# L  ]2 B3 . 请紧记,百度饭团在各大餐馆享受 8 折优惠。
    : k" C2 p# c% y5 I  ^1 |
    . H9 ~6 l7 g: T  B' @9 C+ d输入数据描述如下: * V  B; Z5 ?/ B2 N8 ]0 c
    3 @  T7 [$ i/ G, Y* j+ V+ \! Q
    第一行包含三个整数 N , M , K ( 0<N<=16 , 0<M<=N , 0<K<=12 ),分别表示菜单上菜的数目,饭团需要点的菜的数目,就餐的人数。 ( h  O" i; c. e

    4 ^1 Q0 ~9 C3 s& K2 J9 f1 V紧接着 N 行,每行的格式如下: 7 Y7 _& |) A1 G( L0 J2 H

    # {: ~. W: R5 q0 y6 _菜名(长度不超过 20 个字符) 价格(原价,整数) 是否荤菜( 1 表示是, 0 表示否) 是否辛辣( 1 表示是, 0 表示否)
    9 e- c; q! @9 M8 L% w9 l( P; j& P7 k  j. f& O2 Q1 _$ y6 M
    例: ( M; s+ U1 g: q5 M7 G: j3 y

    ) X2 u, M( S  h& h5 U6 i水煮鱼 30 1 1 4 s" B* L3 {! L. f: C& Q4 L
    7 Y; c" J% |, H& @/ f( f( P
    紧接着是 a b c d 四个整数,分别表示需要点的荤菜,素菜,辛辣,清淡菜的数目。
    4 S+ }9 `. u! q  P' F! M( I8 t) j$ m. ^% j' }
    输出数据: 0 p! u# |: l& ]( L9 ?* E; R
    " w( Y0 \4 b3 w' a# h% }
    对于每一测试数据,输出数据包含 M+1 行,前 M 行每行包含一个菜名(按菜名在原菜单的顺序排序)。第 M+1 行是人均消费,结果保留两位小数。
    ; f9 P) E6 d3 C( x
    + O6 a9 W8 _$ P2 x% i1 |+ ?' p说明:
    ( H, @( Y2 F2 v: g# K2 M5 |) w- |# w* i3 H
    1 .结果菜单的数目应该恰好为 M ,荤菜,素菜,辛辣,清淡菜的数目恰好为 a , b , c , d 。在满足这样的前提下,选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。
    6 h4 k) w; p3 O( N- Y" f, c! Y
    6 U% \6 p1 q8 ]4 [- T2 .每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。 ! R: T" W# D: `3 ]" W2 r

    % c: i  D% G% y+ g- I3 f7 t9 d输入样例

    7 [! [1 u- K9 I* @- V" P3 L
    3 2 2
    # h! {9 t9 s% |
    ! S  |& f" x& _& `水煮鱼 30 1 1
    0 l4 w& W! i- h
    7 x) h3 @% s7 E! J口水鸡 18 1 1 / F% Y. D3 X* c" U. m# ]- ^2 q+ d

    # u  E9 H- T2 T" ~" l8 |$ W9 t清炖豆腐 12 0 0 3 A" O7 G8 T+ x8 \/ v  z+ H
    4 Y% ]! S, p. ]" ~9 p$ k4 T1 j0 f
    1 1 1 1 ' E6 R. K9 g8 K  o; ]


    4 q" c9 f6 N' E6 t: [) O
    8 J/ Z+ ]9 N, ~% l输出样例

    # J2 }3 S, D5 ]2 w
    口水鸡
    : ]3 f, ~# }2 I7 I0 j( D# y( p+ z  j# h
    + c: q7 D) d$ T- n  q清炖豆腐
    ; t! G' s( O! h
    1 y0 D- T* p8 q, @! M/ S% H/ v, e12.00
    2 Y0 s! T8 o! W! \! |

    ( ^7 [* Z0 M8 _  j3 S' z- a0 M3 j

    . e1 ~1 V/ s" h! s$ e& F: P
    # I( h8 I' ?5 p( _/ r9 k时间要求: 1S 之内 3 C3 q% N/ k' K' t' y: O

    ; Z/ o0 f. n; \1 r7 ^0 Dexample:
    " Q1 f8 B4 g, _$ I8 x+ `# }#include <cstdlib>
    " B/ S9 Y' f  J% t. A/ e' v1 F#include <iostream>
    3 q2 [4 p! O$ H% a  s7 Z. m' Q* Y' z( }. e3 s! z
    using namespace std;
    # G9 q- @1 D: I- s% y% b2 N* n! y- C5 @  r* L

    " l/ k, o) ^' v, }" S5 {. T! Astruct cai! W5 B2 l! z$ ]; N% H% v" R0 {
    {
    ! S( t4 q  }" o( ?/ w       string cainame;
    2 J/ Q) u6 h" B5 y# q       int price;9 n: |5 n  m7 Y8 j2 A8 b
           int hun;
    2 |9 d! r6 C) u, A( Y$ n- d       int la;
    4 ?* U6 f4 e) L5 ~       };
    % A. J( z! E7 `- aint* alltotal=new int[30];) g6 ]" p" [( o2 s' C
    int pos=0;
    . d) l- c% B% I8 N; }2 Rcai* pcai;
    . ^. m  t0 a7 e: eint N=3;  
    / E* O! i! G- K, n1 K& Evoid fun(int * select,int n,int M,int a,int b,int c,int d,int total);
    , K% A- f& t( M' u2 Pint main(int argc, char *argv[])8 s# l6 d8 h: ?- b, D- E9 U+ y
    {: y! G8 E4 Q- Z
        int M=2,K=2;% y8 X0 |5 m2 K% \1 ?- f% h
        int a=1,b=1,c=1,d=1;
    9 J6 O6 g8 k2 c* l6 h: F) c    pcai = new cai[N];
      v7 O- w. }+ m- p: ^6 l7 Y    pcai[0].cainame="water fish";
    " Y# m  L9 ^& G( g    pcai[0].hun=1;
    . t( N6 N5 t2 l/ v* r* y    pcai[0].la=1;9 Z; J/ `. L4 t8 H8 B% j# {( H
        pcai[0].price=30;) G; d' g1 }: Z5 z/ c( Y% j; J) D/ [5 a
        pcai[1].cainame="mouth fish";
      K5 G. [$ _# q- D7 t, E$ ^+ _    pcai[1].hun=1;  ^0 [) Q8 L" D5 U* z
        pcai[1].la=1;& J6 _5 x9 p& ?
        pcai[1].price=18;
    , F1 C% y! ^0 Y    pcai[2].cainame="doufu";* G/ _. `* }& U/ K* n" ]2 d! d
        pcai[2].hun=0;
    2 s. b# Q- y1 ^$ j    pcai[2].la=0;/ B2 |; m3 q2 D  ^# |+ a: l
        pcai[2].price=12;
    6 q  ~2 U& C9 U7 |    for(int i=0;i<N;i++)5 |7 X! q1 W" r- o/ t
        {
    4 |, h# o+ M0 t; U        if( (pcai.hun==1 && a>0) ||(pcai.hun==0 && b>0) || (pcai.la==1 && c>0) || (pcai.la==0 && d>0))0 Y  n' ~$ `! Z/ |5 Z5 r
            {
    , [  L( k" Z( h( J  [% s  s- O        int ta=a,tb=b,tc=c,td=d;   
    6 }% v# d. u5 Y( k        int* select=new int[1];   
    ; F, n1 I0 b5 c+ s0 n        select[0]=i;0 F3 j+ e' }. }8 P0 g2 n. [5 B  T
            if(pcai.hun==1)ta--;else tb--;4 [3 R; b8 U0 p: o1 M
            if(pcai.la==1)tc--;else td--;' g% {4 g4 N! Z$ e- T( Q( C5 H2 [
            fun(select,1,M-1,ta,tb,tc,td,pcai.price);" t, J0 x! e0 M0 Y4 l0 Y
            delete[] select;/ p8 x3 c: J+ s- v; [) Q/ Q
            }. F, H& `3 G, I5 W6 O
        }
    4 [  |7 \3 P6 t; @  I    for(int i=0;i<pos;i++)
    * v  v. P4 N! X% F8 Q$ C  U    cout<<alltotal<<endl;
    4 f# h; {( |. I2 d    delete alltotal;
    4 r( \% [. z0 U3 Q    delete []pcai;1 v4 f' _. @& L: a8 V! Q' u$ J
        system("PAUSE");
    ! B5 k9 o+ W! C    return EXIT_SUCCESS;) B1 ^: q$ e6 `
    }
    ) x! P" Z, [& h9 b% y- y- d# i/ w+ y) rvoid fun(int * select,int n,int M,int a,int b,int c,int d,int total)2 K8 D2 c8 ]: M: {# ~. O+ A
    {4 Z# A$ y# L6 A( |/ J
        //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;: [9 k( c# ], e1 ~& S( w
        //getchar();5 ]; s$ F; M8 P( j( F
        //cout<<n<<"|"<<M<<"|"<<a<<"|"<<b<<"|"<<c<<"|"<<d<<"|"<<total<<"|"<<endl;3 G1 a) U4 m7 i, c5 I) _3 z/ ]$ H
        if(M<=0 && (a>0||b>0||c>0||d>0)){cout<<"impossible"<<endl;return;}6 J0 e8 [+ T  B7 Z; K+ [
        if(M<=0 && (a<=0&&b<=0&&c<=0&&d<=0)){cout<<total<<endl;alltotal[pos++]=total;return;}
    9 t/ I' L% ]2 n4 U' L    for(int i=select[n-1];i<N;i++)3 A* \; p! h* }5 |( z1 L( ]) @
        {6 n! J, E) T# g0 A+ d6 s- p
             for(int j=0;j<n;j++)if(select[j]==i)continue;/ r1 H! y' j& u) s  q0 x" A
            if( (a<=0&&b<=0&&c<=0&&d<=0) || (pcai.hun==1 && a>0) ||(pcai.hun==0 && b>0) || (pcai.la==1 && c>0) || (pcai.la==0 && d>0))' J& N) q- G( r5 p
            {2 q! R* w) @6 F8 Y3 t
            int ta=a,tb=b,tc=c,td=d;' C; G) ~3 w- `& R  y
            int* myselect=new int[n+1];    ' G8 ~+ _  Z1 V" {+ n: X
            for(int k=0;k<n;k++)myselect[k]=select[k];( K- J0 y" \6 l6 B" _- s
            myselect[n]=i;; s1 j/ r4 B4 R" h8 u: U
            if(pcai.hun==1)ta--;else tb--;
    9 \5 m8 W5 U3 C! s, d        if(pcai.la==1)tc--;else td--;
    : S( h) V: \) ^        fun(myselect,n+1,M-1,ta,tb,tc,td,total+pcai.price);- {8 {; x4 n6 R- @, D
            delete[] myselect;0 v- w. y6 r9 K6 R, v
            }
    & R7 u8 S# F+ p# [, [# |7 U- _    }" e* l" N- J0 U9 D# u' i
    }
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    928171481        

    2

    主题

    6

    听众

    34

    积分

    升级  30.53%

    该用户从未签到

    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-6-14 15:28 , Processed in 0.378939 second(s), 55 queries .

    回顶部