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

厚积薄发

饭团的烦恼
' d$ U+ W1 j) i4 |  B
* }& q" V; c6 [7 z9 r1 t" d6 z: F- A“午餐饭团“是百度内部参与人数最多的民间组织。
- \% ?8 M3 W* W6 q% h
同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。
+ G3 l# @) a( D# w5 l9 |! u- X; K
; B, G- j$ ~6 s* m; c参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。
$ N' _; F7 U7 F
  R; \" c9 e: p: K) C: K1 s' ~' k但是，随着百度的员工越来越多，各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口，饭团的点菜负责人背负的责任越来越大。现在，这个重担落在百度之星的肩上，因为，你们将要为所有的百度饭团设计一个自动点菜的算法。
0 _; l! a; [0 w7 E  z
饭团点菜的需求如下：
+ O4 n7 L/ i7 h* p8 s
1 ． 经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近 12 元越好。
0 b3 o# ~# D" N- c
0 S: q, ?' ]2 z5 T7 F9 ^0 }* r2 ． 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。

3 ． 请紧记，百度饭团在各大餐馆享受 8 折优惠。
" {2 W, D8 @! p) j/ x$ n! `, p
/ X4 R+ U. P, k& |% i8 w' [输入数据描述如下：

' ?, n5 y% H, x! d9 O+ n第一行包含三个整数 N ， M ， K （ 0<N<=16 ， 0<M<=N ， 0<K<=12 ），分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。

6 o* j' ^" W3 o# l2 g' k紧接着 N 行，每行的格式如下：

菜名（长度不超过 20 个字符） 价格（原价，整数） 是否荤菜（ 1 表示是， 0 表示否） 是否辛辣（ 1 表示是， 0 表示否）

例：

6 h) w3 Q- O* m# ?4 f% W水煮鱼 30 1 1

5 b% c4 L- q/ I$ c紧接着是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。

4 D9 f4 I6 k* I: Y输出数据：

对于每一测试数据，输出数据包含 M+1 行，前 M 行每行包含一个菜名（按菜名在原菜单的顺序排序）。第 M+1 行是人均消费，结果保留两位小数。
0 o6 O4 j% g) P: _: O
说明：

6 c0 R2 Q# S' m6 s( K+ I1 ．结果菜单的数目应该恰好为 M ，荤菜，素菜，辛辣，清淡菜的数目恰好为 a ， b ， c ， d 。在满足这样的前提下，选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。
8 _' E; t  F# @1 _; d7 Y" }
2 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。

输入样例

2 w9 R8 ~3 c+ [) `( y- ^5 [- k3 2 2
  r" ?& R1 s/ o1 t" a
4 r6 j& r; |/ V* p# O' a5 T水煮鱼 30 1 1

! d) }- X1 x% }) @口水鸡 18 1 1
1 d. h7 n- s8 P8 q+ c; v; f. x2 W
清炖豆腐 12 0 0
9 i* E% U; |" X1 s& D% {
/ c) a1 k3 \; T' J- Q/ {1 1 1 1

输出样例

9 M  I: i) C5 W! Y口水鸡

3 U8 m1 k  A7 p/ ?清炖豆腐
/ c8 G" X5 S+ `! |/ d1 Z9 Z
12.00

5 T8 `$ n- I. T' h; z时间要求： 1S 之内
* E) b1 o# ]( }5 Z. F5 l1 i! ~
example：
) E& D. d' U1 D# v- |$ N/ z#include <cstdlib>
9 B) z0 l- \# ^8 ]#include <iostream>

7 Y! p( Q# \- ]: F8 qusing namespace std;

6 g. m. e' b! E7 d" i
struct cai
{
       string cainame;
4 t) g( _$ b! j8 E( p$ p       int price;
6 c6 S. t- Y- g! G7 E7 W$ g/ |       int hun;
2 Q: W: M+ J2 o  S       int la;
6 g  z) x: u2 Y& n: m3 c( J* R       };
int* alltotal=new int[30];
int pos=0;
cai* pcai;
/ `: c4 E8 \$ B* R6 E$ n; }+ K  Wint N=3;  
. }7 o$ X/ X0 V+ C/ Mvoid fun(int * select,int n,int M,int a,int b,int c,int d,int total);
  o0 d6 I1 g8 T) a, ^7 v/ }$ rint main(int argc, char *argv[])
+ s5 S1 }$ K+ o# n1 k{
# l: @3 L4 Y6 n8 |  Z  `1 H: i    int M=2,K=2;
    int a=1,b=1,c=1,d=1;
- l8 Z7 X' f3 j" r! |) r/ E  p, i    pcai = new cai[N];
1 C& A8 U) h- N% [    pcai[0].cainame="water fish";
    pcai[0].hun=1;
- E( }4 f5 S4 d& {9 y) F3 X    pcai[0].la=1;
1 c" d2 z* u/ {7 j/ w; F    pcai[0].price=30;
9 c2 Q  D  D# f6 B4 ^$ V7 A    pcai[1].cainame="mouth fish";
8 A% i( D* n5 c- G8 d0 ?  Q" q& a( j    pcai[1].hun=1;
% `1 }( C) X% |* h' D4 t    pcai[1].la=1;
    pcai[1].price=18;
    pcai[2].cainame="doufu";
& g) G" B/ q9 M7 a2 T    pcai[2].hun=0;
    pcai[2].la=0;
    pcai[2].price=12;
% x, }) ?+ m9 P  f2 Y% L3 I; G: R    for(int i=0;i<N;i++)
" z1 }/ o$ d( D1 K    {
        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;   
5 f& V7 W; U5 w        int* select=new int[1];   
1 q9 W1 M. ^) L% ^! s        select[0]=i;
        if(pcai.hun==1)ta--;else tb--;
, p0 x  v; D& U) V+ P+ I7 E. c1 Z        if(pcai.la==1)tc--;else td--;
% d: Z0 e6 }; ^6 Q! _        fun(select,1,M-1,ta,tb,tc,td,pcai.price);
        delete[] select;
        }
    }
    for(int i=0;i<pos;i++)
4 H; x3 n9 m0 }3 n. e    cout<<alltotal<<endl;
& R4 d9 P+ [: U* C: Y+ _    delete alltotal;
    delete []pcai;
    system("PAUSE");
    return EXIT_SUCCESS;
& Q  p9 a# ~  W. _: A7 k% \: U}
* B- K! d3 `+ x8 `void fun(int * select,int n,int M,int a,int b,int c,int d,int total)
{
4 g6 s1 @" N9 D% c) l) {0 S& i% c    //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;}
; F2 ?% T7 \% U    if(M<=0 && (a<=0&&b<=0&&c<=0&&d<=0)){cout<<total<<endl;alltotal[pos++]=total;return;}
0 F5 B. |! ?* p2 D; w; ?2 V    for(int i=select[n-1];i<N;i++)
5 p6 I  D, G# t$ B; Y    {
         for(int j=0;j<n;j++)if(select[j]==i)continue;
& B8 X% T; K9 d; @( H$ [; H        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))
        {
' b3 W6 y% c) H: c; p9 D        int ta=a,tb=b,tc=c,td=d;
        int* myselect=new int[n+1];   
8 w: ?7 p! w4 d6 Y5 e3 K7 Q1 b        for(int k=0;k<n;k++)myselect[k]=select[k];
        myselect[n]=i;
" g5 E5 O/ ^# o( I! f        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;
        }
* g2 m) }% u9 l; D5 T    }
* ?$ E* D+ ^# ^+ a+ e% o6 V}

928171481

嗯，不错不错