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

厚积薄发

饭团的烦恼
( |/ o! |# K$ \$ Z
$ A  X* o. F6 v, e  [) L. v5 {4 U4 Q5 o“午餐饭团“是百度内部参与人数最多的民间组织。
: t; A. p7 Q: Z
  n  a1 T9 o9 }: a2 X/ {9 h同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。
9 f0 B+ W) v' F
. _; Z' ^$ \. v( h2 o9 ?参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。
: `7 i: x3 W  b  H. }% p  w
$ z9 ~; m# z5 }/ {' N+ \) @: T但是，随着百度的员工越来越多，各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口，饭团的点菜负责人背负的责任越来越大。现在，这个重担落在百度之星的肩上，因为，你们将要为所有的百度饭团设计一个自动点菜的算法。

4 ~" ]  L- Q) H  W: q饭团点菜的需求如下：

: Q+ D  M8 ]8 H1 ． 经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近 12 元越好。

2 ． 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。
$ ^6 \. Z$ b; n/ g% {
3 ． 请紧记，百度饭团在各大餐馆享受 8 折优惠。

6 C+ M" [" |6 U1 \2 z, s输入数据描述如下：
" p: u* G; ?: v
第一行包含三个整数 N ， M ， K （ 0<N<=16 ， 0<M<=N ， 0<K<=12 ），分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。

紧接着 N 行，每行的格式如下：
" c/ D6 z2 i( k5 A1 z
, h; L% {3 B! H( ~- E; c菜名（长度不超过 20 个字符） 价格（原价，整数） 是否荤菜（ 1 表示是， 0 表示否） 是否辛辣（ 1 表示是， 0 表示否）

. `' i' j, v( k/ m' i  p/ A例：

水煮鱼 30 1 1
9 T9 r5 E9 u2 i0 H9 ~5 l4 o) e
紧接着是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。
$ x, Y6 ^, q2 X/ n
5 g0 H8 t+ {5 m. K# v. e9 G' {' J: t输出数据：

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

说明：
' g, |6 B) b$ u/ |1 E5 S0 {
! b" s9 r' v9 E8 M/ E5 [" f1 ．结果菜单的数目应该恰好为 M ，荤菜，素菜，辛辣，清淡菜的数目恰好为 a ， b ， c ， d 。在满足这样的前提下，选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。
6 O+ e# Z0 z/ ~; [3 `
2 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。
5 u2 O8 n6 m2 T7 d. U  S1 Y
输入样例

! v, X: T( h7 I1 j% n# V/ f3 2 2

水煮鱼 30 1 1
; p  P( u9 V& k1 I# W/ N
口水鸡 18 1 1

清炖豆腐 12 0 0

$ J, p% q. t' U- ?" o3 H! q& n1 1 1 1
2 p8 A9 c1 x6 l6 U+ n. a- t( j

9 t' E& h; e" G0 ?8 q输出样例

" @& R! n: x, a" p" J4 W口水鸡

7 \( h, u3 f: A) \8 W; @% Z清炖豆腐
: |4 q; ~9 U6 I4 z3 {! _: n$ z( l  y
8 C8 A1 q4 Q2 m" U12.00

8 W7 v' [; [0 F, y
3 b) a) m7 c- t6 i7 ^时间要求： 1S 之内
3 m; ^  P: ^( L! O
7 X3 S) b6 Z. y9 f) @' Qexample：
#include <cstdlib>
4 z8 ]$ _) |- o& j* F#include <iostream>

' a& T7 @6 U8 a0 o- P/ @2 V5 Wusing namespace std;

) s& ~6 U) o4 y8 s& Y. g
struct cai
{
5 ?( x) S- Z: s- k/ \  g       string cainame;
, a4 O1 n7 _6 D& {2 y+ |       int price;
, y6 m. A  ?5 q  v5 l* K! k  \       int hun;
       int la;
5 K. A$ }7 `1 k1 q1 e6 B       };
" ^* J( |4 s% R8 N- F6 Q* T4 Dint* alltotal=new int[30];
int pos=0;
cai* pcai;
int N=3;  
, c! |% ~0 k, G! x5 Y# d' Avoid fun(int * select,int n,int M,int a,int b,int c,int d,int total);
int main(int argc, char *argv[])
. {! H, {; ?2 l{
    int M=2,K=2;
7 _0 F  q% Z! P' ?/ P8 }    int a=1,b=1,c=1,d=1;
    pcai = new cai[N];
    pcai[0].cainame="water fish";
    pcai[0].hun=1;
    pcai[0].la=1;
    pcai[0].price=30;
    pcai[1].cainame="mouth fish";
    pcai[1].hun=1;
    pcai[1].la=1;
    pcai[1].price=18;
; I! I- [# Z  N( |, y* g4 P    pcai[2].cainame="doufu";
9 `3 z+ C3 ^# A( Q2 w    pcai[2].hun=0;
; O6 Z  K. u& G; ~/ G    pcai[2].la=0;
4 r3 P# B! E5 f* [) B: V2 h    pcai[2].price=12;
* ]( D. ^' K+ E/ }' v    for(int i=0;i<N;i++)
$ g2 f" F9 j; j9 x1 W$ o    {
1 x0 D* h% z9 y2 `1 q0 z        if( (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;   
5 q$ F' p7 Q: j        int* select=new int[1];   
        select[0]=i;
        if(pcai.hun==1)ta--;else tb--;
4 l& i" R# S6 K- E7 d        if(pcai.la==1)tc--;else td--;
" c$ q3 N3 C2 {8 W( J5 R2 J5 P        fun(select,1,M-1,ta,tb,tc,td,pcai.price);
- p. ?/ A( L" j2 q& @. o        delete[] select;
# K* {' S$ L3 [2 D; q        }
    }
    for(int i=0;i<pos;i++)
! s& {2 j9 s7 J4 w    cout<<alltotal<<endl;
    delete alltotal;
/ J6 j: R  s; D6 N( J/ }: D! f0 m    delete []pcai;
    system("PAUSE");
    return EXIT_SUCCESS;
# x1 S! U2 m+ m" q: I7 e. i}
void fun(int * select,int n,int M,int a,int b,int c,int d,int total)
. |. p! B9 f8 ~{
    //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;
4 S4 [! W+ b7 s: \    //getchar();
- ]: q, l: p2 T7 X$ P    //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;}
/ |# @! G2 J( B( z2 C% z- d    for(int i=select[n-1];i<N;i++)
    {
         for(int j=0;j<n;j++)if(select[j]==i)continue;
/ J5 o% d4 d4 }, ]1 C1 B( A        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))
        {
! i6 z8 ]% l7 _! h: S7 ]# ]        int ta=a,tb=b,tc=c,td=d;
        int* myselect=new int[n+1];   
. P! f. u1 Q' H        for(int k=0;k<n;k++)myselect[k]=select[k];
        myselect[n]=i;
        if(pcai.hun==1)ta--;else tb--;
) q- x6 n/ E* P* c0 N/ z8 S        if(pcai.la==1)tc--;else td--;
        fun(myselect,n+1,M-1,ta,tb,tc,td,total+pcai.price);
) H0 A  p+ |$ u, q  t4 C( W1 [1 L: c. l# e        delete[] myselect;
( Y$ G$ b  H" X2 J, w) j        }
    }
}

928171481

嗯，不错不错