QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 12525|回复: 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 |邮箱已经成功绑定
    饭团的烦恼
    ' e6 U0 S3 M: z7 W8 ?6 Q2 l! ^9 y2 ~
    “午餐饭团“是百度内部参与人数最多的民间组织。 ( M1 N% p, n% N

    + F0 c# }2 t4 {同一个部门的,同一间大学的,同一年出生的,用同一种型号电脑的,员工们总是以各种理由,各种借口组织各种长久的,临时的饭团。   u, k+ c* X0 V5 O. O! c1 s0 L

    4 v( q8 K: X! X: u9 Q参加饭团,不仅可以以优惠的价格尝到更加丰富的菜式,还可以在吃饭的时候和同事们唠唠嗑,吹吹水,增进感情。 . {! J4 N- S+ O* J/ A! V
    7 x1 v! U1 a& I( d& d# W
    但是,随着百度的员工越来越多,各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口,饭团的点菜负责人背负的责任越来越大。现在,这个重担落在百度之星的肩上,因为,你们将要为所有的百度饭团设计一个自动点菜的算法。
    - }7 q) p6 i& c' v; b1 e1 N# K
    ) S$ `' f7 S7 Y) E* ~( y  ~饭团点菜的需求如下: & m& r* e9 J2 P5 ^. d- Y. A) @! v
    9 _+ ^2 R; I5 C3 o" @4 D
    1 . 经济是我们要考虑的一个因素,既要充分利用百度员工的午餐补助,又不能铺张浪费。因此,我们希望最后的人均费用越接近 12 元越好。 , t% b0 b* Y4 C6 g

    0 A8 `# e& b% `, c$ Z2 . 菜式丰富是我们要考虑的另一个因素。为简单起见,我们将各种菜肴的属性归结为荤菜,素菜,辛辣,清淡,并且每个菜只能点一次。 4 O( J* r* V+ c$ G# ~% D, p

    2 A) P! r5 D# h3 . 请紧记,百度饭团在各大餐馆享受 8 折优惠。 / Z8 s, [# l  k4 z% Q

    9 V5 s5 R2 D6 I8 s: P2 T输入数据描述如下:
    5 {0 B% j* |- o+ I; Y9 l* W4 M/ x7 }
    第一行包含三个整数 N , M , K ( 0<N<=16 , 0<M<=N , 0<K<=12 ),分别表示菜单上菜的数目,饭团需要点的菜的数目,就餐的人数。
    : U* j. L$ s6 F: ]8 w* J# u; ~2 K: A! _
    紧接着 N 行,每行的格式如下: 2 {) i) G1 ?$ e
    * b% w- y$ s( p& V
    菜名(长度不超过 20 个字符) 价格(原价,整数) 是否荤菜( 1 表示是, 0 表示否) 是否辛辣( 1 表示是, 0 表示否) % C& z+ k1 o' P5 o7 q& _
    ' j7 G" a; ?+ O' ~. b
    例:
    0 A0 W+ W5 b8 J* _
    & i* @& O  l$ s水煮鱼 30 1 1 % q9 O- S; I- [8 @0 f+ \

    0 g* |9 K4 P8 i5 b" |紧接着是 a b c d 四个整数,分别表示需要点的荤菜,素菜,辛辣,清淡菜的数目。
    ; U: l8 @7 ]/ O# f* y1 k/ \) Q% e4 g! M; t
    输出数据:
    9 I! a0 H8 H" B; k6 e2 x
    . S, R5 P4 p" |4 m* @对于每一测试数据,输出数据包含 M+1 行,前 M 行每行包含一个菜名(按菜名在原菜单的顺序排序)。第 M+1 行是人均消费,结果保留两位小数。 8 n' U- |, `2 D6 d  N3 O3 x% R/ ]* L6 t

    0 r% r# S* z3 z说明:
    , ?5 z) R" ~( u, c  n7 ^( U
    . i) L9 @' c( q; R$ }4 h1 .结果菜单的数目应该恰好为 M ,荤菜,素菜,辛辣,清淡菜的数目恰好为 a , b , c , d 。在满足这样的前提下,选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。
    " Q* {" o4 |" ~- B! y( f! b" [1 s" @
    2 .每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。
    9 d( w5 ~8 A3 o. @( t& o, ]7 h9 \- |% P7 I6 ?
    输入样例

    0 g. U5 h! S- u+ w
    3 2 2 5 V; z- p1 q8 e7 h
    $ F7 `2 X  T) M; [! y
    水煮鱼 30 1 1 " u& d# V: i: S9 v/ _# G/ h5 [# K- P
    % F$ j0 o) _6 D
    口水鸡 18 1 1
    1 N* [7 X; I" ]# O: _8 y& }$ H) ]! K, M8 \
    清炖豆腐 12 0 0
    & N7 H7 }. A  W1 x0 D
    2 o  B; ?7 R- \7 [1 _' z  H1 1 1 1 / C5 H  `6 w+ {. X7 P* ~


    ' C! n! K2 v2 p% @- m1 r' a, j0 e3 R1 D. h9 ]/ b6 G: ]$ L
    输出样例

    ) C4 n# i, x: a
    口水鸡
    . w8 f9 c9 W/ P. b; ^6 a6 n- g4 I6 \+ T! o' I1 x1 N; T
    清炖豆腐 / E$ S# X- F4 f# \# q5 R$ P

    2 o% ^! T& M% [7 A; l6 r* v/ c+ z12.00
    " A: n( {8 n7 i& d0 ?2 A


    ; [% O& C' D2 s' N
    5 W& m+ W' X& A% W) z7 u; f5 p, x  W) {
    时间要求: 1S 之内
    3 {- B: Y( E* N" {& z7 ?) D& V/ x' E2 _/ \5 P
    example:
    0 T& [# ~3 j5 @5 P: K#include <cstdlib>
    . `3 l+ b. Y1 p' m9 s#include <iostream>- Q) h8 p6 w$ e3 s% _8 o

    ; z: `1 p& `6 d% musing namespace std;
    8 j0 H- j/ T6 |3 r' V( T* r5 y2 L$ I! Q* [& L
    " C1 E9 c% G$ m9 ^# y, n: E# z
    struct cai
    $ b$ k$ z! w, ^$ X0 ~) X7 _{& R; X7 r8 ?" d2 ]% l: b
           string cainame;
    3 S- T: A7 T+ p  S       int price;
    ) O' m- n& d8 K7 K$ e# s0 s7 m       int hun;
    / S! ?- e: ^6 a" s. Q( i       int la;
    2 [1 Y; P0 j- z  s3 C       };" \5 k$ H) I' J; Q6 E7 F( v$ f; v
    int* alltotal=new int[30];
    - m8 B2 @' m( g" N& t# M; f  c, Mint pos=0;
    9 u- A4 b$ h; @cai* pcai;
    / W; M# A8 _8 b$ `  M( kint N=3;  
    9 D* n; o, ~& K1 Z; V2 m  a2 i- T- wvoid fun(int * select,int n,int M,int a,int b,int c,int d,int total);
    + u1 R5 b* r/ n  ]int main(int argc, char *argv[])
    9 z  D8 I% S5 w3 _3 t" ]6 y" Q{) y3 a+ C# q$ H- {/ a
        int M=2,K=2;0 a3 U4 H* C, g* _8 M$ y1 R
        int a=1,b=1,c=1,d=1;
    + y+ J5 g+ o% d    pcai = new cai[N];8 ^# t: m4 T/ k: Q
        pcai[0].cainame="water fish";
    0 Z; d* D/ ~% M) s9 q    pcai[0].hun=1;
    + `/ b8 A) l6 ~! l( G5 ^# z; Y    pcai[0].la=1;
    / v: I* _& s* a    pcai[0].price=30;/ U) ^  p, V7 R; M
        pcai[1].cainame="mouth fish";
    3 \( s- e* _; u' ~. q( d    pcai[1].hun=1;
    & _1 @4 I+ [* C    pcai[1].la=1;" G8 k+ ~/ Z9 {( a, w
        pcai[1].price=18; ( _0 p( R  o, u! f
        pcai[2].cainame="doufu";- Y. J6 x, k  {* w+ ]
        pcai[2].hun=0;& V& ]) ^; T+ v' Z( q% @
        pcai[2].la=0;
    3 |% G7 z! R6 [7 ?0 c# E7 x    pcai[2].price=12; 3 D- j1 j4 ?: j  x& B' B# T
        for(int i=0;i<N;i++)
    3 i8 Q' c. ~) D6 O/ J9 y( A    {
    4 y) q- O3 m* d) Z        if( (pcai.hun==1 && a>0) ||(pcai.hun==0 && b>0) || (pcai.la==1 && c>0) || (pcai.la==0 && d>0))+ }7 ?) N9 V3 u  P
            {4 [3 w* W& C- k9 z# L2 s0 |' o" j
            int ta=a,tb=b,tc=c,td=d;    3 p% ^" l- @) W6 u3 N, E2 f6 ~
            int* select=new int[1];    . s/ y8 U: F' b5 u" @) {& ?3 R! t1 E) I
            select[0]=i;9 \8 c+ V) C' T( M* _6 @  E
            if(pcai.hun==1)ta--;else tb--;
    , s! B+ }3 ^/ }, k9 ]1 R) p        if(pcai.la==1)tc--;else td--;
    6 |+ u, O4 @( L; R3 G        fun(select,1,M-1,ta,tb,tc,td,pcai.price);+ v# J$ u( ]4 \- d% r: \; z
            delete[] select;
    0 N+ x* ?3 Q5 j2 w# P- y, m9 [        }2 h1 g4 }" Y9 V
        }, z4 F4 Q- R/ }* u, }: l# W2 d
        for(int i=0;i<pos;i++)1 ~/ N. m. S' s
        cout<<alltotal<<endl;
    / t& O- ~* [# g. y    delete alltotal;0 E' l7 ]- C2 ~/ f6 r
        delete []pcai;) H1 m' H$ Q1 k4 j
        system("PAUSE");: t6 |9 e. e: [/ y& z
        return EXIT_SUCCESS;
    8 Z# T9 {4 v- K3 |) v* a}
    ) }0 t: S: g5 s2 o/ Qvoid fun(int * select,int n,int M,int a,int b,int c,int d,int total)/ }- ^9 ^  u. i: B/ f
    {
    # N% I% R; z. ?    //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;
    & M5 \0 {, b6 l0 d1 a8 R4 e  O    //getchar();
    ' }1 f/ l" F: y8 h    //cout<<n<<"|"<<M<<"|"<<a<<"|"<<b<<"|"<<c<<"|"<<d<<"|"<<total<<"|"<<endl;
    2 X( n* c, T  q7 L    if(M<=0 && (a>0||b>0||c>0||d>0)){cout<<"impossible"<<endl;return;}
    $ {0 a- j2 Z! _/ K; q+ M) n9 @    if(M<=0 && (a<=0&&b<=0&&c<=0&&d<=0)){cout<<total<<endl;alltotal[pos++]=total;return;}
    9 w+ q- f0 _; w4 Y0 T3 n0 H    for(int i=select[n-1];i<N;i++)
    ! ]8 W2 G; \9 D7 R. o    {
      t; @0 _1 t  r5 Y/ y4 s         for(int j=0;j<n;j++)if(select[j]==i)continue;. w* w9 j; O! @9 r8 I
            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))( L. W( r$ z2 ~3 [
            {
    3 J: a( ?; j; R* ~2 u) ?        int ta=a,tb=b,tc=c,td=d;
    # m' ?4 r$ }- W( ~- e4 W* z4 E' v2 r        int* myselect=new int[n+1];   
    & z6 g6 A1 F' Q/ z, Q        for(int k=0;k<n;k++)myselect[k]=select[k];
    - d% R+ d, k( S2 ~  ^0 j/ e* J1 L/ T$ \        myselect[n]=i;
    + k. F" ~3 x; n& z! y$ r        if(pcai.hun==1)ta--;else tb--;
    9 p  k) P0 A4 @& A        if(pcai.la==1)tc--;else td--;
    # H1 O! e2 r9 W9 B! {        fun(myselect,n+1,M-1,ta,tb,tc,td,total+pcai.price);
    2 b& F+ E+ T" r& m2 a9 J# e9 y        delete[] myselect;
    . w1 X, ]9 G8 c9 i: R3 i        }' a1 L+ L2 V( n. `
        }
    * @" F2 m7 Z; p' n}
    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-8-27 06:45 , Processed in 0.495038 second(s), 56 queries .

    回顶部