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

厚积薄发

饭团的烦恼
2 F, v( m7 A7 @# n. s1 R
“午餐饭团“是百度内部参与人数最多的民间组织。
! c' p9 h3 D, `3 d
同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。

参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。
" @6 F% f1 b! X8 w
但是，随着百度的员工越来越多，各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口，饭团的点菜负责人背负的责任越来越大。现在，这个重担落在百度之星的肩上，因为，你们将要为所有的百度饭团设计一个自动点菜的算法。

饭团点菜的需求如下：
; H6 u8 M0 T' O
5 b" h. Z5 E; }7 ~1 ． 经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近 12 元越好。

2 ． 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。
; N2 c( Q9 t8 h
3 ． 请紧记，百度饭团在各大餐馆享受 8 折优惠。

输入数据描述如下：

; |: M2 J8 d; m2 b( I第一行包含三个整数 N ， M ， K （ 0<N<=16 ， 0<M<=N ， 0<K<=12 ），分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。
# Z: b5 j1 u% A3 f4 I
紧接着 N 行，每行的格式如下：

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

例：
2 |9 D6 L7 p; r# P) f4 w4 S
水煮鱼 30 1 1
) B  \5 t) g! L
. H& L+ A- p9 o/ k7 _紧接着是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。

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

说明：

1 ．结果菜单的数目应该恰好为 M ，荤菜，素菜，辛辣，清淡菜的数目恰好为 a ， b ， c ， d 。在满足这样的前提下，选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。
0 B5 z; a$ P; Y* ^5 H- ~
) n  a& Z5 t3 X6 J  h1 Y( h& k2 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。

输入样例

3 2 2
' d6 H: d$ c2 p
7 |, r) G2 u. c8 T, j3 ~, z" E# |水煮鱼 30 1 1
' y; l) ^; d; ^9 z
7 J/ V: P9 q8 n: R6 J$ ]! a4 p" q口水鸡 18 1 1
& Q) T$ R! E$ T3 b& K
清炖豆腐 12 0 0
# T& |* r7 ]* q4 X
1 1 1 1
4 o. }# O7 y/ \: j

输出样例

- x' ~1 J& M" Q' V- r口水鸡

7 K1 g9 s9 W* B' K清炖豆腐
5 O- Z: l9 K  X7 n' {$ F: k5 o
; y2 M7 r# o6 S3 m12.00
0 j, a, q- B3 h0 L5 o& J+ u

; U% i6 E4 y% f: t

时间要求： 1S 之内

example：
#include <cstdlib>
#include <iostream>

using namespace std;

+ a, G# Z) L1 h6 ]
struct cai
# t  v  W7 m9 T% t$ M{
7 l# q6 ^/ F* a' y* @, Q. Y& p" H- B       string cainame;
       int price;
8 z+ Q' |2 O9 C0 w" i2 a       int hun;
# w1 f# T" _5 H       int la;
       };
. D' O" |/ q  O9 p- b' h* Uint* alltotal=new int[30];
$ \" k+ F- u" E; |int pos=0;
" H( |# D& F) I( O4 z$ a, c8 `cai* pcai;
int N=3;  
void fun(int * select,int n,int M,int a,int b,int c,int d,int total);
% p( e, g7 @3 P' _& a5 g: Rint main(int argc, char *argv[])
{
    int M=2,K=2;
    int a=1,b=1,c=1,d=1;
    pcai = new cai[N];
6 x! H& L$ z2 c6 y9 |: M. {( h    pcai[0].cainame="water fish";
3 f( D! A( w6 y) _. A# v: g    pcai[0].hun=1;
    pcai[0].la=1;
    pcai[0].price=30;
    pcai[1].cainame="mouth fish";
& a( O6 S1 p7 w5 ]3 G    pcai[1].hun=1;
7 ~  w) }2 i9 O( u- P    pcai[1].la=1;
    pcai[1].price=18;
    pcai[2].cainame="doufu";
    pcai[2].hun=0;
4 }7 [) {1 G/ N2 z2 b9 D    pcai[2].la=0;
3 J- ^% G1 c9 r" |2 e    pcai[2].price=12;
* k  v% H5 J) l7 U5 g% L    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))
        {
: k1 {6 `+ k0 _8 d, S  V+ o        int ta=a,tb=b,tc=c,td=d;   
% f/ D6 k( Q9 ~, M0 l0 ^: ]* {0 m        int* select=new int[1];   
        select[0]=i;
/ B, E. W% F4 o! G3 x+ y% s        if(pcai.hun==1)ta--;else tb--;
& L, T* m+ H' B8 e+ z8 a        if(pcai.la==1)tc--;else td--;
9 W7 r* p# j! D# X3 Q( N+ ]        fun(select,1,M-1,ta,tb,tc,td,pcai.price);
        delete[] select;
! r8 A* \& E3 N. P9 Q4 o! N: R, u        }
2 p* k2 [5 i' ~2 V/ K    }
    for(int i=0;i<pos;i++)
% d- j! B- N$ T! j. i    cout<<alltotal<<endl;
    delete alltotal;
0 n, N9 ]( M/ B& z5 z    delete []pcai;
# C8 H4 Q! x, U; i+ n. ^    system("PAUSE");
" {$ G8 \/ I( r$ ~8 i1 ~+ B/ ~    return EXIT_SUCCESS;
}
& v9 J& F) W# R/ {8 x8 w3 yvoid fun(int * select,int n,int M,int a,int b,int c,int d,int total)
5 W$ e5 I1 ~% |/ x: F5 L1 x{
/ \$ I! `/ l2 c# C* e! ^. U    //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;
) M9 p% k9 l& Y! \" Z5 A) s    //getchar();
6 R' {, B9 N2 B    //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;}
    for(int i=select[n-1];i<N;i++)
    {
         for(int j=0;j<n;j++)if(select[j]==i)continue;
+ V' ^. p" q- C+ i        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))
6 k. ^) W+ @, Y; d/ Z        {
% q4 D2 s% }: T& W        int ta=a,tb=b,tc=c,td=d;
7 F+ d: @6 V  _  K) Y        int* myselect=new int[n+1];   
. Z" H) ?6 K, d8 a  z: I. E        for(int k=0;k<n;k++)myselect[k]=select[k];
        myselect[n]=i;
; R7 X* m  ]8 P9 F3 m        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);
% X! L$ L4 k  j. G2 @        delete[] myselect;
        }
    }
}

928171481

嗯，不错不错