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

厚积薄发

饭团的烦恼
5 h5 _: I/ j) }. R/ Y3 g3 Y
“午餐饭团“是百度内部参与人数最多的民间组织。
' o$ `( u; Y% V7 V8 ^# u- a
+ k4 n7 D3 _( i* U同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。
% `, W3 C. p& z! D! I. o- u1 Z' T
3 i2 e# M/ @# g! w8 i1 ?& h! Y' U参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。

3 ~1 T4 g- `5 ~" T# [但是，随着百度的员工越来越多，各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口，饭团的点菜负责人背负的责任越来越大。现在，这个重担落在百度之星的肩上，因为，你们将要为所有的百度饭团设计一个自动点菜的算法。
( C6 f' u6 {0 F
饭团点菜的需求如下：

1 ． 经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近 12 元越好。
9 n- \# a" R' ^4 l6 c. c
7 ?" K3 b6 p# z2 ． 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。
1 ]4 Q. D0 B2 |( X( Z
3 ． 请紧记，百度饭团在各大餐馆享受 8 折优惠。
, L. U& r& g3 \6 m% E% Z# Q- W8 i' |
' N0 }. b' q. }" ?输入数据描述如下：
# z2 g8 ^) Y5 y$ V+ Y) I
! S" ~. D- \2 F" l4 r第一行包含三个整数 N ， M ， K （ 0<N<=16 ， 0<M<=N ， 0<K<=12 ），分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。

紧接着 N 行，每行的格式如下：

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

6 V9 J+ u( z( P" p6 S& m6 y& _例：

7 ^) j7 T+ V: l# y/ u水煮鱼 30 1 1

紧接着是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。
6 J& b4 T7 {7 @% d" H: l. O! y
. l8 N2 I0 u2 s' G# v* s" h输出数据：
1 Y% b6 h  x5 U/ d" p3 @) N4 P
  u: T5 a4 P% W9 L+ M对于每一测试数据，输出数据包含 M+1 行，前 M 行每行包含一个菜名（按菜名在原菜单的顺序排序）。第 M+1 行是人均消费，结果保留两位小数。

说明：
  N! o' l# ]7 |3 e
) q; x) g! M- k) W" U; C1 ．结果菜单的数目应该恰好为 M ，荤菜，素菜，辛辣，清淡菜的数目恰好为 a ， b ， c ， d 。在满足这样的前提下，选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。

- f! z' K/ W: u# N2 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。
: ]& b; @- S4 K' e# I0 y- C/ U
输入样例

7 X+ i# m7 ]# H% h3 2 2

  l8 i5 L; I' m) ]: p" v水煮鱼 30 1 1
% P4 y; h' o3 g) G$ A7 @
口水鸡 18 1 1
  m. E2 M& X; \( b% K
' J7 ?5 E2 [  B清炖豆腐 12 0 0
2 J) @) s4 T, c8 J0 s& F
& N3 j% D. J/ x3 v) X1 1 1 1
, B5 W2 N: L2 S  ^1 L( U3 l% }

# P& j1 T/ g& G; J+ K
2 u9 \/ v/ f8 Y输出样例

口水鸡

清炖豆腐
3 Z: K0 t5 K8 z5 I
12.00
4 v, S' y& d1 Z. D1 H8 Q& M6 T0 C

/ M! `$ {. C* i3 ?' ?1 v- W
5 ?- i2 a% ~' t* z4 W, ]时间要求： 1S 之内

example：
#include <cstdlib>
#include <iostream>
( F! E% B4 `* D9 o% u
! f, `" ~# I% ousing namespace std;


struct cai
{
& N* P6 U8 a0 {! @3 h6 k       string cainame;
) k* X% W- J4 j' y# m5 D- y       int price;
6 a( p/ b! R5 S( Q+ U9 R       int hun;
6 P; U, q4 U8 v# [       int la;
       };
1 y# n7 u* D4 t& Aint* alltotal=new int[30];
. h3 y* t; P* pint pos=0;
cai* pcai;
0 [0 q1 N! p$ Q9 z. D* h, tint N=3;  
, b: T- [% d7 d( ovoid fun(int * select,int n,int M,int a,int b,int c,int d,int total);
- j: c6 N( r* I7 Y* Y" Y6 wint main(int argc, char *argv[])
{
7 m5 v+ Q) R3 ~$ C) I8 \: y6 M    int M=2,K=2;
1 j3 o' _/ U, ~/ f) v    int a=1,b=1,c=1,d=1;
    pcai = new cai[N];
5 X7 [" S6 H  \, f0 g) q    pcai[0].cainame="water fish";
: S& a$ g3 ~- O    pcai[0].hun=1;
$ w* H0 E6 p3 F5 e  _: ?    pcai[0].la=1;
    pcai[0].price=30;
7 ~  J# ]1 H! B2 L$ K7 L' @    pcai[1].cainame="mouth fish";
    pcai[1].hun=1;
3 o' Q0 O/ L1 l9 {    pcai[1].la=1;
    pcai[1].price=18;
    pcai[2].cainame="doufu";
    pcai[2].hun=0;
' x" l9 G* n; @% s    pcai[2].la=0;
    pcai[2].price=12;
1 N  \  F, i$ t/ m* Q6 I    for(int i=0;i<N;i++)
/ C- [2 A; n7 m, ]( S3 z    {
        if( (pcai.hun==1 && a>0) ||(pcai.hun==0 && b>0) || (pcai.la==1 && c>0) || (pcai.la==0 && d>0))
        {
: z* U( D8 }+ P9 g* b2 T0 ?3 ?. C        int ta=a,tb=b,tc=c,td=d;   
        int* select=new int[1];   
: t% Y2 a7 q9 N* R% H7 ^2 g: f        select[0]=i;
        if(pcai.hun==1)ta--;else tb--;
3 F5 l( z9 I! K" P+ q* b! O. `        if(pcai.la==1)tc--;else td--;
        fun(select,1,M-1,ta,tb,tc,td,pcai.price);
        delete[] select;
        }
$ t* C: ?- G' x4 W1 |6 S* L; M    }
6 g. Y8 b* C) V# y  H    for(int i=0;i<pos;i++)
    cout<<alltotal<<endl;
    delete alltotal;
: [* ~: q) r* u- }2 o9 I* L    delete []pcai;
5 k' [- `0 v! N6 `7 F, Q: G' v& e    system("PAUSE");
+ j9 h' S9 b) B4 Y  k    return EXIT_SUCCESS;
}
void fun(int * select,int n,int M,int a,int b,int c,int d,int total)
# x$ N2 ?1 h$ D. K{
% g3 E5 V2 k5 J! C    //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;
2 m) a9 ^! @' E" t9 N6 A    //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;}
    if(M<=0 && (a<=0&&b<=0&&c<=0&&d<=0)){cout<<total<<endl;alltotal[pos++]=total;return;}
( a" [4 m+ Z+ P2 S# G9 N    for(int i=select[n-1];i<N;i++)
/ ^* |4 k# q2 o$ H8 J3 C    {
! L1 O; J9 Z2 i0 o% |; k$ B7 h         for(int j=0;j<n;j++)if(select[j]==i)continue;
        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];
  H% P( ^. R8 C4 ?) A4 |% P        myselect[n]=i;
        if(pcai.hun==1)ta--;else tb--;
) Q6 t3 n) ^! Y        if(pcai.la==1)tc--;else td--;
$ a2 R# C# ]& x6 l        fun(myselect,n+1,M-1,ta,tb,tc,td,total+pcai.price);
        delete[] myselect;
        }
- A- L; Z# c; o0 x7 c' I0 G: p8 h    }
% `) N$ K4 F, A4 A* {. M! J$ n}

928171481

嗯，不错不错