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

厚积薄发

饭团的烦恼
* @+ K0 a! u5 y, t
“午餐饭团“是百度内部参与人数最多的民间组织。

4 e+ ?0 h" L  j7 B7 i( W: {同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。
+ Q4 L* z8 l. p
参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。

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

8 B; D2 w* s# J7 n) h$ p8 ]饭团点菜的需求如下：
( F' w* p& L" a' h9 h- M9 v
/ l- `* z. g2 O1 o4 ]) d5 z' m1 ． 经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近 12 元越好。

2 ． 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。
0 {- f% B( [' ~2 y5 g
  x( _; v2 U+ O) p  ~0 E9 I3 ． 请紧记，百度饭团在各大餐馆享受 8 折优惠。
9 o* q2 b- w/ @8 C' q1 L
( `9 f" _( K7 W  b: t! q输入数据描述如下：
( t: e5 A' F! h: T
' B6 E, ]9 F* Z+ c/ ?; n" |第一行包含三个整数 N ， M ， K （ 0<N<=16 ， 0<M<=N ， 0<K<=12 ），分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。
3 g# z: l$ i7 `0 y
$ j0 n$ y% ^) K, w9 h! b" d紧接着 N 行，每行的格式如下：
6 K" d, N7 A' O% p1 {7 K
" r0 I0 y  [/ T. K2 X- C/ v菜名（长度不超过 20 个字符） 价格（原价，整数） 是否荤菜（ 1 表示是， 0 表示否） 是否辛辣（ 1 表示是， 0 表示否）

例：

水煮鱼 30 1 1
0 T6 e  j& d/ U
紧接着是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。
1 d# T0 H3 Y/ y; j
输出数据：
& x/ ]/ q2 K: x0 ^0 @
; S- I2 Y3 [3 h9 v对于每一测试数据，输出数据包含 M+1 行，前 M 行每行包含一个菜名（按菜名在原菜单的顺序排序）。第 M+1 行是人均消费，结果保留两位小数。

$ q( F  r* s! [: \$ h) E; D7 L: Y说明：

1 ．结果菜单的数目应该恰好为 M ，荤菜，素菜，辛辣，清淡菜的数目恰好为 a ， b ， c ， d 。在满足这样的前提下，选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。
. i! E  ^! ~1 j; r) i& I) ?
2 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。

5 D: Z( W8 u, ~, H$ s( z1 n6 \5 i输入样例

* \# u" {3 W. o; S5 S) J3 2 2
5 E* b1 O: a/ U" B( D8 l4 Z
水煮鱼 30 1 1

2 S4 r( \7 I7 }- u  R+ @* m口水鸡 18 1 1
. v2 z! |8 d8 g+ I% c
清炖豆腐 12 0 0
9 j% g+ u% Y# Q  G1 m8 W: j% X) g
1 1 1 1

, ^. B$ |, `8 J+ I8 F" a
输出样例

口水鸡

1 r% h/ s9 ?4 K2 B" Y清炖豆腐
( y  v6 j! T) f
12.00
  g0 N3 ~' r+ t" f# R6 q+ n" H5 J

$ @. ~9 t" X$ i2 f# g时间要求： 1S 之内

example：
#include <cstdlib>
% a( b% G7 M. }, g- a& r#include <iostream>

using namespace std;
0 ]. M' d/ {1 S$ F
2 `9 S1 ^# W" K2 W8 c
/ G% l9 N0 d! w7 e! I9 Nstruct cai
5 t  c/ _+ N  c( ]+ U{
       string cainame;
2 w: O# @5 S' B( ?8 q* ~* K7 z: h       int price;
- G  p. C5 H$ r0 K' G       int hun;
       int la;
       };
8 K/ H( K& Y* F4 P5 i' @& {1 H2 [int* alltotal=new int[30];
# L! o7 B1 m+ gint pos=0;
cai* pcai;
int N=3;  
$ z- V1 o& G. ~" Q1 rvoid fun(int * select,int n,int M,int a,int b,int c,int d,int total);
int main(int argc, char *argv[])
{
' @  f; j; y! {3 X8 e* D; ~" Z9 S    int M=2,K=2;
    int a=1,b=1,c=1,d=1;
! _9 @# b, m1 d* _! A/ e9 I    pcai = new cai[N];
/ f2 |# F, X" T' N  F* c" `    pcai[0].cainame="water fish";
    pcai[0].hun=1;
    pcai[0].la=1;
    pcai[0].price=30;
! F& ~2 C: u9 Q5 H    pcai[1].cainame="mouth fish";
    pcai[1].hun=1;
) o( O7 M7 M- L; q; m/ a" u- z    pcai[1].la=1;
$ I3 i) n1 c8 e7 @( j7 \    pcai[1].price=18;
    pcai[2].cainame="doufu";
" ^9 L) J  ^" m2 _9 k" E+ j0 g- Q: Y    pcai[2].hun=0;
8 G  y  Z. u4 c! w    pcai[2].la=0;
    pcai[2].price=12;
7 q+ @: ?% e8 i3 J! r5 O    for(int i=0;i<N;i++)
  O# p8 @2 x6 q3 i3 C& N    {
        if( (pcai.hun==1 && a>0) ||(pcai.hun==0 && b>0) || (pcai.la==1 && c>0) || (pcai.la==0 && d>0))
        {
" k7 ~4 i2 E# J+ K! i/ n        int ta=a,tb=b,tc=c,td=d;   
        int* select=new int[1];   
        select[0]=i;
        if(pcai.hun==1)ta--;else tb--;
! ?2 U/ E8 N% C# e/ X% J, c        if(pcai.la==1)tc--;else td--;
- L$ I1 `& G9 B) _        fun(select,1,M-1,ta,tb,tc,td,pcai.price);
        delete[] select;
5 d& f9 b( [. A  g# {        }
. c8 U9 o+ O( J' P- A* b    }
    for(int i=0;i<pos;i++)
! W2 F9 I2 ~* X9 L) k8 Y6 j0 X8 `" H    cout<<alltotal<<endl;
    delete alltotal;
    delete []pcai;
    system("PAUSE");
& o' f4 Q. W8 w    return EXIT_SUCCESS;
" z# l1 r& ~" A) z7 V$ \}
) T6 i2 o8 \4 [2 l$ E3 A2 Zvoid fun(int * select,int n,int M,int a,int b,int c,int d,int total)
{
7 l6 F  a. P& I) T# Q; V    //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;
    //getchar();
( l& G4 t" k$ \. }2 {4 k2 r. 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;}
3 {9 w) j& N' X$ b2 c    if(M<=0 && (a<=0&&b<=0&&c<=0&&d<=0)){cout<<total<<endl;alltotal[pos++]=total;return;}
) u8 y: U$ `) e9 C- Z  b8 w    for(int i=select[n-1];i<N;i++)
    {
6 Q3 H% f0 S; H* B- X         for(int j=0;j<n;j++)if(select[j]==i)continue;
- |9 Q0 l% R- t+ {+ t        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))
        {
        int ta=a,tb=b,tc=c,td=d;
0 z; j+ [' Y# ?* g) d        int* myselect=new int[n+1];   
        for(int k=0;k<n;k++)myselect[k]=select[k];
4 L6 s0 D: c+ j# P# x9 d        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;
, s3 E, e- S% P& K7 i        }
9 q* \+ {& a' x* G    }
* h) D1 {0 {) q) A; ?1 e}

928171481

嗯，不错不错