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

厚积薄发

饭团的烦恼
/ X, a/ z0 J  B, [5 F; h0 ~
“午餐饭团“是百度内部参与人数最多的民间组织。

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

. C' y( d9 [9 f参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。
) ~% }3 H: Y0 O9 _# b- H0 R  e2 G
7 a2 A2 ~" w" k但是，随着百度的员工越来越多，各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口，饭团的点菜负责人背负的责任越来越大。现在，这个重担落在百度之星的肩上，因为，你们将要为所有的百度饭团设计一个自动点菜的算法。
' _$ _1 `7 h1 K+ ~
+ `7 k% Y# U2 e, j; P饭团点菜的需求如下：
; I; c# v: C, n: e, [
2 K4 {; u( o) p+ O- v- w1 ． 经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近 12 元越好。

2 ． 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。
& Y# Y1 ]% c) I/ @
- O3 p  f" h% P* @) ]3 A. q3 ． 请紧记，百度饭团在各大餐馆享受 8 折优惠。

输入数据描述如下：

9 {: g4 S  ?4 D( F% p3 U0 y) j9 O: V7 B第一行包含三个整数 N ， M ， K （ 0<N<=16 ， 0<M<=N ， 0<K<=12 ），分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。

, w1 o$ G. Q$ ^6 f; j4 J0 f紧接着 N 行，每行的格式如下：

; p0 |/ S$ t( k1 E7 h+ X菜名（长度不超过 20 个字符） 价格（原价，整数） 是否荤菜（ 1 表示是， 0 表示否） 是否辛辣（ 1 表示是， 0 表示否）
# |0 Z4 m1 k+ Q, V: n$ f
8 z/ h. |/ d7 m) f" x; K' }) ]  s4 y* i例：

水煮鱼 30 1 1
6 ~8 y$ Z5 |( p/ v2 @! \6 v7 C* D
: K4 J8 u+ E# G5 y) ]紧接着是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。
+ }5 G+ d) c7 t3 E3 p
输出数据：

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

说明：
: O4 G5 y, ~- Q, B" t" ?6 j* n1 h
1 ．结果菜单的数目应该恰好为 M ，荤菜，素菜，辛辣，清淡菜的数目恰好为 a ， b ， c ， d 。在满足这样的前提下，选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。
# T0 p( O$ M, Q5 O' l, u
2 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。

输入样例

! B  M3 ?- f# S' f5 R4 f0 r3 2 2

0 K$ h8 S& s4 |. @水煮鱼 30 1 1

口水鸡 18 1 1
' F5 U2 B, }5 j4 T4 N
+ i# X4 ^6 f* f! D/ }2 u清炖豆腐 12 0 0
9 R" h1 ~) V1 Y; M' o4 R" T: H
1 1 1 1
2 {6 @1 D  w! U/ f2 O1 V

输出样例

口水鸡
% x) d) _! J: b5 \4 k& F
清炖豆腐

12.00
) P' |5 l! m$ u5 M* \

3 O0 A# n5 H' j4 q

时间要求： 1S 之内

+ F4 A0 A$ d2 T5 R% A: V# wexample：
2 X, F8 g$ e3 u- C#include <cstdlib>
4 `  F! f: Z6 m* E#include <iostream>

using namespace std;
6 d" a0 C0 A1 @5 o& K# B

0 @5 P& d6 C  W! }* c, Z/ ?4 sstruct cai
{
2 ~& r0 h8 o# ?8 U8 p/ n$ F4 l       string cainame;
       int price;
       int hun;
       int la;
9 M1 R% X0 X* d3 _% k) @( Q       };
- d# t! d- J- Z5 L+ jint* alltotal=new int[30];
% U+ z; D  p+ ?% a: [; z% yint pos=0;
. [7 B4 u+ X* ecai* pcai;
$ d6 l3 {( Q- v* F# \: `int N=3;  
void fun(int * select,int n,int M,int a,int b,int c,int d,int total);
int main(int argc, char *argv[])
{
    int M=2,K=2;
    int a=1,b=1,c=1,d=1;
- Q& H# U5 ]+ Y1 R4 A: ]" {7 Z# m' }    pcai = new cai[N];
8 [# n3 {# ?8 e8 c+ k/ m    pcai[0].cainame="water fish";
    pcai[0].hun=1;
    pcai[0].la=1;
1 E2 Y' D  c6 W    pcai[0].price=30;
: u) L: U7 w$ M) t% g% c9 E. y: l    pcai[1].cainame="mouth fish";
" W1 }+ z, O8 @    pcai[1].hun=1;
! I, S4 K+ k& _    pcai[1].la=1;
    pcai[1].price=18;
    pcai[2].cainame="doufu";
    pcai[2].hun=0;
' d: o6 V% `. U5 W    pcai[2].la=0;
- O8 t' H! F+ y; H* l    pcai[2].price=12;
    for(int i=0;i<N;i++)
    {
0 n1 B: m, ]: G3 N8 p1 P* K. u# S        if( (pcai.hun==1 && a>0) ||(pcai.hun==0 && b>0) || (pcai.la==1 && c>0) || (pcai.la==0 && d>0))
/ z, ^' _3 U0 x# r& `        {
/ M2 y& Q" {; P; d  t        int ta=a,tb=b,tc=c,td=d;   
        int* select=new int[1];   
        select[0]=i;
        if(pcai.hun==1)ta--;else tb--;
. P0 ^& Q* \6 R; E$ E        if(pcai.la==1)tc--;else td--;
        fun(select,1,M-1,ta,tb,tc,td,pcai.price);
        delete[] select;
        }
    }
    for(int i=0;i<pos;i++)
. Q5 Q( a$ C3 ]: l$ t) Q" J4 p    cout<<alltotal<<endl;
/ J  |" a& l: B; ]" v2 K    delete alltotal;
2 a! w: p. y2 q7 b  o    delete []pcai;
    system("PAUSE");
; i$ z5 {0 [9 `" `" G    return EXIT_SUCCESS;
}
( O* L6 _* J1 W7 n/ T$ t' w; k6 A; Lvoid fun(int * select,int n,int M,int a,int b,int c,int d,int total)
, e0 i+ F  D$ |# a: j. m+ ~{
    //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;
: x! n+ a! X: @0 \# x4 f    //getchar();
# N$ Q; ]2 U+ V5 |5 C! q' h    //cout<<n<<"|"<<M<<"|"<<a<<"|"<<b<<"|"<<c<<"|"<<d<<"|"<<total<<"|"<<endl;
: U7 p$ f) ^8 e; H! [4 ]# U    if(M<=0 && (a>0||b>0||c>0||d>0)){cout<<"impossible"<<endl;return;}
/ M) M' J# y' T! p* a    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++)
    {
& [, P; u' v$ o. \         for(int j=0;j<n;j++)if(select[j]==i)continue;
8 G' `. \9 m" }, h        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))
        {
, x  a  g( C5 M$ X5 a& |        int ta=a,tb=b,tc=c,td=d;
1 I8 U9 Q0 \, y+ W        int* myselect=new int[n+1];   
        for(int k=0;k<n;k++)myselect[k]=select[k];
" _$ s9 F! \( s! j        myselect[n]=i;
( {4 o2 Q  v# d        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);
' R: Z8 _/ h0 m( A( W        delete[] myselect;
        }
    }
2 f5 g/ z" l5 `7 c3 }}

928171481

嗯，不错不错