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

厚积薄发

饭团的烦恼
' e6 U0 S3 M: z7 W
“午餐饭团“是百度内部参与人数最多的民间组织。

+ F0 c# }2 t4 {同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。

4 v( q8 K: X! X: u9 Q参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。

但是，随着百度的员工越来越多，各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口，饭团的点菜负责人背负的责任越来越大。现在，这个重担落在百度之星的肩上，因为，你们将要为所有的百度饭团设计一个自动点菜的算法。
- }7 q) p6 i& c' v; b1 e1 N# K
) S$ `' f7 S7 Y) E* ~( y  ~饭团点菜的需求如下：

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

0 A8 `# e& b% `, c$ Z2 ． 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。

2 A) P! r5 D# h3 ． 请紧记，百度饭团在各大餐馆享受 8 折优惠。

9 V5 s5 R2 D6 I8 s: P2 T输入数据描述如下：
5 {0 B% j* |- o+ I
第一行包含三个整数 N ， M ， K （ 0<N<=16 ， 0<M<=N ， 0<K<=12 ），分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。
: U* j. L$ s6 F
紧接着 N 行，每行的格式如下：

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

例：
0 A0 W+ W5 b8 J* _
& i* @& O  l$ s水煮鱼 30 1 1

0 g* |9 K4 P8 i5 b" |紧接着是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。
; U: l8 @7 ]/ O# f* y
输出数据：
9 I! a0 H8 H" B; k6 e2 x
. S, R5 P4 p" |4 m* @对于每一测试数据，输出数据包含 M+1 行，前 M 行每行包含一个菜名（按菜名在原菜单的顺序排序）。第 M+1 行是人均消费，结果保留两位小数。

0 r% r# S* z3 z说明：
, ?5 z) R" ~( u, c  n7 ^( U
. i) L9 @' c( q; R$ }4 h1 ．结果菜单的数目应该恰好为 M ，荤菜，素菜，辛辣，清淡菜的数目恰好为 a ， b ， c ， d 。在满足这样的前提下，选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。
" Q* {" o4 |" ~- B! y
2 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。
9 d( w5 ~8 A3 o. @( t& o
输入样例

3 2 2

水煮鱼 30 1 1

口水鸡 18 1 1
1 N* [7 X; I" ]# O
清炖豆腐 12 0 0
& N7 H7 }. A  W1 x0 D
2 o  B; ?7 R- \7 [1 _' z  H1 1 1 1

' C! n! K2 v2 p% @- m1 r' a, j
输出样例

口水鸡
. w8 f9 c9 W/ P. b; ^6 a6 n
清炖豆腐

2 o% ^! T& M% [7 A; l6 r* v/ c+ z12.00
" A: n( {8 n7 i& d0 ?2 A

; [% O& C' D2 s' N
5 W& m+ W' X& A
时间要求： 1S 之内
3 {- B: Y( E* N" {& z7 ?
example：
0 T& [# ~3 j5 @5 P: K#include <cstdlib>
. `3 l+ b. Y1 p' m9 s#include <iostream>

; z: `1 p& `6 d% musing namespace std;
8 j0 H- j/ T6 |3 r' V( T* r

struct cai
$ b$ k$ z! w, ^$ X0 ~) X7 _{
       string cainame;
3 S- T: A7 T+ p  S       int price;
) O' m- n& d8 K7 K$ e# s0 s7 m       int hun;
/ S! ?- e: ^6 a" s. Q( i       int la;
2 [1 Y; P0 j- z  s3 C       };
int* alltotal=new int[30];
- m8 B2 @' m( g" N& t# M; f  c, Mint pos=0;
9 u- A4 b$ h; @cai* pcai;
/ W; M# A8 _8 b$ `  M( kint N=3;  
9 D* n; o, ~& K1 Z; V2 m  a2 i- T- wvoid fun(int * select,int n,int M,int a,int b,int c,int d,int total);
+ u1 R5 b* r/ n  ]int main(int argc, char *argv[])
9 z  D8 I% S5 w3 _3 t" ]6 y" Q{
    int M=2,K=2;
    int a=1,b=1,c=1,d=1;
+ y+ J5 g+ o% d    pcai = new cai[N];
    pcai[0].cainame="water fish";
0 Z; d* D/ ~% M) s9 q    pcai[0].hun=1;
+ `/ b8 A) l6 ~! l( G5 ^# z; Y    pcai[0].la=1;
/ v: I* _& s* a    pcai[0].price=30;
    pcai[1].cainame="mouth fish";
3 \( s- e* _; u' ~. q( d    pcai[1].hun=1;
& _1 @4 I+ [* C    pcai[1].la=1;
    pcai[1].price=18;
    pcai[2].cainame="doufu";
    pcai[2].hun=0;
    pcai[2].la=0;
3 |% G7 z! R6 [7 ?0 c# E7 x    pcai[2].price=12;
    for(int i=0;i<N;i++)
3 i8 Q' c. ~) D6 O/ J9 y( A    {
4 y) q- O3 m* d) 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;   
        int* select=new int[1];   
        select[0]=i;
        if(pcai.hun==1)ta--;else tb--;
, s! B+ }3 ^/ }, k9 ]1 R) p        if(pcai.la==1)tc--;else td--;
6 |+ u, O4 @( L; R3 G        fun(select,1,M-1,ta,tb,tc,td,pcai.price);
        delete[] select;
0 N+ x* ?3 Q5 j2 w# P- y, m9 [        }
    }
    for(int i=0;i<pos;i++)
    cout<<alltotal<<endl;
/ t& O- ~* [# g. y    delete alltotal;
    delete []pcai;
    system("PAUSE");
    return EXIT_SUCCESS;
8 Z# T9 {4 v- K3 |) v* a}
) }0 t: S: g5 s2 o/ Qvoid fun(int * select,int n,int M,int a,int b,int c,int d,int total)
{
# N% I% R; z. ?    //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;
& M5 \0 {, b6 l0 d1 a8 R4 e  O    //getchar();
' }1 f/ l" F: y8 h    //cout<<n<<"|"<<M<<"|"<<a<<"|"<<b<<"|"<<c<<"|"<<d<<"|"<<total<<"|"<<endl;
2 X( n* c, T  q7 L    if(M<=0 && (a>0||b>0||c>0||d>0)){cout<<"impossible"<<endl;return;}
$ {0 a- j2 Z! _/ K; q+ M) n9 @    if(M<=0 && (a<=0&&b<=0&&c<=0&&d<=0)){cout<<total<<endl;alltotal[pos++]=total;return;}
9 w+ q- f0 _; w4 Y0 T3 n0 H    for(int i=select[n-1];i<N;i++)
! ]8 W2 G; \9 D7 R. o    {
  t; @0 _1 t  r5 Y/ y4 s         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))
        {
3 J: a( ?; j; R* ~2 u) ?        int ta=a,tb=b,tc=c,td=d;
# m' ?4 r$ }- W( ~- e4 W* z4 E' v2 r        int* myselect=new int[n+1];   
& z6 g6 A1 F' Q/ z, Q        for(int k=0;k<n;k++)myselect[k]=select[k];
- d% R+ d, k( S2 ~  ^0 j/ e* J1 L/ T$ \        myselect[n]=i;
+ k. F" ~3 x; n& z! y$ r        if(pcai.hun==1)ta--;else tb--;
9 p  k) P0 A4 @& A        if(pcai.la==1)tc--;else td--;
# H1 O! e2 r9 W9 B! {        fun(myselect,n+1,M-1,ta,tb,tc,td,total+pcai.price);
2 b& F+ E+ T" r& m2 a9 J# e9 y        delete[] myselect;
. w1 X, ]9 G8 c9 i: R3 i        }
    }
* @" F2 m7 Z; p' n}

928171481

嗯，不错不错