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

厚积薄发

饭团的烦恼
. L2 ?% T# }# V5 a
“午餐饭团“是百度内部参与人数最多的民间组织。
3 K  c& P. s9 k$ L; @: m$ b5 U
同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。
& d+ m5 Z  P( ~* D* o, k
1 \9 q$ p: a$ S6 r1 b, L- s参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。
# _% K; j6 @+ @* E4 i
但是，随着百度的员工越来越多，各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口，饭团的点菜负责人背负的责任越来越大。现在，这个重担落在百度之星的肩上，因为，你们将要为所有的百度饭团设计一个自动点菜的算法。

3 q' b% m" u. T; K饭团点菜的需求如下：
) D/ L/ Y1 m# D! A: i# D
1 ． 经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近 12 元越好。

) C7 a& k( x$ s. I; ]7 e: ^2 ． 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。
/ O% `2 C% U- [$ ~8 j
3 ． 请紧记，百度饭团在各大餐馆享受 8 折优惠。
+ ^; X5 \! h+ Z9 Z
输入数据描述如下：

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

: ]2 F, v9 F6 ?$ N紧接着 N 行，每行的格式如下：
' ~$ O; @8 j0 ~0 V
菜名（长度不超过 20 个字符） 价格（原价，整数） 是否荤菜（ 1 表示是， 0 表示否） 是否辛辣（ 1 表示是， 0 表示否）

例：

. L& m2 z3 h; Y% {9 {水煮鱼 30 1 1

3 m+ X  _+ u" E& O紧接着是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。
3 u# c7 H+ T$ ^  p) N! @( C
! a3 B+ p+ h& o2 F& k输出数据：
4 U* `" H& X3 L# Q
* p) [3 S* a7 D, Y; r6 d对于每一测试数据，输出数据包含 M+1 行，前 M 行每行包含一个菜名（按菜名在原菜单的顺序排序）。第 M+1 行是人均消费，结果保留两位小数。
$ z' [6 l8 i3 o- _' ~. K" t3 ]
说明：

1 ．结果菜单的数目应该恰好为 M ，荤菜，素菜，辛辣，清淡菜的数目恰好为 a ， b ， c ， d 。在满足这样的前提下，选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。

4 D; P1 [# J8 c/ \7 Q2 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。

; `; V- b# r& X# A输入样例

+ F0 O) o' G/ d1 l  X3 2 2

水煮鱼 30 1 1
# @4 G7 m8 q; m; g
口水鸡 18 1 1

6 i- {1 s+ x. `1 A8 V- f- N+ H清炖豆腐 12 0 0
. V& b. ~) ^5 T" k% C) P% `; B
1 1 1 1
) G0 m4 p! C+ \9 V& D- c

/ y. P* d$ x$ [+ r
输出样例

口水鸡

清炖豆腐
' ~& {) g$ |/ G3 d  N
$ |+ C) h/ `: G2 B7 ]  T* X( O9 B12.00
6 \" @* V. O9 @

3 d" R% P: f+ ~7 c8 u7 p. Z0 O# p% U
& l1 t+ g; \  D: u& i
时间要求： 1S 之内

) M. w4 e9 `3 |  E" L) uexample：
#include <cstdlib>
#include <iostream>
9 `) J! O9 T0 R$ F- F! l. R5 N
using namespace std;

0 e9 Y* z1 {# d6 u( ^. c1 y
struct cai
  H+ t  ?6 ]% f5 r3 ^{
9 a2 R; h7 l, d' G) Z       string cainame;
       int price;
: A/ @8 ~1 u: A$ |9 a3 h. R, c       int hun;
       int la;
       };
int* alltotal=new int[30];
int pos=0;
cai* pcai;
int N=3;  
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;
9 j$ M; k; P7 Q4 Q& G& S    int a=1,b=1,c=1,d=1;
    pcai = new cai[N];
    pcai[0].cainame="water fish";
3 J8 q4 G- p1 q/ U5 ^0 `    pcai[0].hun=1;
; j2 V9 Y# Q" Y. u' D7 R, W    pcai[0].la=1;
    pcai[0].price=30;
    pcai[1].cainame="mouth fish";
; y2 X* `2 J" ~* }    pcai[1].hun=1;
    pcai[1].la=1;
- u) g+ T6 s" i& ?# u  S3 T    pcai[1].price=18;
* Q& j- M# y8 b) J  M1 Q    pcai[2].cainame="doufu";
    pcai[2].hun=0;
    pcai[2].la=0;
( A6 t- t4 T! y- W% w    pcai[2].price=12;
6 t' f3 r# h: y; M8 b5 Z    for(int i=0;i<N;i++)
9 X! o# R8 }( h( @2 N, y  M    {
        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--;
1 C; Z) s+ n/ a' @0 H9 R8 Y        if(pcai.la==1)tc--;else td--;
        fun(select,1,M-1,ta,tb,tc,td,pcai.price);
  G1 \9 K% c% r        delete[] select;
        }
    }
$ y5 {  |$ h6 a. i# h" }    for(int i=0;i<pos;i++)
* n1 ?+ L2 p# t0 Z% P: {    cout<<alltotal<<endl;
    delete alltotal;
( x, s' l0 |( f2 k    delete []pcai;
    system("PAUSE");
    return EXIT_SUCCESS;
}
! S) k) D& F: s) ]( {void fun(int * select,int n,int M,int a,int b,int c,int d,int total)
{
2 A5 A9 R8 q. S1 G    //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;
" W6 f* r5 K4 W- V' o1 K) S    //getchar();
. t2 E0 {/ D/ |3 D3 }, _$ y    //cout<<n<<"|"<<M<<"|"<<a<<"|"<<b<<"|"<<c<<"|"<<d<<"|"<<total<<"|"<<endl;
$ n; i( r* v: M* A# a8 v' p7 F% g- h    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++)
+ j  S3 Y1 F! T$ Q5 R    {
7 `: T* d( ~7 a* {* Z7 k. v         for(int j=0;j<n;j++)if(select[j]==i)continue;
" K6 i; y! l0 I# S        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--;
        if(pcai.la==1)tc--;else td--;
# O& q8 j8 z/ _7 p" w        fun(myselect,n+1,M-1,ta,tb,tc,td,total+pcai.price);
4 p: B2 S: u. H        delete[] myselect;
5 B& s( B1 J4 k3 ]: e5 @        }
    }
}

928171481

嗯，不错不错