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

厚积薄发

饭团的烦恼

! P6 ]2 `* Z1 b# ~$ A7 n  K“午餐饭团“是百度内部参与人数最多的民间组织。
0 n( u/ Z3 s9 {4 s9 c
8 R# ^3 z6 ?; x: p3 w0 B同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。
& v, Y0 f' i: W6 h- f8 D0 {: ~
参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。

但是，随着百度的员工越来越多，各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口，饭团的点菜负责人背负的责任越来越大。现在，这个重担落在百度之星的肩上，因为，你们将要为所有的百度饭团设计一个自动点菜的算法。
9 B3 c- L7 Z2 a6 N6 k- I
饭团点菜的需求如下：
. N6 i- l& M/ d. \' z7 |* I
1 ． 经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近 12 元越好。
4 ^) y# I; w/ Z$ t+ S8 U' V& z
2 ． 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。
, [$ r+ z5 {$ h" E/ ]
6 |0 A  [# Y0 w3 ． 请紧记，百度饭团在各大餐馆享受 8 折优惠。

输入数据描述如下：
" y  w8 I# S# [2 j
第一行包含三个整数 N ， M ， K （ 0<N<=16 ， 0<M<=N ， 0<K<=12 ），分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。
; M) M) l& N/ A8 ]; g
紧接着 N 行，每行的格式如下：
! w3 v( r4 s& S, a7 J8 w: Z. m
菜名（长度不超过 20 个字符） 价格（原价，整数） 是否荤菜（ 1 表示是， 0 表示否） 是否辛辣（ 1 表示是， 0 表示否）
6 Q, T2 T/ Q7 P. s% p, e! F. ^2 X
例：

水煮鱼 30 1 1

紧接着是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。

输出数据：

对于每一测试数据，输出数据包含 M+1 行，前 M 行每行包含一个菜名（按菜名在原菜单的顺序排序）。第 M+1 行是人均消费，结果保留两位小数。
4 _' A) v9 a1 d! M. a- `% ~( K1 [
8 \0 h: V8 c! }6 l1 b% t+ K  l说明：
0 _3 L1 w9 o" s6 {0 h
1 ．结果菜单的数目应该恰好为 M ，荤菜，素菜，辛辣，清淡菜的数目恰好为 a ， b ， c ， d 。在满足这样的前提下，选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。
. d; M+ s6 x1 C" U0 f( K
2 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。

) h5 R2 e3 C4 S/ b+ k9 ~输入样例

0 f+ b( R; N* O! u% K" b3 2 2

水煮鱼 30 1 1
. D# X1 x! C! J2 U" K  O2 R- z
5 C1 X2 P8 @/ E( P! r口水鸡 18 1 1
5 A; H5 R, V* j& q4 P
7 U8 |0 O( W5 K清炖豆腐 12 0 0

1 1 1 1

2 a/ r! f5 ^2 a0 k2 j0 E  g% G: X
输出样例

! X; J  Q0 i9 P# g口水鸡
: L$ Z) \$ K) [9 ^4 q* d) W
+ T& @1 J) Z/ w+ w0 p8 {清炖豆腐
2 S' ^! k2 \) S. r$ |. ]$ ]) L7 Z. t8 U
( @) ~7 t3 W, ~12.00

9 t& N* o4 Q4 X. z5 e
时间要求： 1S 之内
6 `' o0 {# p- ~3 F0 n0 V
; r; h3 x; ~5 {" G, |example：
2 M$ j. n4 G, l' y  l) u4 z#include <cstdlib>
+ F' V* ]$ ^# P: o/ t" s( }#include <iostream>

using namespace std;
) t( l& {0 L" Q5 m

struct cai
{
       string cainame;
0 v( B1 z- ?7 I$ u% e# A4 s7 G% k       int price;
       int hun;
' k' v  n8 j4 J3 W% r0 {6 e       int la;
& j" a- X1 s9 F3 {& E" V# f0 [2 y       };
int* alltotal=new int[30];
6 `2 H- H6 C5 Q, K, Tint pos=0;
cai* pcai;
+ G. |* o7 e7 j9 h/ N, Vint N=3;  
; q4 j" |- y7 qvoid fun(int * select,int n,int M,int a,int b,int c,int d,int total);
8 g% a' U, d* H8 L7 w9 nint main(int argc, char *argv[])
) U5 ^. z0 k0 `3 D) m{
    int M=2,K=2;
    int a=1,b=1,c=1,d=1;
' w' @% W" ^. g. c    pcai = new cai[N];
) ^4 b& n$ b0 ^, \  H* J    pcai[0].cainame="water fish";
    pcai[0].hun=1;
    pcai[0].la=1;
    pcai[0].price=30;
7 A' c0 D7 ^) n+ d    pcai[1].cainame="mouth fish";
  y( z) }4 w" X7 C    pcai[1].hun=1;
    pcai[1].la=1;
    pcai[1].price=18;
; [* o% L- }. U  I, Z2 K    pcai[2].cainame="doufu";
    pcai[2].hun=0;
    pcai[2].la=0;
2 H+ ~) Y* W" [- s! F    pcai[2].price=12;
+ a2 V6 S: O) x2 `+ y6 J5 \- d, V9 P    for(int i=0;i<N;i++)
7 O9 d- m: K. C( u    {
        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;   
& x5 E( \% }3 |2 W2 v9 l( K        int* select=new int[1];   
        select[0]=i;
        if(pcai.hun==1)ta--;else tb--;
6 D4 G; j5 f! L8 V' F, d        if(pcai.la==1)tc--;else td--;
        fun(select,1,M-1,ta,tb,tc,td,pcai.price);
        delete[] select;
        }
1 x* _8 K4 C- |8 d    }
# p$ P- K+ f1 S    for(int i=0;i<pos;i++)
    cout<<alltotal<<endl;
) A  k* G  @$ c0 ?7 P1 s    delete alltotal;
( u' }3 K" K+ m# e0 Y    delete []pcai;
    system("PAUSE");
    return EXIT_SUCCESS;
& @+ @& c! n7 h}
6 E0 w/ M) }) [void fun(int * select,int n,int M,int a,int b,int c,int d,int total)
$ U* U6 r, ~6 B6 S1 i" ~{
" D; V2 I0 x4 s+ b: V! J- p    //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;
    //getchar();
! H" d0 ~" y2 r7 ]: w# K) X9 R    //cout<<n<<"|"<<M<<"|"<<a<<"|"<<b<<"|"<<c<<"|"<<d<<"|"<<total<<"|"<<endl;
    if(M<=0 && (a>0||b>0||c>0||d>0)){cout<<"impossible"<<endl;return;}
8 V5 x+ L; p' _4 G5 v: k$ m+ e4 m    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++)
; g7 T0 ^3 w3 j$ `, v    {
: s5 }6 x1 o! j2 t  n         for(int j=0;j<n;j++)if(select[j]==i)continue;
$ Y9 ~8 ]+ l+ e* ]+ d        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;
. e$ M3 g& r1 ^# `* A) O7 n, _9 p        int* myselect=new int[n+1];   
- O" P$ J$ Y- o& ]+ t% v( D1 Q$ _/ s        for(int k=0;k<n;k++)myselect[k]=select[k];
* u9 i! f& F" v) j2 H9 F8 Z. Z7 o        myselect[n]=i;
        if(pcai.hun==1)ta--;else tb--;
        if(pcai.la==1)tc--;else td--;
        fun(myselect,n+1,M-1,ta,tb,tc,td,total+pcai.price);
        delete[] myselect;
( c6 l2 @+ v9 b3 f7 i        }
    }
}

928171481

嗯，不错不错