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

厚积薄发

饭团的烦恼
2 i& l6 a/ e  x5 {4 Z0 y. {
# z" t% K0 _3 _8 ^: z' {“午餐饭团“是百度内部参与人数最多的民间组织。
4 h6 R( B; C! x2 L; ~7 N: d
同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。

参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。
" M; f( F$ m' i$ `: U  J
但是，随着百度的员工越来越多，各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口，饭团的点菜负责人背负的责任越来越大。现在，这个重担落在百度之星的肩上，因为，你们将要为所有的百度饭团设计一个自动点菜的算法。

饭团点菜的需求如下：

9 t7 V& o( t( p. h! j( P3 m: S1 ． 经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近 12 元越好。
, |7 D9 ?; T9 D3 I
2 ． 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。
  e# }' q4 G* P0 _% X
3 ． 请紧记，百度饭团在各大餐馆享受 8 折优惠。
) k  m9 r1 d* I) X
输入数据描述如下：
6 |8 N  T2 {& P8 L% |9 _9 |
第一行包含三个整数 N ， M ， K （ 0<N<=16 ， 0<M<=N ， 0<K<=12 ），分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。
9 H) a; p6 F* Z1 t2 e0 r' Z$ I8 M8 x
. S7 X8 w" ?) u紧接着 N 行，每行的格式如下：

4 A) u: Q( y6 _9 A. U: G' N菜名（长度不超过 20 个字符） 价格（原价，整数） 是否荤菜（ 1 表示是， 0 表示否） 是否辛辣（ 1 表示是， 0 表示否）

, c: `8 S. S# c# W$ a例：

水煮鱼 30 1 1

紧接着是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。
6 W2 ?( S3 h! I- }$ k
2 X  d+ i, Z$ H- J) r0 U输出数据：

对于每一测试数据，输出数据包含 M+1 行，前 M 行每行包含一个菜名（按菜名在原菜单的顺序排序）。第 M+1 行是人均消费，结果保留两位小数。
" G7 `% R: ?- R. @' m$ `. |3 Z7 Q
* e9 r( P* j4 p( }8 u/ w说明：

  z$ N. H/ U$ Q  P  U! @1 ．结果菜单的数目应该恰好为 M ，荤菜，素菜，辛辣，清淡菜的数目恰好为 a ， b ， c ， d 。在满足这样的前提下，选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。
. K) R1 ?% u! ?( e3 R( T, u) E
2 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。
, ^4 z: M1 o7 k/ I  b# u1 E" D
: S  r% z: {3 o. j4 D/ }" u输入样例

: i0 \; \0 O- d7 q+ Y2 w9 e$ Y3 2 2
" Q% A1 C+ a: ?. i" a. ~
水煮鱼 30 1 1
3 D- x( e* e  O# Z6 H* R; d" R
口水鸡 18 1 1
$ D3 s/ g* A# T! Z8 q
清炖豆腐 12 0 0
4 c7 g4 U. }( b
+ t# u6 f& \1 m' I0 i9 V1 1 1 1

输出样例

( B" {  K% O8 t" ]+ G  |$ G2 a口水鸡

清炖豆腐

' u: n# n5 Y. y4 w- A/ S7 q12.00

3 {: x2 X9 ~& \

( \# i. t7 H5 Q& v$ B时间要求： 1S 之内

8 ^: ^* g# e2 d2 i2 H" I9 eexample：
#include <cstdlib>
1 W  V# a6 W6 K# N4 n#include <iostream>

9 H: o. ]! Z2 I2 A) Y8 G: U  }using namespace std;
, T& A8 `/ `: _9 q1 r# R! c
' g8 h! h- Y8 Y0 O  L/ ^' V
8 V- I( L) E7 C# @7 astruct cai
% N6 N- h3 L$ _' f{
. o5 f+ `' U6 T. u* s8 Q0 W       string cainame;
/ O/ @3 j; E( n& N; W9 w$ S7 O* C       int price;
  b* C+ F9 v$ k! l. ~/ j       int hun;
3 f! B4 F8 \" o0 ?# {  |       int la;
       };
int* alltotal=new int[30];
# e% ?# U4 b6 i9 t5 ]int pos=0;
: J9 T5 W, @0 y: ncai* pcai;
1 B8 g5 y" R; C3 A3 Oint N=3;  
. }: b* Y5 b" e1 k' w3 D4 @void fun(int * select,int n,int M,int a,int b,int c,int d,int total);
int main(int argc, char *argv[])
{
    int M=2,K=2;
5 M  K/ H" q) W    int a=1,b=1,c=1,d=1;
# Z$ N' `8 M9 J& A# r    pcai = new cai[N];
4 Y2 M# v( G4 {3 f3 b) S' ]4 u    pcai[0].cainame="water fish";
    pcai[0].hun=1;
/ l/ A- J# c) o7 u    pcai[0].la=1;
    pcai[0].price=30;
    pcai[1].cainame="mouth fish";
    pcai[1].hun=1;
    pcai[1].la=1;
    pcai[1].price=18;
    pcai[2].cainame="doufu";
7 \2 B0 b' N1 K1 J& d) F    pcai[2].hun=0;
; \4 D0 }( {7 K7 ]$ `    pcai[2].la=0;
    pcai[2].price=12;
    for(int i=0;i<N;i++)
: c5 y) ]0 l" y! v" {7 E    {
4 k' M6 n! V4 S, Y        if( (pcai.hun==1 && a>0) ||(pcai.hun==0 && b>0) || (pcai.la==1 && c>0) || (pcai.la==0 && d>0))
- a5 h) [# o/ ?& h! L, v: P, D        {
        int ta=a,tb=b,tc=c,td=d;   
: o( [3 Z, _) Z7 w        int* select=new int[1];   
        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;
  C8 ~- F8 n7 H1 O# o; ?4 k! N        }
7 y# q# ]% a  Z. D" n# \    }
3 S  A) H* E) i; Q9 y    for(int i=0;i<pos;i++)
    cout<<alltotal<<endl;
# d0 n1 f6 @. t3 C" s2 R: {    delete alltotal;
    delete []pcai;
    system("PAUSE");
    return EXIT_SUCCESS;
}
void fun(int * select,int n,int M,int a,int b,int c,int d,int total)
2 h$ ]' ~- z2 ?; r, E. x/ o{
    //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;
0 P" Z1 ^0 z% G0 H' _$ u8 v5 q2 _    //getchar();
    //cout<<n<<"|"<<M<<"|"<<a<<"|"<<b<<"|"<<c<<"|"<<d<<"|"<<total<<"|"<<endl;
' t4 K- l/ [. k5 R7 P' L; m    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;}
7 Y2 _/ f, E0 Y2 @: e    for(int i=select[n-1];i<N;i++)
9 O- z' u4 M" B  \+ h- x    {
; T" T/ F2 _9 d+ ~1 [# [/ V, r         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))
7 |7 P. b! Y/ f9 f        {
3 x% h% Z: @/ o, x3 Z, k( E# ~+ E" P        int ta=a,tb=b,tc=c,td=d;
        int* myselect=new int[n+1];   
& x( x* q6 C3 n4 V( D, z9 u        for(int k=0;k<n;k++)myselect[k]=select[k];
        myselect[n]=i;
        if(pcai.hun==1)ta--;else tb--;
        if(pcai.la==1)tc--;else td--;
  ?/ Z/ u, K/ N        fun(myselect,n+1,M-1,ta,tb,tc,td,total+pcai.price);
        delete[] myselect;
8 G0 F; [& `: I, @* U        }
. U, v9 ?, f! x7 X' A: Q    }
1 u2 Z; X4 h6 e5 H0 w6 R}

928171481

嗯，不错不错