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

厚积薄发

饭团的烦恼
! h( y- z) A; C0 `+ C+ j7 u% q
5 k' @! F, o" ]* [“午餐饭团“是百度内部参与人数最多的民间组织。
  ?+ ]4 q4 o* f' s# p
: i8 l: @. V% E- l$ B3 p同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。
) o) A' q0 ?2 ^, u0 w! B6 F
5 z" F; C  v2 d1 {0 Z' n参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。

, Q& X9 U& L- T6 d* _' D; A但是，随着百度的员工越来越多，各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口，饭团的点菜负责人背负的责任越来越大。现在，这个重担落在百度之星的肩上，因为，你们将要为所有的百度饭团设计一个自动点菜的算法。
6 M9 m) o% f5 }2 g/ ^( }; g
9 ~# O* F, \# M* f3 h& q饭团点菜的需求如下：

: T) h' R/ E& B) x1 ]1 ． 经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近 12 元越好。

2 ． 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。
+ ]2 l# R8 \& F5 I  H1 Y
3 ． 请紧记，百度饭团在各大餐馆享受 8 折优惠。

输入数据描述如下：
- k$ t: c0 k9 K- `  u
, c- J, g1 N% K* i& A1 H1 d: w第一行包含三个整数 N ， M ， K （ 0<N<=16 ， 0<M<=N ， 0<K<=12 ），分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。
3 A5 I1 [" j' w$ X, p$ P% {
紧接着 N 行，每行的格式如下：
+ H* T2 b) T; Z6 J
" h& F" E' `) u( `% V) S( s菜名（长度不超过 20 个字符） 价格（原价，整数） 是否荤菜（ 1 表示是， 0 表示否） 是否辛辣（ 1 表示是， 0 表示否）
6 Z, ]+ h, C, ?, {
' `4 ~/ `& l6 }9 E例：

水煮鱼 30 1 1
/ N( e, Q) z) l8 ~
/ R. s& I# {( ^0 O( I紧接着是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。

输出数据：

对于每一测试数据，输出数据包含 M+1 行，前 M 行每行包含一个菜名（按菜名在原菜单的顺序排序）。第 M+1 行是人均消费，结果保留两位小数。

$ r( B! l) ]8 J: G9 g0 o说明：
8 Y% q9 W9 ^  K) A
$ C' D* o" L7 T0 L% r1 ．结果菜单的数目应该恰好为 M ，荤菜，素菜，辛辣，清淡菜的数目恰好为 a ， b ， c ， d 。在满足这样的前提下，选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。
3 R/ `# k9 w  K
2 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。
! E$ i& A( ?' ~7 z  B% N
输入样例

1 K& I1 ]3 t0 L4 x3 2 2

水煮鱼 30 1 1

口水鸡 18 1 1

清炖豆腐 12 0 0
+ y+ Y. A' d2 {4 ]3 N+ }0 M. T
, s3 N" n; c/ ]6 x) V( t, k1 1 1 1

6 y5 M) J8 I& ^% q! J! A输出样例

1 X" C# _- V0 O% \" P( H口水鸡
7 {  ?  ^8 G0 H0 f) J; q1 f. k$ w
清炖豆腐
1 ]8 \4 _6 c* e/ V
8 ^% d( _, h' o( i12.00

4 `1 a9 v3 R" N7 c; F0 B" J
; C1 R' A9 Z2 @0 H) X
时间要求： 1S 之内
; X6 K: L7 a' L+ v: V0 b% u8 G2 d- ]
- e8 u: N' d) F8 H( d) T" {! {example：
5 P8 m( a- G+ R3 c: [#include <cstdlib>
8 P- p; X! H  c( A! v8 r2 @" k# X+ k0 a+ u#include <iostream>

using namespace std;


struct cai
{
5 S0 `3 S/ M& t       string cainame;
       int price;
       int hun;
3 \% |  l) y" y  H5 p       int la;
0 l! ^5 e" X) l. y2 X% u       };
/ R8 H  a+ }0 kint* alltotal=new int[30];
int pos=0;
) @  Z4 g- _2 Ycai* pcai;
% v3 [) \3 @4 G& ?int N=3;  
' X* L1 D! v4 w8 f) Ivoid 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;
' t$ F; t4 o7 _$ b$ ^    int a=1,b=1,c=1,d=1;
6 R; G4 J# g  T( m% Q    pcai = new cai[N];
    pcai[0].cainame="water fish";
    pcai[0].hun=1;
: F$ ^: e5 o  H. ~    pcai[0].la=1;
    pcai[0].price=30;
, p4 R$ n) X  @9 g. Q' j$ [4 u    pcai[1].cainame="mouth fish";
    pcai[1].hun=1;
    pcai[1].la=1;
    pcai[1].price=18;
    pcai[2].cainame="doufu";
    pcai[2].hun=0;
& L) l6 U4 d9 \5 v( w    pcai[2].la=0;
! q: V3 ~5 b4 Y+ {8 q    pcai[2].price=12;
6 D! F9 x1 |# @; r: D8 E    for(int i=0;i<N;i++)
    {
; J8 \/ o$ k7 z0 T- |& A8 a" Z0 K% `        if( (pcai.hun==1 && a>0) ||(pcai.hun==0 && b>0) || (pcai.la==1 && c>0) || (pcai.la==0 && d>0))
3 {. z( @1 o8 @8 g. {0 z        {
        int ta=a,tb=b,tc=c,td=d;   
        int* select=new int[1];   
        select[0]=i;
        if(pcai.hun==1)ta--;else tb--;
' p9 L* p# \1 ^! P        if(pcai.la==1)tc--;else td--;
        fun(select,1,M-1,ta,tb,tc,td,pcai.price);
        delete[] select;
        }
4 M3 ^8 {: _! L8 v3 @    }
    for(int i=0;i<pos;i++)
    cout<<alltotal<<endl;
  T- N" l* n! J! |- K9 C    delete alltotal;
) c; Q' T5 Y1 f1 n! y# b: ^: V4 y+ t    delete []pcai;
3 t" z" |% S: S2 v    system("PAUSE");
    return EXIT_SUCCESS;
: j7 A# I9 R9 h6 l}
void fun(int * select,int n,int M,int a,int b,int c,int d,int total)
{
; c! s+ i% G# [3 v& E; P* t    //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;
9 G" m/ T) S1 Q$ u8 q    //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;}
! L6 H4 X/ Y$ r: c/ d    if(M<=0 && (a<=0&&b<=0&&c<=0&&d<=0)){cout<<total<<endl;alltotal[pos++]=total;return;}
' A9 t, t; f) y    for(int i=select[n-1];i<N;i++)
    {
         for(int j=0;j<n;j++)if(select[j]==i)continue;
/ H. d2 c; A0 q$ b: d        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];   
& e7 @+ o/ {" \' b- Y/ h        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--;
# D- w1 D8 l" s: W        fun(myselect,n+1,M-1,ta,tb,tc,td,total+pcai.price);
. w. g# z6 B0 t# h- }2 U4 V$ X" `6 }        delete[] myselect;
        }
8 T/ E1 N. U* v# Q" R% l1 q; ~5 J    }
}

928171481

嗯，不错不错