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

厚积薄发

饭团的烦恼
) {6 |- j, F9 l4 s4 k
6 R/ K# K$ H: g3 k/ \9 K“午餐饭团“是百度内部参与人数最多的民间组织。

同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。

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

: O1 l+ T9 J( r' d1 u5 j) O% }9 n) H! D但是，随着百度的员工越来越多，各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口，饭团的点菜负责人背负的责任越来越大。现在，这个重担落在百度之星的肩上，因为，你们将要为所有的百度饭团设计一个自动点菜的算法。
" C; g# y4 C2 [1 t7 W1 l
饭团点菜的需求如下：

1 ． 经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近 12 元越好。
8 g- h  a5 C6 r& g+ L; I8 m
2 ． 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。
6 o3 |# z/ g* m
3 |; o) {3 p. t; o9 }. R: N3 ． 请紧记，百度饭团在各大餐馆享受 8 折优惠。

输入数据描述如下：

第一行包含三个整数 N ， M ， K （ 0<N<=16 ， 0<M<=N ， 0<K<=12 ），分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。

  `3 a6 W4 B2 N/ @2 o6 o; _紧接着 N 行，每行的格式如下：

& K& P$ _% h$ d" n菜名（长度不超过 20 个字符） 价格（原价，整数） 是否荤菜（ 1 表示是， 0 表示否） 是否辛辣（ 1 表示是， 0 表示否）

) x0 E6 }3 U: r- g例：

, j4 e$ \( w4 M9 Z4 K水煮鱼 30 1 1

紧接着是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。
7 F' s4 C" K6 y
输出数据：
: U5 Z. |* h* [1 T6 R3 X
对于每一测试数据，输出数据包含 M+1 行，前 M 行每行包含一个菜名（按菜名在原菜单的顺序排序）。第 M+1 行是人均消费，结果保留两位小数。
" P, F. X: p; H- c6 K! e
说明：
, h7 d  M! S8 N) `; ~/ ^; ]  s
1 ．结果菜单的数目应该恰好为 M ，荤菜，素菜，辛辣，清淡菜的数目恰好为 a ， b ， c ， d 。在满足这样的前提下，选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。
2 Q3 q" b1 E3 R% T3 o0 K
2 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。
. E; h& W5 U( N6 F+ b& a$ C  K
输入样例

7 z3 [/ W  c$ E3 N4 T3 2 2
; B9 v# e; X$ Z1 n
水煮鱼 30 1 1

口水鸡 18 1 1
; m4 L4 u5 y2 R# O
清炖豆腐 12 0 0

* J# x/ w7 z4 Z/ P1 1 1 1

: d2 x' y7 E7 n) o* V& g( o1 L, j
输出样例

口水鸡
. y  Q2 a/ f6 b' `. Y
9 j$ R7 A4 [* O' w. s; l清炖豆腐
' c3 E- x2 E. g  N, J/ I! \4 Y
12.00
) w: s9 Y8 O: E

" E$ b& u- D$ T, k
时间要求： 1S 之内

" r& h3 Y& B. G2 D; z8 Q) xexample：
2 j" a: {$ i% {7 R#include <cstdlib>
  J/ ?, |1 Q% a$ q) q. `#include <iostream>
* \5 S1 n& T2 i. E. @' B
+ j, n$ k! N- d& |& Nusing namespace std;
; E! @6 Z3 _3 s6 ]2 @
( o$ z0 I( _- Y5 a4 d" T
/ C9 m7 u' l) w5 Y& u7 a% R; Fstruct cai
& }5 `- M( ?$ u; S5 r8 h{
       string cainame;
7 d6 v& m! \7 T7 `4 \1 T       int price;
: ]; B7 J. e& \' M; X9 N  v) x, X( f5 Y       int hun;
       int la;
       };
- ]! n5 W( B  e4 v* S4 iint* alltotal=new int[30];
. K7 h1 L( o/ y" b) P' Kint pos=0;
- J8 Z7 W- K# o% p, H8 G. m) R( ?cai* pcai;
4 L6 p) E5 e6 O" X; w& @  U" vint N=3;  
. ]5 f- _0 \9 y* V. j) v: B) xvoid fun(int * select,int n,int M,int a,int b,int c,int d,int total);
' m  ]5 D( ]  {3 ]% ~6 aint main(int argc, char *argv[])
{
    int M=2,K=2;
. D- l1 t: v7 I  ?. ?& L    int a=1,b=1,c=1,d=1;
    pcai = new cai[N];
8 D$ O% y$ j" K5 H- }' c% W/ f2 v5 W    pcai[0].cainame="water fish";
    pcai[0].hun=1;
    pcai[0].la=1;
    pcai[0].price=30;
    pcai[1].cainame="mouth fish";
! }; J% ]/ i# b: x    pcai[1].hun=1;
- A; N6 B. W) W" G: E    pcai[1].la=1;
    pcai[1].price=18;
( a8 ]2 _" E5 Z( j    pcai[2].cainame="doufu";
& w& c; w$ D8 C    pcai[2].hun=0;
    pcai[2].la=0;
    pcai[2].price=12;
+ Z# q- _" ?4 d    for(int i=0;i<N;i++)
( \) r) j! c6 L, [% w% q7 n    {
        if( (pcai.hun==1 && a>0) ||(pcai.hun==0 && b>0) || (pcai.la==1 && c>0) || (pcai.la==0 && d>0))
0 `  Q( m) U+ h) c4 j& v        {
- h, o) e, j# }- P. v0 H        int ta=a,tb=b,tc=c,td=d;   
        int* select=new int[1];   
        select[0]=i;
        if(pcai.hun==1)ta--;else tb--;
& S. O2 X* r8 V/ a/ I( t        if(pcai.la==1)tc--;else td--;
        fun(select,1,M-1,ta,tb,tc,td,pcai.price);
$ r5 C0 v% X1 {4 x2 B# M        delete[] select;
( A6 ?  }4 d& B: i* W. A        }
    }
    for(int i=0;i<pos;i++)
    cout<<alltotal<<endl;
6 n* o, S' g% P7 h$ {/ d: p: v    delete alltotal;
    delete []pcai;
/ A  ~7 [1 k3 ?  b- G3 C0 F    system("PAUSE");
& E( D% W5 b/ ~6 R2 G% i    return EXIT_SUCCESS;
. e# V0 {) h8 D$ `: \' d# [' {; i}
void fun(int * select,int n,int M,int a,int b,int c,int d,int total)
{
; P! h% m# c6 ~, n. p# A, J    //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;
    //getchar();
) C1 s% O, Y/ I0 Y. D( ~    //cout<<n<<"|"<<M<<"|"<<a<<"|"<<b<<"|"<<c<<"|"<<d<<"|"<<total<<"|"<<endl;
7 s; ?/ j- z8 a8 ]$ b1 i    if(M<=0 && (a>0||b>0||c>0||d>0)){cout<<"impossible"<<endl;return;}
    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++)
    {
         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))
' ^+ f6 \) k" k) `        {
        int ta=a,tb=b,tc=c,td=d;
        int* myselect=new int[n+1];   
        for(int k=0;k<n;k++)myselect[k]=select[k];
6 Z; U# l5 K, S: D$ p        myselect[n]=i;
% I( u1 M+ ~% E9 ?        if(pcai.hun==1)ta--;else tb--;
        if(pcai.la==1)tc--;else td--;
1 [8 t: g9 ?8 q        fun(myselect,n+1,M-1,ta,tb,tc,td,total+pcai.price);
0 u- j. s  s! h        delete[] myselect;
$ D/ g. g* q0 y5 F! i! A6 o. c        }
    }
}

928171481

嗯，不错不错