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

厚积薄发

饭团的烦恼
$ ]/ P1 S7 E4 {$ z
“午餐饭团“是百度内部参与人数最多的民间组织。
5 q/ t* z8 h6 L5 `9 H  C# P
# B3 w, x6 r% a" j8 l同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。

参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。

' F: ~! ]  Q1 d" D0 z7 N& y$ T但是，随着百度的员工越来越多，各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口，饭团的点菜负责人背负的责任越来越大。现在，这个重担落在百度之星的肩上，因为，你们将要为所有的百度饭团设计一个自动点菜的算法。

饭团点菜的需求如下：

- Y, y" q. P9 u, v* o0 M, B1 ． 经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近 12 元越好。
- e. w- a+ m: ]0 K
5 f8 E' b" C* G6 y; e2 ． 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。

+ g1 ^. ?* s% `3 P* k; J/ {3 ． 请紧记，百度饭团在各大餐馆享受 8 折优惠。

8 {' H, j3 p; _' x' ?输入数据描述如下：

4 f: R. K9 f( _/ j8 c* B第一行包含三个整数 N ， M ， K （ 0<N<=16 ， 0<M<=N ， 0<K<=12 ），分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。

4 Y# P, e3 |  ?3 y& y( p紧接着 N 行，每行的格式如下：
1 j  m# I! e  i# S  }% T
菜名（长度不超过 20 个字符） 价格（原价，整数） 是否荤菜（ 1 表示是， 0 表示否） 是否辛辣（ 1 表示是， 0 表示否）

例：

! q& W. x( _" M5 X1 K水煮鱼 30 1 1
; ?+ o! {, A; p& a0 V- E9 W
紧接着是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。

3 E$ e" h$ b2 P% q" m1 r# g输出数据：
, t! |3 V) W) i# U
% A. U. I4 f& I对于每一测试数据，输出数据包含 M+1 行，前 M 行每行包含一个菜名（按菜名在原菜单的顺序排序）。第 M+1 行是人均消费，结果保留两位小数。

说明：

$ w0 {" @1 q# l% Z: I1 ．结果菜单的数目应该恰好为 M ，荤菜，素菜，辛辣，清淡菜的数目恰好为 a ， b ， c ， d 。在满足这样的前提下，选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。
" e: m; E4 N$ M6 g4 U! |
2 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。

$ K  E# ]/ Q7 ]$ [% F& r/ K3 [输入样例

3 2 2
! S& t- B) `+ L. H2 q& b* ^" Z
水煮鱼 30 1 1

口水鸡 18 1 1

4 F) M( }4 M  a- o6 B5 @清炖豆腐 12 0 0
; ~' j% g6 S" _3 x8 t0 N
1 1 1 1

输出样例

3 a3 J  S0 S) `# s9 w( o  E+ U- d口水鸡

清炖豆腐
% ^7 j# b. g* p% n0 A
12.00

, I) j* r! ~" w' i
1 p9 f3 W0 P5 I! J/ R
  c' f( q1 t% M- V时间要求： 1S 之内
2 M8 F* \% |4 ?2 @" s+ g
example：
#include <cstdlib>
9 P1 h& o; C' V% ?#include <iostream>
6 a/ X" t; V3 N! p( M0 B$ y
& Z; p: ]/ V$ F! f6 U8 P+ Cusing namespace std;
9 g) T$ V/ k: R. ^( a3 K

3 h! c7 O4 T& n8 pstruct cai
{
       string cainame;
+ y" a8 T5 ]4 X( n$ Z       int price;
       int hun;
       int la;
       };
int* alltotal=new int[30];
; {9 M! S- ?; F& V. sint pos=0;
* J- c" B4 C. O! f8 Kcai* pcai;
int N=3;  
! s8 k1 i/ l/ n6 Vvoid fun(int * select,int n,int M,int a,int b,int c,int d,int total);
int main(int argc, char *argv[])
9 x3 b/ b" ^. v. E{
9 _% X, m* Q2 w$ L0 p, N  M( D    int M=2,K=2;
9 i3 q3 p; j+ l2 z$ R' G$ T    int a=1,b=1,c=1,d=1;
8 U! \# L; `$ B" C- f: m- K3 i    pcai = new cai[N];
    pcai[0].cainame="water fish";
    pcai[0].hun=1;
    pcai[0].la=1;
    pcai[0].price=30;
    pcai[1].cainame="mouth fish";
6 r7 i& m! I9 \: F! J! {- u    pcai[1].hun=1;
1 q; }% V( `3 y& n7 U) g    pcai[1].la=1;
; V  M) i/ Y0 s+ o2 }. ^6 f    pcai[1].price=18;
' b2 w0 L- L. t7 {    pcai[2].cainame="doufu";
    pcai[2].hun=0;
    pcai[2].la=0;
    pcai[2].price=12;
) F! C  n2 M  Y% z- b5 p    for(int i=0;i<N;i++)
    {
        if( (pcai.hun==1 && a>0) ||(pcai.hun==0 && b>0) || (pcai.la==1 && c>0) || (pcai.la==0 && d>0))
! j$ b8 b/ ^4 j& y, q8 q        {
! @$ Z, f+ {6 x2 Z. X        int ta=a,tb=b,tc=c,td=d;   
        int* select=new int[1];   
- B2 P0 f5 }& P2 a& `, L+ \        select[0]=i;
        if(pcai.hun==1)ta--;else tb--;
% L! {2 ?& A* z: S7 B        if(pcai.la==1)tc--;else td--;
        fun(select,1,M-1,ta,tb,tc,td,pcai.price);
4 p1 ~% }& w6 @  e/ ?        delete[] select;
        }
8 ?" g2 L  }* q; e    }
! B/ u: _( t, F1 I+ G    for(int i=0;i<pos;i++)
- _% x9 R% Z; s( K2 u    cout<<alltotal<<endl;
    delete alltotal;
    delete []pcai;
    system("PAUSE");
& _+ c# @) C: X! W# f4 X2 p; \6 l    return EXIT_SUCCESS;
}
4 Q3 M$ ]% g# Y8 D4 _. f/ G$ v/ g6 S' hvoid fun(int * select,int n,int M,int a,int b,int c,int d,int total)
! x% |+ j2 S# F" T, V{
6 v+ G2 V! v* D' ~5 y    //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;
    //getchar();
1 y' o2 P) u: w, A/ ]8 J0 r3 ^- `    //cout<<n<<"|"<<M<<"|"<<a<<"|"<<b<<"|"<<c<<"|"<<d<<"|"<<total<<"|"<<endl;
    if(M<=0 && (a>0||b>0||c>0||d>0)){cout<<"impossible"<<endl;return;}
. [) c9 f) d" e% D+ p! h    if(M<=0 && (a<=0&&b<=0&&c<=0&&d<=0)){cout<<total<<endl;alltotal[pos++]=total;return;}
8 \# i" H1 G* I3 s- Q" P! p! A    for(int i=select[n-1];i<N;i++)
) g  f* t/ g# z* {, k    {
         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))
        {
! L: Y  `+ r- \& W0 a7 V7 e        int ta=a,tb=b,tc=c,td=d;
  z, m4 }" Z# I" ^  [. P( B$ O        int* myselect=new int[n+1];   
        for(int k=0;k<n;k++)myselect[k]=select[k];
! W" W. l) Q, ~        myselect[n]=i;
        if(pcai.hun==1)ta--;else tb--;
; `4 g% L2 `, H$ |# ]        if(pcai.la==1)tc--;else td--;
- i6 b" s& C1 y2 ?) d7 q/ c4 M8 i        fun(myselect,n+1,M-1,ta,tb,tc,td,total+pcai.price);
$ p: k. W0 k" Q2 f        delete[] myselect;
        }
! i  I2 M1 h. o0 _& E7 ?7 Y    }
}

928171481

嗯，不错不错