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

厚积薄发

饭团的烦恼
$ H! b8 J% a; V; v' U3 y: _
& V6 e8 S$ ^1 k) ~2 `6 Q0 N' q“午餐饭团“是百度内部参与人数最多的民间组织。
  @4 i5 p! ^  `5 a3 U! h: g
同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。

( {) ~/ v) P- Q+ @4 W, b5 |参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。
0 y, ~( {4 h8 E8 Q& M
& [2 H( O7 A2 f但是，随着百度的员工越来越多，各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口，饭团的点菜负责人背负的责任越来越大。现在，这个重担落在百度之星的肩上，因为，你们将要为所有的百度饭团设计一个自动点菜的算法。

7 [, U) ]6 S, n& t0 y( A$ c饭团点菜的需求如下：
# {" \/ J. E  J) {7 o4 n9 f
1 ． 经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近 12 元越好。

2 ． 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。

3 ． 请紧记，百度饭团在各大餐馆享受 8 折优惠。
( l$ c$ k" Z7 L1 P& Y6 R
输入数据描述如下：

% i/ N3 J+ Y$ O# x4 P% K9 x$ Y& n第一行包含三个整数 N ， M ， K （ 0<N<=16 ， 0<M<=N ， 0<K<=12 ），分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。

+ \* g' u- H, t1 H2 v- k紧接着 N 行，每行的格式如下：
5 i7 _* T4 j7 Z# U& A& l( o
# O1 F& Y/ o8 i7 [- e3 R菜名（长度不超过 20 个字符） 价格（原价，整数） 是否荤菜（ 1 表示是， 0 表示否） 是否辛辣（ 1 表示是， 0 表示否）
2 h) g2 m: [- k) ]
例：

9 y; z. z% L' N3 I: U水煮鱼 30 1 1
+ w. v0 `9 h/ s0 n" J
紧接着是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。

输出数据：
' Z' I. v  C* q5 _
7 F* `/ f$ M4 Y, Q  D& H+ Y9 e对于每一测试数据，输出数据包含 M+1 行，前 M 行每行包含一个菜名（按菜名在原菜单的顺序排序）。第 M+1 行是人均消费，结果保留两位小数。
: P+ f8 U  F7 C- N( @
4 \: a6 b* P! F. G; E说明：
- y' g3 U  w) @, M$ F5 y
% [- P+ F  a( Y) C& Z& r) }4 e1 J1 ．结果菜单的数目应该恰好为 M ，荤菜，素菜，辛辣，清淡菜的数目恰好为 a ， b ， c ， d 。在满足这样的前提下，选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。
) X, Z0 g6 K1 P/ k4 R6 p. N
& l" ~' h6 P) q: l4 X& {2 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。
0 w  `6 W9 d+ K. `
输入样例

3 2 2

9 v1 B! R  C+ Q4 Y$ S$ |* \水煮鱼 30 1 1

% v! C( y' @6 x2 c/ o口水鸡 18 1 1

清炖豆腐 12 0 0
9 u% }' {2 g8 y; {1 x
# R& n# G; X! c1 1 1 1

输出样例

$ Y/ O$ y* Z, n5 p$ Q1 c) s  A1 E口水鸡

' V2 E. a* [: @3 W: Z: y4 `清炖豆腐
6 u7 ?7 w- s( F
. |+ U/ Y* j$ y  q4 Y12.00

时间要求： 1S 之内
) b' }7 @0 K- R! q# w' E  E1 w
% M; |* L3 ]# P% uexample：
! g7 m6 G8 M# |9 U. n#include <cstdlib>
! j7 Q, M3 {0 e: l' K6 `$ f3 ~) ~4 Q' h#include <iostream>
' z  `' X1 \# k$ k3 T
% G1 p2 d6 j! L' b$ `4 Jusing namespace std;
0 P' a' V$ s+ M) z4 ?! H+ Z% S( E, e

9 ~$ i2 s* d( H( F& a8 M0 }( Hstruct cai
: R' Y$ V/ t5 A& q+ b' F& p{
) i/ F8 ]5 @; N3 U       string cainame;
, ~2 s2 _; b7 n2 B% r4 t" x       int price;
       int hun;
       int la;
       };
/ J9 `% b; q! `4 M4 d0 h- A2 fint* alltotal=new int[30];
# y( ]3 t0 S! K* Cint pos=0;
cai* pcai;
2 H- }9 ^5 _/ @  Q. ]" P8 Lint N=3;  
! ^" u% Z- K& \# K& f, c' f3 wvoid fun(int * select,int n,int M,int a,int b,int c,int d,int total);
  B# q, Z4 |4 Q1 Pint main(int argc, char *argv[])
+ U- L# [; Y7 b* T{
! {6 _0 ~* C- N4 F9 U. x    int M=2,K=2;
$ E9 X8 Q3 A. P) l* s9 v4 o: S5 ?9 E    int a=1,b=1,c=1,d=1;
3 U) C. @. P' |# F3 N    pcai = new cai[N];
$ v2 N9 {7 a8 \; U    pcai[0].cainame="water fish";
    pcai[0].hun=1;
    pcai[0].la=1;
    pcai[0].price=30;
    pcai[1].cainame="mouth fish";
    pcai[1].hun=1;
    pcai[1].la=1;
    pcai[1].price=18;
" f5 T% K4 Q3 n    pcai[2].cainame="doufu";
    pcai[2].hun=0;
    pcai[2].la=0;
9 l; k; K- f: e, n& A) f8 g    pcai[2].price=12;
7 L( k, L- B  U" z# W    for(int i=0;i<N;i++)
    {
3 `7 C! c) F, B) E        if( (pcai.hun==1 && a>0) ||(pcai.hun==0 && b>0) || (pcai.la==1 && c>0) || (pcai.la==0 && d>0))
        {
1 x: n, v4 H4 {* I        int ta=a,tb=b,tc=c,td=d;   
4 E% s6 x; s  u& p9 x2 y9 j        int* select=new int[1];   
        select[0]=i;
5 k* q% ~' a% O8 H$ F        if(pcai.hun==1)ta--;else tb--;
        if(pcai.la==1)tc--;else td--;
5 Y& [7 ?1 T, L2 Z* N8 a: Z        fun(select,1,M-1,ta,tb,tc,td,pcai.price);
        delete[] select;
        }
    }
    for(int i=0;i<pos;i++)
    cout<<alltotal<<endl;
    delete alltotal;
    delete []pcai;
7 m- p6 F+ R1 S" e1 n! e1 Q    system("PAUSE");
4 I- r/ p# m$ B8 Q) n5 B2 x: _    return EXIT_SUCCESS;
$ g! P4 k8 G9 B4 e/ B}
* C* ^; K& l+ {; g0 kvoid fun(int * select,int n,int M,int a,int b,int c,int d,int total)
6 b1 D" W/ r9 M$ S{
0 q, V  [1 x4 l5 X) _# M4 X$ U8 v    //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;
" D; `: o1 H- q9 n; w  @4 k. n    //getchar();
    //cout<<n<<"|"<<M<<"|"<<a<<"|"<<b<<"|"<<c<<"|"<<d<<"|"<<total<<"|"<<endl;
    if(M<=0 && (a>0||b>0||c>0||d>0)){cout<<"impossible"<<endl;return;}
. I  z  M( {2 @- ?( D    if(M<=0 && (a<=0&&b<=0&&c<=0&&d<=0)){cout<<total<<endl;alltotal[pos++]=total;return;}
( t" P# g3 G( f8 G    for(int i=select[n-1];i<N;i++)
    {
         for(int j=0;j<n;j++)if(select[j]==i)continue;
) C' i2 i2 }' P4 U) K        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))
        {
        int ta=a,tb=b,tc=c,td=d;
; N' K" n4 t8 {( D8 ?. C+ e        int* myselect=new int[n+1];   
) u6 u; c; |, }        for(int k=0;k<n;k++)myselect[k]=select[k];
' K. s3 i. ^3 n) S, ~8 H' I        myselect[n]=i;
        if(pcai.hun==1)ta--;else tb--;
        if(pcai.la==1)tc--;else td--;
/ I, N; _' J( _" o        fun(myselect,n+1,M-1,ta,tb,tc,td,total+pcai.price);
* Y! H- n  S6 l5 _0 @1 Q        delete[] myselect;
        }
4 q+ a7 J, w( m9 l    }
2 j9 i( v+ V& b0 l7 v4 H}

928171481

嗯，不错不错