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

厚积薄发

饭团的烦恼

“午餐饭团“是百度内部参与人数最多的民间组织。
1 ^  {& J# f  J8 L, f
7 j$ l# X7 _6 i1 n3 [$ q; Z* i同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。
  `" m- p) g4 a- f3 c
参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。

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

, a/ I! A3 S1 r% l9 j2 a( [0 E饭团点菜的需求如下：
% q* b3 t4 E& j: O
1 ． 经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近 12 元越好。
) j! i" m0 X" n9 Y" w
- f; Z- b' h4 F" p3 k' z2 ． 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。

$ u5 X6 }7 U& e3 p# k3 ． 请紧记，百度饭团在各大餐馆享受 8 折优惠。
0 m" S$ T0 J6 _. V
  f$ D; S& a: ], T: |& \输入数据描述如下：

* W; z' j# X4 E- I$ M第一行包含三个整数 N ， M ， K （ 0<N<=16 ， 0<M<=N ， 0<K<=12 ），分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。
. x' W* [. [$ H, {6 E/ V
; N, @$ S  v- ~. `/ ]紧接着 N 行，每行的格式如下：
9 @, a. d1 R8 `9 N4 K+ E, ?
菜名（长度不超过 20 个字符） 价格（原价，整数） 是否荤菜（ 1 表示是， 0 表示否） 是否辛辣（ 1 表示是， 0 表示否）

. ]9 w' a; i# R! z. B例：
9 z( f7 n6 |  P: {5 L$ d" E7 ?2 a
水煮鱼 30 1 1
6 n0 D9 R7 z) z, U$ X
! ]- U, d! Z9 _8 ]% @紧接着是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。

5 c, x" O: a5 P# w输出数据：
! n2 q2 n! x# F$ w8 B& s. X4 E
对于每一测试数据，输出数据包含 M+1 行，前 M 行每行包含一个菜名（按菜名在原菜单的顺序排序）。第 M+1 行是人均消费，结果保留两位小数。
0 n* v7 e7 u/ {0 h# ]. e
说明：

# B' a  X0 Z3 j- }4 Z7 ]. W# m1 ．结果菜单的数目应该恰好为 M ，荤菜，素菜，辛辣，清淡菜的数目恰好为 a ， b ， c ， d 。在满足这样的前提下，选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。

2 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。
, G- h8 V3 G' U: S- S) f) J* `! ?
输入样例

7 h  Y! }* P: ?/ _+ l3 2 2
, [& a, D9 x/ e1 P; n) t
水煮鱼 30 1 1

! L- M( U0 C7 Z6 ~" h* O# z) l  p口水鸡 18 1 1
, {- o  g8 @9 ^+ H
清炖豆腐 12 0 0

8 l7 S" V' p' A# F3 Z/ s1 1 1 1

- ~/ d( O" h% u9 z4 e% ~/ U; G
输出样例

9 M0 x0 y  \5 K9 T口水鸡
3 t& i( J$ t0 X2 R0 [
, F8 \7 }' d: W! s2 }% O清炖豆腐

12.00

1 X# e: _0 s7 J, `) a9 _

时间要求： 1S 之内

example：
9 ^- s$ u+ z3 R* j& U. Q2 K2 O#include <cstdlib>
#include <iostream>

6 _! D6 {# V- y) f# q7 g% [( H# Ousing namespace std;
, U5 X  u- M. H" U1 a
' I* v/ j+ t. [+ i6 y3 p
struct cai
$ r( ~9 z1 E( P/ `: o{
, _: r4 ]6 g) Y$ a: R       string cainame;
6 U/ @/ g) n2 Q9 C       int price;
- s8 }1 r0 k9 |0 d       int hun;
7 g' |$ V, b6 B3 d       int la;
       };
int* alltotal=new int[30];
- x/ S8 |) a* E- B. V1 lint pos=0;
( y( A! I9 b, L1 `1 tcai* pcai;
2 @! s5 M& N+ Q  B9 G8 mint N=3;  
4 K2 M. ^  K3 Q* Bvoid fun(int * select,int n,int M,int a,int b,int c,int d,int total);
5 p) j3 m6 S& V7 T* Y5 b% X' uint main(int argc, char *argv[])
{
    int M=2,K=2;
. b- b0 E0 H; `4 g1 o1 t! w6 f    int a=1,b=1,c=1,d=1;
    pcai = new cai[N];
2 Y1 M! h8 ]2 s' \+ Y    pcai[0].cainame="water fish";
5 l0 h/ e: ]- p& {    pcai[0].hun=1;
2 g& _4 N& Q) t$ V' z0 ]    pcai[0].la=1;
    pcai[0].price=30;
3 {" {( P5 R! P: E; i# |    pcai[1].cainame="mouth fish";
, I3 S# |4 X1 r% u5 S    pcai[1].hun=1;
    pcai[1].la=1;
. q; \$ f3 ~. M. C    pcai[1].price=18;
    pcai[2].cainame="doufu";
* J! }' R. R0 Z    pcai[2].hun=0;
& S& X$ @: X4 A+ L    pcai[2].la=0;
    pcai[2].price=12;
    for(int i=0;i<N;i++)
6 {2 |! [* p2 M8 l    {
        if( (pcai.hun==1 && a>0) ||(pcai.hun==0 && b>0) || (pcai.la==1 && c>0) || (pcai.la==0 && d>0))
        {
. L9 F/ S# ?8 {7 [; [4 `6 W        int ta=a,tb=b,tc=c,td=d;   
        int* select=new int[1];   
        select[0]=i;
2 e/ M- l0 T$ D        if(pcai.hun==1)ta--;else tb--;
/ ^  n; ^; L6 V9 c/ s1 a$ F        if(pcai.la==1)tc--;else td--;
        fun(select,1,M-1,ta,tb,tc,td,pcai.price);
5 ]0 N5 B6 c* a4 {$ Q! g        delete[] select;
) L; H# s# G/ s- q3 j        }
/ a' Z9 T7 G) \/ ]    }
    for(int i=0;i<pos;i++)
    cout<<alltotal<<endl;
9 U7 ^, o3 M* L9 i: ~    delete alltotal;
1 U' ~4 }2 v3 N* E    delete []pcai;
    system("PAUSE");
    return EXIT_SUCCESS;
}
& q7 |7 t* e- m* @void fun(int * select,int n,int M,int a,int b,int c,int d,int total)
; U$ i, y) l. `' S3 }) o4 y{
$ j1 V- a  F- E$ S0 w! X% h    //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;
    //getchar();
    //cout<<n<<"|"<<M<<"|"<<a<<"|"<<b<<"|"<<c<<"|"<<d<<"|"<<total<<"|"<<endl;
/ h# Z& F0 G2 c% b" {* z    if(M<=0 && (a>0||b>0||c>0||d>0)){cout<<"impossible"<<endl;return;}
  a8 ~$ O* _# u2 Y& l5 h4 b6 U    if(M<=0 && (a<=0&&b<=0&&c<=0&&d<=0)){cout<<total<<endl;alltotal[pos++]=total;return;}
6 Y  a# R4 F- ^, }* B( n5 ^& r    for(int i=select[n-1];i<N;i++)
+ A9 t* a$ \! h5 b( O' a    {
" y7 ~/ r; H  ^1 A6 @         for(int j=0;j<n;j++)if(select[j]==i)continue;
4 v% B% e0 w4 d4 t4 i7 X. i+ K) \3 M        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))
! Y% R+ `9 p# l: J& e6 e5 {        {
        int ta=a,tb=b,tc=c,td=d;
2 x# v1 I0 a9 |/ ?        int* myselect=new int[n+1];   
        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--;
        fun(myselect,n+1,M-1,ta,tb,tc,td,total+pcai.price);
        delete[] myselect;
2 I' ], G) _: G+ v7 K9 B5 J        }
/ x/ k! E. m6 r* Z4 i    }
) o/ s' W. [2 W$ N9 S}

928171481

嗯，不错不错