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

厚积薄发

饭团的烦恼
- X* y1 ^0 ]9 X: H! R
1 D* W6 L% T8 U/ s“午餐饭团“是百度内部参与人数最多的民间组织。
" `9 K3 _4 A7 x: z# B% q
% ^; w# F3 l2 T8 l) n! T同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。

参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。

1 Z/ V2 U! _% d/ T: M但是，随着百度的员工越来越多，各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口，饭团的点菜负责人背负的责任越来越大。现在，这个重担落在百度之星的肩上，因为，你们将要为所有的百度饭团设计一个自动点菜的算法。

饭团点菜的需求如下：

$ P2 J7 y1 U" [) n$ y: g( v6 k  W6 s( n. k1 ． 经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近 12 元越好。
, J/ @. L0 z$ [+ f
7 r; L' M8 W# ~; O2 ． 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。

3 ． 请紧记，百度饭团在各大餐馆享受 8 折优惠。
  r: B. i! y) E
8 ?: @; u4 x* K! p* J4 ?7 i' W, m9 v输入数据描述如下：
3 N5 l; [3 z; _: \  [( k1 E
2 r6 P6 f+ n3 C8 L: @/ K3 K第一行包含三个整数 N ， M ， K （ 0<N<=16 ， 0<M<=N ， 0<K<=12 ），分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。
$ K; `- J! i  Z4 L. v* C1 |) B- i  d
6 q& h4 r5 J8 Q8 K1 P5 c& K紧接着 N 行，每行的格式如下：
- v4 v* H6 c! q% _0 b4 g: N! ^
/ y0 ]2 w; T  m, j. R菜名（长度不超过 20 个字符） 价格（原价，整数） 是否荤菜（ 1 表示是， 0 表示否） 是否辛辣（ 1 表示是， 0 表示否）

例：
. @8 L( V5 m% i0 c% |* G2 [
7 Z0 f6 V% }! d' H( v水煮鱼 30 1 1

* A$ ~" F8 C8 M) i( D# ~紧接着是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。
# S9 L! g, u) o6 l8 o% U. N( [
! ~  t* A. ?- S9 `% d% R输出数据：

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

/ x0 m. \' [3 ~# M# F6 \说明：

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

2 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。
2 ]+ P/ o5 n0 d  u' a; u
, a, T- z# A1 p! n. {) S输入样例

8 n* \" ~5 X, ~" x+ V5 t& }, B3 2 2
7 f5 E& P# _5 Q$ |( J
0 V* U( j( I! T- T" p' J3 [0 ?; j水煮鱼 30 1 1
0 p4 }. b. X3 }4 R. ]
口水鸡 18 1 1
1 B' v3 s8 d$ P; _" _2 j
" Q  z% r  B  Z$ J8 j* Q" d& F. J清炖豆腐 12 0 0
  P: F# |# T# W4 m- F
- K1 {" f6 G$ T/ b( V( n: l$ d" j1 1 1 1

输出样例

% e0 Q# t9 G* _! g% D; D% q口水鸡
: i8 V% O" ^% J+ o& _4 L+ h( v
* t2 I7 l8 K& r7 x) p清炖豆腐

12.00
" |& x7 a$ w0 Z0 t) i4 n

% _- G' q: c1 O6 Y, }# ?

时间要求： 1S 之内
" t( m/ g+ A- h* b! Q
example：
#include <cstdlib>
. Y& {$ ~) H4 N- ]. S# B! p#include <iostream>

( f: q9 b$ R* c) x$ }using namespace std;

* _. e$ x( |4 {
struct cai
{
       string cainame;
3 M5 J7 G+ H; ^6 _       int price;
       int hun;
- Y7 {3 o/ E( k, {& P6 O3 k( g+ {. d       int la;
       };
int* alltotal=new int[30];
" T4 |+ x, |( v) T3 m, o# ~  {! I! Aint pos=0;
cai* pcai;
6 ?5 x/ r: B# i! [& c1 f5 mint N=3;  
, |2 _3 y( K9 v: H/ P8 Wvoid fun(int * select,int n,int M,int a,int b,int c,int d,int total);
! d& q) b& B, p" \- L" Qint main(int argc, char *argv[])
{
    int M=2,K=2;
6 |9 O: a. N- y4 @5 ]; w. s& v    int a=1,b=1,c=1,d=1;
3 K/ X# S9 m9 A: M( p    pcai = new cai[N];
! b9 o  w. u# u# o6 M3 R    pcai[0].cainame="water fish";
    pcai[0].hun=1;
    pcai[0].la=1;
    pcai[0].price=30;
    pcai[1].cainame="mouth fish";
( u7 [/ P2 J& n! l3 @    pcai[1].hun=1;
    pcai[1].la=1;
    pcai[1].price=18;
    pcai[2].cainame="doufu";
$ h2 |7 Y4 f# U; a. j    pcai[2].hun=0;
: ]' G% V" S/ y    pcai[2].la=0;
* Y: v( S* j* e    pcai[2].price=12;
    for(int i=0;i<N;i++)
    {
. x5 Q% K3 F. f/ @/ i4 I        if( (pcai.hun==1 && a>0) ||(pcai.hun==0 && b>0) || (pcai.la==1 && c>0) || (pcai.la==0 && d>0))
        {
! `6 U4 {# x  `5 X* 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--;
        if(pcai.la==1)tc--;else td--;
        fun(select,1,M-1,ta,tb,tc,td,pcai.price);
        delete[] select;
( c# G0 {2 q- }4 `% S% P3 m( |        }
    }
    for(int i=0;i<pos;i++)
+ E  S  S$ j; d3 j1 ]    cout<<alltotal<<endl;
    delete alltotal;
    delete []pcai;
) q1 L  a; A3 m4 a    system("PAUSE");
    return EXIT_SUCCESS;
1 o% G- e  ], l3 N, y$ q- z0 F; |}
void fun(int * select,int n,int M,int a,int b,int c,int d,int total)
( {# H' Y4 v6 T# _+ ]1 I9 q{
    //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;
    //getchar();
, \- E( l+ ]1 P4 Y; @" n  ^$ E    //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;}
+ v% Q* Y( F4 @. e2 B& x0 c; T$ G    for(int i=select[n-1];i<N;i++)
    {
         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))
- v( D  ?& j6 m& Z& W3 w( X        {
5 E( o8 j) X- j* E- a& f# \        int ta=a,tb=b,tc=c,td=d;
- ~) D, N7 y. q, c. s% x        int* myselect=new int[n+1];   
' w3 c* d. ~+ a' c" C4 y: m7 ?; Y        for(int k=0;k<n;k++)myselect[k]=select[k];
0 n& l6 L% u5 ]9 M        myselect[n]=i;
        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);
  _$ ?7 V8 N' S; C2 C1 v" k        delete[] myselect;
% ?, n9 L6 M. y* w, S5 v        }
    }
}

928171481

嗯，不错不错