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

厚积薄发

饭团的烦恼
' m& Z* e, i! R* g2 _
“午餐饭团“是百度内部参与人数最多的民间组织。

同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。
4 w5 @; {& @2 U0 s+ v: O
7 J; q' @- m+ q8 b% U. ~参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。
6 c2 i9 ]6 j8 I1 q
& D( \- B- u% X2 _; b# [但是，随着百度的员工越来越多，各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口，饭团的点菜负责人背负的责任越来越大。现在，这个重担落在百度之星的肩上，因为，你们将要为所有的百度饭团设计一个自动点菜的算法。
. F- L, s& L7 n9 {
' L! v8 Z. g# g1 X! \饭团点菜的需求如下：

& t6 w+ t3 ?; k5 O0 ?% b) S1 ． 经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近 12 元越好。

  [( {: p0 ^. i  }& k5 i, V1 y2 ． 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。

( o( [9 I& u# L  ]2 B3 ． 请紧记，百度饭团在各大餐馆享受 8 折优惠。
: k" C2 p# c% y5 I  ^1 |
. H9 ~6 l7 g: T  B' @9 C+ d输入数据描述如下：

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

4 ^1 Q0 ~9 C3 s& K2 J9 f1 V紧接着 N 行，每行的格式如下：

# {: ~. W: R5 q0 y6 _菜名（长度不超过 20 个字符） 价格（原价，整数） 是否荤菜（ 1 表示是， 0 表示否） 是否辛辣（ 1 表示是， 0 表示否）
9 e- c; q! @9 M8 L% w9 l( P; j& P
例：

) X2 u, M( S  h& h5 U6 i水煮鱼 30 1 1

紧接着是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。
4 S+ }9 `. u! q
输出数据：

对于每一测试数据，输出数据包含 M+1 行，前 M 行每行包含一个菜名（按菜名在原菜单的顺序排序）。第 M+1 行是人均消费，结果保留两位小数。
; f9 P) E6 d3 C( x
+ O6 a9 W8 _$ P2 x% i1 |+ ?' p说明：
( H, @( Y2 F2 v: g# K
1 ．结果菜单的数目应该恰好为 M ，荤菜，素菜，辛辣，清淡菜的数目恰好为 a ， b ， c ， d 。在满足这样的前提下，选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。
6 h4 k) w; p3 O( N- Y" f, c! Y
6 U% \6 p1 q8 ]4 [- T2 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。

% c: i  D% G% y+ g- I3 f7 t9 d输入样例

3 2 2
# h! {9 t9 s% |
! S  |& f" x& _& `水煮鱼 30 1 1
0 l4 w& W! i- h
7 x) h3 @% s7 E! J口水鸡 18 1 1

# u  E9 H- T2 T" ~" l8 |$ W9 t清炖豆腐 12 0 0

1 1 1 1

4 q" c9 f6 N' E6 t: [) O
8 J/ Z+ ]9 N, ~% l输出样例

口水鸡
: ]3 f, ~# }2 I7 I0 j( D# y( p+ z  j# h
+ c: q7 D) d$ T- n  q清炖豆腐
; t! G' s( O! h
1 y0 D- T* p8 q, @! M/ S% H/ v, e12.00
2 Y0 s! T8 o! W! \! |

. e1 ~1 V/ s" h! s$ e& F: P
# I( h8 I' ?5 p( _/ r9 k时间要求： 1S 之内

; Z/ o0 f. n; \1 r7 ^0 Dexample：
" Q1 f8 B4 g, _$ I8 x+ `# }#include <cstdlib>
" B/ S9 Y' f  J% t. A/ e' v1 F#include <iostream>
3 q2 [4 p! O$ H% a  s7 Z
using namespace std;
# G9 q- @1 D: I- s% y% b

" l/ k, o) ^' v, }" S5 {. T! Astruct cai
{
! S( t4 q  }" o( ?/ w       string cainame;
2 J/ Q) u6 h" B5 y# q       int price;
       int hun;
2 |9 d! r6 C) u, A( Y$ n- d       int la;
4 ?* U6 f4 e) L5 ~       };
% A. J( z! E7 `- aint* alltotal=new int[30];
int pos=0;
. d) l- c% B% I8 N; }2 Rcai* pcai;
. ^. m  t0 a7 e: eint N=3;  
/ E* O! i! G- K, n1 K& Evoid fun(int * select,int n,int M,int a,int b,int c,int d,int total);
, K% A- f& t( M' u2 Pint main(int argc, char *argv[])
{
    int M=2,K=2;
    int a=1,b=1,c=1,d=1;
9 J6 O6 g8 k2 c* l6 h: F) c    pcai = new cai[N];
  v7 O- w. }+ m- p: ^6 l7 Y    pcai[0].cainame="water fish";
" Y# m  L9 ^& G( g    pcai[0].hun=1;
. t( N6 N5 t2 l/ v* r* y    pcai[0].la=1;
    pcai[0].price=30;
    pcai[1].cainame="mouth fish";
  K5 G. [$ _# q- D7 t, E$ ^+ _    pcai[1].hun=1;
    pcai[1].la=1;
    pcai[1].price=18;
, F1 C% y! ^0 Y    pcai[2].cainame="doufu";
    pcai[2].hun=0;
2 s. b# Q- y1 ^$ j    pcai[2].la=0;
    pcai[2].price=12;
6 q  ~2 U& C9 U7 |    for(int i=0;i<N;i++)
    {
4 |, h# o+ M0 t; U        if( (pcai.hun==1 && a>0) ||(pcai.hun==0 && b>0) || (pcai.la==1 && c>0) || (pcai.la==0 && d>0))
        {
, [  L( k" Z( h( J  [% s  s- O        int ta=a,tb=b,tc=c,td=d;   
6 }% v# d. u5 Y( k        int* select=new int[1];   
; F, n1 I0 b5 c+ s0 n        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);
        delete[] select;
        }
    }
4 [  |7 \3 P6 t; @  I    for(int i=0;i<pos;i++)
* v  v. P4 N! X% F8 Q$ C  U    cout<<alltotal<<endl;
4 f# h; {( |. I2 d    delete alltotal;
4 r( \% [. z0 U3 Q    delete []pcai;
    system("PAUSE");
! B5 k9 o+ W! C    return EXIT_SUCCESS;
}
) x! P" Z, [& h9 b% y- y- d# i/ w+ y) rvoid fun(int * select,int n,int M,int a,int b,int c,int d,int total)
{
    //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;
    //getchar();
    //cout<<n<<"|"<<M<<"|"<<a<<"|"<<b<<"|"<<c<<"|"<<d<<"|"<<total<<"|"<<endl;
    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;}
9 t/ I' L% ]2 n4 U' L    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))
        {
        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];
        myselect[n]=i;
        if(pcai.hun==1)ta--;else tb--;
9 \5 m8 W5 U3 C! s, d        if(pcai.la==1)tc--;else td--;
: S( h) V: \) ^        fun(myselect,n+1,M-1,ta,tb,tc,td,total+pcai.price);
        delete[] myselect;
        }
& R7 u8 S# F+ p# [, [# |7 U- _    }
}

928171481

嗯，不错不错