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

厚积薄发

饭团的烦恼
- S  `) u0 [" U: j% u. y
9 V0 E, u3 j) {- e“午餐饭团“是百度内部参与人数最多的民间组织。
$ N1 U3 N6 Q4 q4 R1 Q! Q+ R
0 a8 @8 E! D' i1 _/ A! I" ]# A/ s同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。
  ~4 Y8 u4 m; p
参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。

7 ]# A$ ?% ?- ~% {! C但是，随着百度的员工越来越多，各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口，饭团的点菜负责人背负的责任越来越大。现在，这个重担落在百度之星的肩上，因为，你们将要为所有的百度饭团设计一个自动点菜的算法。
9 P2 U! G! Y! N' k* u# j. d
: m6 c& P% h7 M饭团点菜的需求如下：
# B( U8 F* H; R4 \
1 ． 经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近 12 元越好。
, c) `; k& l- r0 w
7 F/ N( Q0 M/ J; r2 ． 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。
* v& X2 m2 p/ q* k0 X5 m
; A7 A) y4 p. g  O7 X; l9 R3 ． 请紧记，百度饭团在各大餐馆享受 8 折优惠。
% L5 R+ w% H& `. }4 S1 o* I5 b
输入数据描述如下：
! _; i& n& c- u; j! E
第一行包含三个整数 N ， M ， K （ 0<N<=16 ， 0<M<=N ， 0<K<=12 ），分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。
9 u2 u: l3 X0 j# R8 A2 T
紧接着 N 行，每行的格式如下：
  `2 e  I* b1 H8 ~+ ^( y
菜名（长度不超过 20 个字符） 价格（原价，整数） 是否荤菜（ 1 表示是， 0 表示否） 是否辛辣（ 1 表示是， 0 表示否）
3 g3 a, o3 K4 u8 K# y- z2 P
例：
; G) i1 f& e( e& q- W0 y
; L+ K8 j6 }# l% n: u! }9 ~8 A  [1 x水煮鱼 30 1 1

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

& i) L; @* T& Z$ B/ ~# ]输出数据：
' L) Y4 p. t  V* T5 @# n
对于每一测试数据，输出数据包含 M+1 行，前 M 行每行包含一个菜名（按菜名在原菜单的顺序排序）。第 M+1 行是人均消费，结果保留两位小数。
1 x+ \5 Y& m( E5 v" S
( W/ b! {& u7 \+ `8 ], s* v说明：

1 ．结果菜单的数目应该恰好为 M ，荤菜，素菜，辛辣，清淡菜的数目恰好为 a ， b ， c ， d 。在满足这样的前提下，选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。
/ p/ \3 ]' W( W3 X  ]. L1 a, W
2 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。
1 @, ^/ E4 ~* {+ r
2 c, L8 y4 m; R, J4 g# T) r输入样例

- G/ ]. {2 b# {, P0 j( q: R3 2 2
  `2 v  \* W" c4 \% C
0 ]) r! G% p$ y1 N9 f水煮鱼 30 1 1

口水鸡 18 1 1
$ x2 l+ a6 r8 G8 T7 `) n# F
清炖豆腐 12 0 0
$ d" e$ j! c, f* U& Y
, Q% m1 }( H3 _3 N. c1 ~1 1 1 1

6 Y4 z3 v2 |0 B% q输出样例

口水鸡

清炖豆腐
; c9 u5 j( U" i
12.00

) ^0 h+ D8 w, L9 I时间要求： 1S 之内
6 O. i/ R6 n8 J2 R- F7 {! h: P
' R( _" |/ P$ X" c2 K* Gexample：
#include <cstdlib>
% ^) K* I* ]' _+ ~( {#include <iostream>

; T- \3 U2 h( }/ e0 xusing namespace std;

( G' j+ f4 u; ^! `# K# Q5 U. d# k
struct cai
- `1 x7 U+ u& I4 d5 T{
+ E  ~, ^4 }' E8 }+ k       string cainame;
7 H( ~. _$ K& n$ V$ ?       int price;
       int hun;
' j$ J: h+ Z# x: c' }0 S+ o# J& o       int la;
0 J: B6 m2 }6 E8 e: _. b       };
  Z( v/ K% v& kint* alltotal=new int[30];
int pos=0;
cai* pcai;
: ~' \+ K$ r& E. V2 Mint N=3;  
void fun(int * select,int n,int M,int a,int b,int c,int d,int total);
- K# |( n! X5 D/ E% Tint main(int argc, char *argv[])
{
    int M=2,K=2;
    int a=1,b=1,c=1,d=1;
    pcai = new cai[N];
2 O% Y* @4 e; M' p$ c0 n+ b9 K    pcai[0].cainame="water fish";
    pcai[0].hun=1;
9 w+ r3 `, o  A! q9 V8 j" i) U2 j4 O    pcai[0].la=1;
    pcai[0].price=30;
    pcai[1].cainame="mouth fish";
& y% m1 g, u1 K7 q& E    pcai[1].hun=1;
    pcai[1].la=1;
    pcai[1].price=18;
, @: h' g; P* c1 G3 \9 z/ ]    pcai[2].cainame="doufu";
" T* E, ]( ]/ E; ^2 H/ S. ~    pcai[2].hun=0;
    pcai[2].la=0;
    pcai[2].price=12;
    for(int i=0;i<N;i++)
    {
! m9 ]1 C' z" y6 H. u        if( (pcai.hun==1 && a>0) ||(pcai.hun==0 && b>0) || (pcai.la==1 && c>0) || (pcai.la==0 && d>0))
        {
# h$ I+ d  I' ^8 ]! h4 U% ?4 K1 ^        int ta=a,tb=b,tc=c,td=d;   
        int* select=new int[1];   
        select[0]=i;
        if(pcai.hun==1)ta--;else tb--;
5 x. r: Q" M5 M3 i8 S; [8 `        if(pcai.la==1)tc--;else td--;
        fun(select,1,M-1,ta,tb,tc,td,pcai.price);
# K: ~" E7 i! t* ]3 ^5 Q" s        delete[] select;
. h8 A1 D4 J" _5 ?. i        }
3 a# n3 U) @, s/ s    }
+ n, h/ t) O: U& ^( _    for(int i=0;i<pos;i++)
; M1 x6 N; l6 o# n( ]" K+ o    cout<<alltotal<<endl;
& e0 D, ~. y2 [    delete alltotal;
4 \$ y3 ?2 h9 c1 |. H5 E    delete []pcai;
    system("PAUSE");
    return EXIT_SUCCESS;
}
! e- d0 K; B5 F/ C* z9 W! Ovoid 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;
# b' D# F+ o0 d/ w- h    //getchar();
$ G- B# y7 y6 B- V* W$ [6 Y8 E, Z; v    //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;}
    for(int i=select[n-1];i<N;i++)
    {
( Y5 Y2 j, g3 ?+ V* z6 V% _# _         for(int j=0;j<n;j++)if(select[j]==i)continue;
8 c. i3 i, A1 l3 K* T        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))
        {
$ g# }1 R/ g4 [        int ta=a,tb=b,tc=c,td=d;
        int* myselect=new int[n+1];   
) _" ], \. I" W- V- N) Z' i3 A1 Y  A        for(int k=0;k<n;k++)myselect[k]=select[k];
        myselect[n]=i;
        if(pcai.hun==1)ta--;else tb--;
: V- @9 o" m7 K6 q8 C! j/ Q( Z        if(pcai.la==1)tc--;else td--;
3 I+ N" k$ t# `8 Y        fun(myselect,n+1,M-1,ta,tb,tc,td,total+pcai.price);
7 V  T; I8 ~8 t        delete[] myselect;
        }
    }
$ G6 `0 g4 W% {* h$ ?5 b}

928171481

嗯，不错不错