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

厚积薄发

饭团的烦恼

“午餐饭团“是百度内部参与人数最多的民间组织。

6 Q2 t" P) g; b6 k" h0 B# D/ R同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。
) q4 o  G& B) I- }& Z5 ]
/ Q" ^3 l7 O9 ]参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。
- P# j1 @, ?& G' K$ `1 s0 I
2 [$ |9 I# y- ~; I: Y- k但是，随着百度的员工越来越多，各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口，饭团的点菜负责人背负的责任越来越大。现在，这个重担落在百度之星的肩上，因为，你们将要为所有的百度饭团设计一个自动点菜的算法。

饭团点菜的需求如下：

" |2 C' |" I. k+ h+ _1 ． 经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近 12 元越好。

3 f& }/ y# i' ]2 ． 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。

" M5 I2 l1 J4 G; O* l8 o  z! u" w3 ． 请紧记，百度饭团在各大餐馆享受 8 折优惠。
# ?) C7 z% _8 A- h" J/ G- [
输入数据描述如下：
" m% |' Y1 a: ?1 P+ m" S* X
% Q" W2 R% P" Q: {& g0 ^+ Q第一行包含三个整数 N ， M ， K （ 0<N<=16 ， 0<M<=N ， 0<K<=12 ），分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。

4 r5 V" X! X% ^* F, ?, Z$ _  Q紧接着 N 行，每行的格式如下：

, Y+ Y% H2 t% c- D+ q菜名（长度不超过 20 个字符） 价格（原价，整数） 是否荤菜（ 1 表示是， 0 表示否） 是否辛辣（ 1 表示是， 0 表示否）
8 V/ t  n  u2 {# [1 I2 Z
9 G' `* V( r) ]- k例：
; k9 K9 y+ n4 z/ U  S
9 g# R- h2 A( q8 w) h0 ?8 @水煮鱼 30 1 1

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

输出数据：
" g, L! r1 a1 ^" `& f
对于每一测试数据，输出数据包含 M+1 行，前 M 行每行包含一个菜名（按菜名在原菜单的顺序排序）。第 M+1 行是人均消费，结果保留两位小数。

- `4 X4 f; }+ X- p+ g9 ?0 R说明：
, r) I+ D/ G4 e( i! c  B( v; m% H
1 ．结果菜单的数目应该恰好为 M ，荤菜，素菜，辛辣，清淡菜的数目恰好为 a ， b ， c ， d 。在满足这样的前提下，选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。
) c3 T* u/ o+ N- x
2 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。

输入样例

3 2 2

* _4 _: I3 R" X7 `( U0 V$ l# @/ c3 A水煮鱼 30 1 1
  r, Q0 `. p9 t, b/ V6 C/ Y' C
口水鸡 18 1 1
3 H$ g9 a" ?# |* P% s
清炖豆腐 12 0 0
6 G" {. }9 V# F* ]) q# b) C9 J
% s" W4 t3 e, k: _1 1 1 1
, J: C+ N" [1 K; M

  {6 K% P; m9 u- W
, H, ]- A' c& j) L( q输出样例

口水鸡

清炖豆腐

$ s* l' b3 z0 k) O4 R+ y12.00

7 \- @1 O' ~. Y( l2 B* z% c: v时间要求： 1S 之内

# ~" @7 j$ k7 ~+ J, `example：
8 i4 a! }# p: h4 W: I#include <cstdlib>
3 r. H. v5 t* g4 t2 X( `#include <iostream>
  G3 [/ B9 U( O; d1 E' T4 T
6 J6 L. z" x2 d0 n5 F/ A9 Qusing namespace std;


- z- g4 ~* u; f: r  }$ estruct cai
  m: t+ `# K  p{
       string cainame;
       int price;
       int hun;
& a  o# K2 p9 P       int la;
       };
int* alltotal=new int[30];
4 l5 w( t* v6 {+ A+ Mint pos=0;
8 S: D8 `# E2 Acai* pcai;
int N=3;  
7 y/ W$ z% f7 Avoid fun(int * select,int n,int M,int a,int b,int c,int d,int total);
int main(int argc, char *argv[])
{
- T& N& a$ ]  u9 O2 p    int M=2,K=2;
0 v5 [5 t' l9 B" ^' i    int a=1,b=1,c=1,d=1;
    pcai = new cai[N];
5 s% {$ k6 W, ?0 H5 e' Z1 H8 T    pcai[0].cainame="water fish";
    pcai[0].hun=1;
: D7 m4 l: V! n    pcai[0].la=1;
6 b7 f1 m. h& y( {& u; C  ~) I    pcai[0].price=30;
  a8 C! B% h1 L" Y. {7 C( Q6 }    pcai[1].cainame="mouth fish";
    pcai[1].hun=1;
3 z3 G2 W6 t+ l    pcai[1].la=1;
    pcai[1].price=18;
% {* x, N( p) F' D7 e    pcai[2].cainame="doufu";
    pcai[2].hun=0;
    pcai[2].la=0;
* _6 F$ f2 d9 T5 U9 s5 _% l9 S    pcai[2].price=12;
4 c0 m5 e6 w9 K% A" @) G    for(int i=0;i<N;i++)
    {
        if( (pcai.hun==1 && a>0) ||(pcai.hun==0 && b>0) || (pcai.la==1 && c>0) || (pcai.la==0 && d>0))
$ r5 |; e8 {, t" g        {
        int ta=a,tb=b,tc=c,td=d;   
        int* select=new int[1];   
        select[0]=i;
        if(pcai.hun==1)ta--;else tb--;
        if(pcai.la==1)tc--;else td--;
# J4 S* Q& `( Q- L$ U9 i& W' _/ V        fun(select,1,M-1,ta,tb,tc,td,pcai.price);
        delete[] select;
) x' I% Q( C# M, Q& m        }
    }
    for(int i=0;i<pos;i++)
    cout<<alltotal<<endl;
# d2 N# {9 @2 f    delete alltotal;
$ i. @! L1 _! l2 _    delete []pcai;
% J; s; f+ A' N6 P$ H5 T* R3 G    system("PAUSE");
/ V7 @/ X: g! i4 m/ t8 W* e    return EXIT_SUCCESS;
}
! j2 `, Z2 b3 L5 T7 D% ivoid fun(int * select,int n,int M,int a,int b,int c,int d,int total)
( a; \+ }% [9 R6 G$ Q$ Q{
0 D: B+ n3 w- H& m. B0 ~$ s    //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;
, Z/ V' P; j4 G' y- Q) _5 W    //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;}
8 m! H5 O0 N2 M, C$ s) U# C    if(M<=0 && (a<=0&&b<=0&&c<=0&&d<=0)){cout<<total<<endl;alltotal[pos++]=total;return;}
8 f5 x1 E. Y) |0 \& @    for(int i=select[n-1];i<N;i++)
    {
         for(int j=0;j<n;j++)if(select[j]==i)continue;
* I$ G6 b9 x* A. E7 w# @) 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))
, U1 A& Y: w+ o        {
        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;
+ f' T7 k" [5 r9 V9 A+ X" C        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;
1 _- G4 @( q5 a6 s2 l$ A+ |" V        }
4 }/ [3 l' P2 ~) E1 j7 B    }
}

928171481

嗯，不错不错