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

厚积薄发

饭团的烦恼

“午餐饭团“是百度内部参与人数最多的民间组织。

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

5 R  L+ {2 H* ?4 M( q3 S7 B- i参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。

但是，随着百度的员工越来越多，各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口，饭团的点菜负责人背负的责任越来越大。现在，这个重担落在百度之星的肩上，因为，你们将要为所有的百度饭团设计一个自动点菜的算法。
. B, T2 A# V( t  n4 u9 X  `
1 z7 @* v) D. ]. x3 G饭团点菜的需求如下：

# i9 S6 f& w9 v1 ． 经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近 12 元越好。
, G5 H/ z* R" A) q
1 n- K9 y* q' n- O! n8 V0 O2 ． 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。
9 F  G0 Q& E: [6 G8 W! K: b
3 ． 请紧记，百度饭团在各大餐馆享受 8 折优惠。

7 w: A: ?2 q1 G! G# P输入数据描述如下：
9 D/ a$ D; p4 [+ W" Q# q8 M* s
第一行包含三个整数 N ， M ， K （ 0<N<=16 ， 0<M<=N ， 0<K<=12 ），分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。

紧接着 N 行，每行的格式如下：
- ], A1 e* @9 V& ^% _
% n7 }7 r0 d! y4 `菜名（长度不超过 20 个字符） 价格（原价，整数） 是否荤菜（ 1 表示是， 0 表示否） 是否辛辣（ 1 表示是， 0 表示否）

3 S1 Z. V, N4 F9 f1 h$ j7 T例：

  K: ?4 {3 \3 ~% ~+ p4 j# \  j3 G水煮鱼 30 1 1

紧接着是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。
$ O# J0 j, y9 W: `) x
输出数据：

对于每一测试数据，输出数据包含 M+1 行，前 M 行每行包含一个菜名（按菜名在原菜单的顺序排序）。第 M+1 行是人均消费，结果保留两位小数。
  N$ B! b' Z& H7 z: }
* [0 H* {0 l% p3 `7 `说明：

  V. r7 k1 ]3 h5 x8 x# S2 J1 ．结果菜单的数目应该恰好为 M ，荤菜，素菜，辛辣，清淡菜的数目恰好为 a ， b ， c ， d 。在满足这样的前提下，选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。
3 Y# e# l2 W# \" @
2 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。

输入样例

& E1 o; X7 t  l. K6 Y" x3 2 2

- d3 F) }$ V# R, {* {水煮鱼 30 1 1

4 R& }3 z4 T& i0 Y  h口水鸡 18 1 1
- S+ p2 f' a/ d7 H8 r( l
清炖豆腐 12 0 0

1 1 1 1
0 S, t7 p6 N( Y3 C) K4 w) R

9 I. e! W5 x, h0 g) D) K
输出样例

口水鸡
; f7 G* [+ ?% ^& W$ A
清炖豆腐

; X# K% \- w# ]7 Y! k1 d* X12.00

, T! Z& f0 R" B. P, d/ e
# [! Q3 s. w& o/ U时间要求： 1S 之内

* {6 j, W3 l" k) i+ B; eexample：
#include <cstdlib>
#include <iostream>

( T( J, M% q+ Y6 Ousing namespace std;

5 Y( g* ?2 E. ?; F8 L9 i  p
/ e7 z1 f9 L, c1 ]. _2 `8 a2 Tstruct cai
: v$ c- P2 b6 Q- C0 V{
       string cainame;
       int price;
       int hun;
       int la;
& _% u( s" o$ a6 I6 v6 e6 g       };
int* alltotal=new int[30];
int pos=0;
' h# Q8 o. g: \3 x4 y, r, u8 Scai* pcai;
2 ~" i5 P2 V9 t( n* S1 ^9 ]int N=3;  
void fun(int * select,int n,int M,int a,int b,int c,int d,int total);
  B2 z0 X$ U+ E7 bint main(int argc, char *argv[])
7 r! p5 E8 {! v/ l# [$ K{
% }! J, q7 X; T# F/ c    int M=2,K=2;
    int a=1,b=1,c=1,d=1;
    pcai = new cai[N];
    pcai[0].cainame="water fish";
, L+ E' P, b+ R$ W4 G/ L0 S5 I, ?    pcai[0].hun=1;
    pcai[0].la=1;
; M/ Y* [+ O3 H' T    pcai[0].price=30;
    pcai[1].cainame="mouth fish";
- }. p, d3 `1 v    pcai[1].hun=1;
: ]3 w: E2 ~1 p    pcai[1].la=1;
- T. i  U( j- M; {& |' K    pcai[1].price=18;
/ y: q( s. u3 o    pcai[2].cainame="doufu";
    pcai[2].hun=0;
    pcai[2].la=0;
    pcai[2].price=12;
    for(int i=0;i<N;i++)
; `8 }: T% A0 z! }# m3 f0 ~    {
, _3 W3 k/ @( ]' j* j        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;   
        int* select=new int[1];   
        select[0]=i;
        if(pcai.hun==1)ta--;else tb--;
        if(pcai.la==1)tc--;else td--;
$ Z  U' S: I) n7 K        fun(select,1,M-1,ta,tb,tc,td,pcai.price);
        delete[] select;
$ ?. {6 i1 i* v5 }. e8 B        }
    }
% `( W# _. R' {4 v$ U    for(int i=0;i<pos;i++)
    cout<<alltotal<<endl;
    delete alltotal;
* F2 t# y$ R& `( s) E/ r( a6 l    delete []pcai;
    system("PAUSE");
    return EXIT_SUCCESS;
}
; `! P- l: a3 Y* k- v# O9 O; ?void fun(int * select,int n,int M,int a,int b,int c,int d,int total)
* ?* q: M& C( J6 _; Y{
- B4 v+ H9 b3 h2 s    //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;
/ ]1 E# N9 n1 i: ^$ L, D    //getchar();
    //cout<<n<<"|"<<M<<"|"<<a<<"|"<<b<<"|"<<c<<"|"<<d<<"|"<<total<<"|"<<endl;
2 R5 N1 V, j3 R4 h# q    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++)
+ H. _- C" e: l3 Q    {
         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))
        {
, X5 S7 o; a5 k- a        int ta=a,tb=b,tc=c,td=d;
        int* myselect=new int[n+1];   
# m) o% ]" W% M- c        for(int k=0;k<n;k++)myselect[k]=select[k];
        myselect[n]=i;
8 ~0 N2 [3 X  u        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;
" @. C  {7 L' u/ j# N% W6 c        }
    }
}

928171481

嗯，不错不错