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

厚积薄发

饭团的烦恼

“午餐饭团“是百度内部参与人数最多的民间组织。
# K2 T7 S. h8 R5 C$ _
同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。

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

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

+ P* J, ]* g1 ]$ ~6 R+ O: C$ C2 @饭团点菜的需求如下：

5 @7 f0 k$ D/ ~, y2 }. `1 ． 经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近 12 元越好。

1 m' M; l; s% V/ v2 ． 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。

3 ． 请紧记，百度饭团在各大餐馆享受 8 折优惠。

) Z; s4 Q: w; S! ^输入数据描述如下：

4 H! N5 Z# y* H5 n  [第一行包含三个整数 N ， M ， K （ 0<N<=16 ， 0<M<=N ， 0<K<=12 ），分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。

& w$ H. F- K( }/ B2 w紧接着 N 行，每行的格式如下：

9 R% z2 O& u: \( g' U  x菜名（长度不超过 20 个字符） 价格（原价，整数） 是否荤菜（ 1 表示是， 0 表示否） 是否辛辣（ 1 表示是， 0 表示否）
' @3 L" r) |2 R2 ?$ }
. V+ c; Q' {; B, d例：
9 |) |, R$ u* ~# g: R
水煮鱼 30 1 1
3 V% w8 y# ]7 m* H
紧接着是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。
# y# Q' J8 A' ?. H9 e; R& f, O
- r* {/ q3 x) ?  V2 q0 y/ l7 _输出数据：
  P7 p( D, P8 ?
: d* y" B0 o. N5 w0 w7 X5 z+ s# p对于每一测试数据，输出数据包含 M+1 行，前 M 行每行包含一个菜名（按菜名在原菜单的顺序排序）。第 M+1 行是人均消费，结果保留两位小数。

说明：

" b, c8 m- g6 p  N2 ]1 ．结果菜单的数目应该恰好为 M ，荤菜，素菜，辛辣，清淡菜的数目恰好为 a ， b ， c ， d 。在满足这样的前提下，选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。
! R; f! V6 a4 y; q3 \) D0 `
2 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。

2 J& j' G' m% F; F9 g输入样例

! n0 ]: \6 P$ L3 g8 K3 2 2
% X- |- k* ?: q4 u0 T
$ r. {+ i- R0 ?! |水煮鱼 30 1 1
) ^5 ?. L0 n( i5 M5 a+ w; J
1 q) l5 a6 b9 V/ z7 g& C口水鸡 18 1 1
5 X$ P2 m0 M* p% e6 r- f
* U* b6 D: j) y% c: G清炖豆腐 12 0 0
9 |! }- J$ M$ z. N8 K" _
# D) w2 E' E+ ?. b. v% I2 B1 1 1 1
7 f  {: O) c6 U. y; V7 j0 f0 F

# H9 R% Y; q4 r4 c
; Y2 e" J; ]1 C$ B* \9 \. v输出样例

口水鸡
3 @/ H, L" M; k
清炖豆腐

12.00
1 r% k* C7 w/ M8 M0 }6 P: Z& Y

  ~, _  x/ R/ F( g, }- g; J# K时间要求： 1S 之内

7 F1 K$ I9 ^) l7 Z" N+ U1 ?example：
. L& b" v; |# G! K4 |#include <cstdlib>
#include <iostream>
7 o! D8 F3 ^2 _+ i  J. L
+ m: w( N: G: x6 l5 R) Z5 V; Qusing namespace std;
# Q* y* @7 S3 T
; Y# R! _$ [4 f7 d' t8 R4 f
struct cai
! d/ Y# c  F6 U9 [5 l{
       string cainame;
       int price;
       int hun;
       int la;
" ^& D  o* D& ~7 X/ d       };
1 `, s3 ]1 J, E+ \  k/ aint* alltotal=new int[30];
) Y/ _( Q% {- {8 ~/ S  @: Aint pos=0;
" G& S! B& S# S5 B9 O( tcai* pcai;
int N=3;  
void fun(int * select,int n,int M,int a,int b,int c,int d,int total);
1 J9 K) s3 C1 Yint main(int argc, char *argv[])
3 e/ k% z4 d4 x4 C9 M* V. s/ s{
    int M=2,K=2;
6 s( j  I4 a) o    int a=1,b=1,c=1,d=1;
    pcai = new cai[N];
    pcai[0].cainame="water fish";
0 q, {" E& U. d9 i* O    pcai[0].hun=1;
* q( D+ X7 R! _( ]$ x2 |4 |3 i5 ~' i    pcai[0].la=1;
    pcai[0].price=30;
" [8 z& ?5 r  r4 E    pcai[1].cainame="mouth fish";
    pcai[1].hun=1;
) `" E' K6 z6 i$ h  A% Q# U8 ?    pcai[1].la=1;
    pcai[1].price=18;
; @: _6 @3 p+ @- P% R- G, H    pcai[2].cainame="doufu";
    pcai[2].hun=0;
/ ^8 @2 t  q5 o$ W    pcai[2].la=0;
    pcai[2].price=12;
    for(int i=0;i<N;i++)
+ _. @- F* e+ E; p& D    {
        if( (pcai.hun==1 && a>0) ||(pcai.hun==0 && b>0) || (pcai.la==1 && c>0) || (pcai.la==0 && d>0))
        {
  j6 @, F9 }" Y  p* \        int ta=a,tb=b,tc=c,td=d;   
+ a3 c; r" F/ G0 v# z        int* select=new int[1];   
8 j( R7 e' K% v6 y8 v% N7 ]- D% Y        select[0]=i;
        if(pcai.hun==1)ta--;else tb--;
        if(pcai.la==1)tc--;else td--;
        fun(select,1,M-1,ta,tb,tc,td,pcai.price);
8 `4 y# l. S) w. F0 v( a        delete[] select;
4 ~! Y+ v9 X2 u6 t' h) x        }
    }
    for(int i=0;i<pos;i++)
- a( @# }( a% A- u    cout<<alltotal<<endl;
    delete alltotal;
, ]/ A% d* F7 C0 `/ e5 t    delete []pcai;
    system("PAUSE");
    return EXIT_SUCCESS;
$ {6 W4 \: S6 q/ e5 q% ~}
0 B2 \) o8 h: U1 ]void fun(int * select,int n,int M,int a,int b,int c,int d,int total)
{
# `! G. [, t5 z  A) N    //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;
    //getchar();
/ ]0 y; b% J3 O, z* M9 ~6 P6 ?    //cout<<n<<"|"<<M<<"|"<<a<<"|"<<b<<"|"<<c<<"|"<<d<<"|"<<total<<"|"<<endl;
# ^$ F' u5 Y. Z    if(M<=0 && (a>0||b>0||c>0||d>0)){cout<<"impossible"<<endl;return;}
8 R" m0 q8 g+ L/ R& P5 l9 L    if(M<=0 && (a<=0&&b<=0&&c<=0&&d<=0)){cout<<total<<endl;alltotal[pos++]=total;return;}
    for(int i=select[n-1];i<N;i++)
5 K, S; f" _' L, Q6 r" u! }    {
         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))
# Q3 C4 e4 ~5 `+ w/ l6 ^        {
1 s2 f: T& t# c% m6 {$ |: ~4 V6 s        int ta=a,tb=b,tc=c,td=d;
2 ~1 T% V' G8 u* z' x        int* myselect=new int[n+1];   
! z' q" j8 Z( Q- x        for(int k=0;k<n;k++)myselect[k]=select[k];
        myselect[n]=i;
8 ?6 Y3 Z5 g: K5 G" f1 p; l# h        if(pcai.hun==1)ta--;else tb--;
        if(pcai.la==1)tc--;else td--;
) x$ N( o; A8 Z: m3 i        fun(myselect,n+1,M-1,ta,tb,tc,td,total+pcai.price);
: Y. o: N3 }/ W% y        delete[] myselect;
        }
    }
2 }0 b- r: J; h5 c: v# ]' H5 d# C+ H}

928171481

嗯，不错不错