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

厚积薄发

饭团的烦恼

" g) K( E+ O1 M3 P  q$ d: J“午餐饭团“是百度内部参与人数最多的民间组织。
/ C3 B. |2 z9 ]3 y% J  M5 P
同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。

参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。
" ?  n2 ^' n; P+ T& w2 }
7 \  [: g) _  L3 U; |但是，随着百度的员工越来越多，各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口，饭团的点菜负责人背负的责任越来越大。现在，这个重担落在百度之星的肩上，因为，你们将要为所有的百度饭团设计一个自动点菜的算法。

; e' N/ U$ J% x# I# z, ?% a' h0 ^饭团点菜的需求如下：
- f7 Q0 w' U0 n7 [
# ]& v8 x  l1 \# h' z7 \1 ． 经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近 12 元越好。
. |. Q+ d* b! o" e* y
2 ． 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。

, Z$ L$ v& r! n+ d. E3 ． 请紧记，百度饭团在各大餐馆享受 8 折优惠。

输入数据描述如下：
" b* j$ r& |1 h' l/ B7 A
' J; }8 J. i! s% h# U6 ^5 k第一行包含三个整数 N ， M ， K （ 0<N<=16 ， 0<M<=N ， 0<K<=12 ），分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。
9 L/ ~: L# A4 c+ z3 M0 o- D" z
紧接着 N 行，每行的格式如下：
2 s+ P: a3 [4 j% K
菜名（长度不超过 20 个字符） 价格（原价，整数） 是否荤菜（ 1 表示是， 0 表示否） 是否辛辣（ 1 表示是， 0 表示否）
3 J2 b' T% T$ c% w
例：
! L- w( ~8 r' Z, \4 x5 Y
2 ]" k/ G0 t% ]水煮鱼 30 1 1

' b$ S. u& u; p/ m# `紧接着是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。

) \6 @- B: o6 X5 f  L! |输出数据：
& {4 Q5 w& q* Y" ?# _" C- X
对于每一测试数据，输出数据包含 M+1 行，前 M 行每行包含一个菜名（按菜名在原菜单的顺序排序）。第 M+1 行是人均消费，结果保留两位小数。

* c; G' C/ u3 |/ k说明：

1 ．结果菜单的数目应该恰好为 M ，荤菜，素菜，辛辣，清淡菜的数目恰好为 a ， b ， c ， d 。在满足这样的前提下，选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。

2 X( Y" |* Z  I: ]1 {2 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。
* _# Y" ], X* K* j8 F5 Z3 x
! s: z. N: p# H: k4 I输入样例

3 2 2
. y& B: P0 @) [9 t# \
水煮鱼 30 1 1

; q- R) c+ f# x2 N- A口水鸡 18 1 1

清炖豆腐 12 0 0
5 `) v  h3 [. n
) n" u9 {, A) E; m: L1 1 1 1

. c( \8 V2 ~" P7 ]8 ~* d  b输出样例

口水鸡
6 \5 Z, G. m- L
清炖豆腐

12.00

: e7 U; G+ u6 o% J
$ h. {" r9 B; U+ d5 t
时间要求： 1S 之内
6 |! F5 T2 l2 G' [  _; M9 \
" j9 ?8 H! f7 |- e& T% Fexample：
& U0 C8 n* o$ S7 ~$ A7 ~#include <cstdlib>
: m( E! B/ I6 v; {+ r, g#include <iostream>

8 H( V3 i- h3 p" Rusing namespace std;
% v2 l8 p7 d# U* A* l. F( J

, z6 b& V4 Y  C! B5 ^" dstruct cai
{
. L) z7 s: z- w' e, F' y" j6 J       string cainame;
- A/ o( [+ W, p' u6 @       int price;
9 V) ]! Y9 d5 G       int hun;
       int la;
& u) h; T& C6 ^4 Q4 N  y       };
, [) i7 {: c6 l# f0 Lint* alltotal=new int[30];
int pos=0;
( j: J, q. B. q4 H: pcai* pcai;
) B0 K* J+ @% d$ Y) Sint N=3;  
void fun(int * select,int n,int M,int a,int b,int c,int d,int total);
int main(int argc, char *argv[])
% s1 l  L. f, e* |8 e{
    int M=2,K=2;
    int a=1,b=1,c=1,d=1;
    pcai = new cai[N];
    pcai[0].cainame="water fish";
2 G6 Q, [  \+ ^+ \    pcai[0].hun=1;
9 p$ Q+ s2 Z! x$ N    pcai[0].la=1;
. n9 H4 ~* N+ T! K2 B; ~/ V    pcai[0].price=30;
4 i) v6 |* p9 |$ h    pcai[1].cainame="mouth fish";
5 l# `" x2 I7 l$ x$ ~4 r    pcai[1].hun=1;
: E$ u7 x; B* }' H' ^. Q    pcai[1].la=1;
    pcai[1].price=18;
! m1 ]* i& b# o6 C    pcai[2].cainame="doufu";
    pcai[2].hun=0;
    pcai[2].la=0;
1 A1 P& O: E* I+ E7 a$ L    pcai[2].price=12;
1 m. H" ]" o! M& R( F    for(int i=0;i<N;i++)
  n: j7 V: ^$ a. k  F7 P3 [7 ]/ }    {
        if( (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;   
  ]! C' X: C0 x  n        int* select=new int[1];   
        select[0]=i;
        if(pcai.hun==1)ta--;else tb--;
        if(pcai.la==1)tc--;else td--;
% z/ {0 \# Z: A8 ?6 ]        fun(select,1,M-1,ta,tb,tc,td,pcai.price);
( X8 G9 z+ g: S        delete[] select;
: p. X6 I& @  n4 I        }
    }
    for(int i=0;i<pos;i++)
% I9 Z/ W) S* o5 |3 o2 B3 L    cout<<alltotal<<endl;
1 Q, o4 C( b- I5 |    delete alltotal;
    delete []pcai;
    system("PAUSE");
    return EXIT_SUCCESS;
5 E# t! P/ w7 A+ q+ q) D. l' p! R}
+ [$ W. x! w$ Q* s7 j: bvoid fun(int * select,int n,int M,int a,int b,int c,int d,int total)
0 s% u& c4 h. w% E+ t' J# i{
+ Z. Z5 _" V  t7 H+ B3 ^    //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;
' Q" u$ W2 E/ i5 C    //getchar();
    //cout<<n<<"|"<<M<<"|"<<a<<"|"<<b<<"|"<<c<<"|"<<d<<"|"<<total<<"|"<<endl;
7 V& t- N3 F& K/ a7 k    if(M<=0 && (a>0||b>0||c>0||d>0)){cout<<"impossible"<<endl;return;}
1 p& W' N1 R9 g0 y' h! O; M    if(M<=0 && (a<=0&&b<=0&&c<=0&&d<=0)){cout<<total<<endl;alltotal[pos++]=total;return;}
3 j$ T$ e1 w; W    for(int i=select[n-1];i<N;i++)
    {
         for(int j=0;j<n;j++)if(select[j]==i)continue;
        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;
& ]$ D. F7 n- s. u4 {        int* myselect=new int[n+1];   
9 M$ ]* x$ h$ R/ x* \        for(int k=0;k<n;k++)myselect[k]=select[k];
        myselect[n]=i;
, F1 r' J' F0 _3 [        if(pcai.hun==1)ta--;else tb--;
        if(pcai.la==1)tc--;else td--;
% D2 D  P/ f. d: ]# C        fun(myselect,n+1,M-1,ta,tb,tc,td,total+pcai.price);
        delete[] myselect;
5 c, S0 Q* K* B9 C& V        }
0 g$ I6 P3 T; C+ T/ m% _    }
}

928171481

嗯，不错不错