饭团的烦恼 9 U8 _' J7 ] U
7 V+ ^8 U$ ~% d, ~“午餐饭团“是百度内部参与人数最多的民间组织。
8 A: p3 d8 u3 p c8 m6 _: D8 t9 k+ Y# E# d+ q% I
同一个部门的,同一间大学的,同一年出生的,用同一种型号电脑的,员工们总是以各种理由,各种借口组织各种长久的,临时的饭团。
7 y3 }( S% F' I! w4 k( D
! ]$ C- w W8 Q6 R: Y- c参加饭团,不仅可以以优惠的价格尝到更加丰富的菜式,还可以在吃饭的时候和同事们唠唠嗑,吹吹水,增进感情。
% [2 U) I3 D a0 r U2 g, }9 I; x+ q2 c% s ^
但是,随着百度的员工越来越多,各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口,饭团的点菜负责人背负的责任越来越大。现在,这个重担落在百度之星的肩上,因为,你们将要为所有的百度饭团设计一个自动点菜的算法。
* L* Q$ q2 T0 a# c6 x* {
6 {3 @. D. a1 M2 X4 ^8 G' f- T饭团点菜的需求如下: & l# D r" \/ x7 V. o
6 {4 j6 d; R* A W5 P
1 . 经济是我们要考虑的一个因素,既要充分利用百度员工的午餐补助,又不能铺张浪费。因此,我们希望最后的人均费用越接近 12 元越好。 8 z/ M$ g) Q; ~& t* Y' X5 R2 _
, m) Q! ?) ^) [/ n( g8 H7 v2 . 菜式丰富是我们要考虑的另一个因素。为简单起见,我们将各种菜肴的属性归结为荤菜,素菜,辛辣,清淡,并且每个菜只能点一次。
; X" x1 U! {. c
! d$ `9 S- I1 Y }3 . 请紧记,百度饭团在各大餐馆享受 8 折优惠。 m0 ?, r! ^3 k- q. M, f, j/ q6 \4 V
3 U4 i. R; V1 s输入数据描述如下:
, E2 o: Z0 {0 i' x' Z' q% t% _( V0 S- c
第一行包含三个整数 N , M , K ( 0<N<=16 , 0<M<=N , 0<K<=12 ),分别表示菜单上菜的数目,饭团需要点的菜的数目,就餐的人数。 L# N! K) p: U
8 z0 ~! t" A, A8 T; G5 L6 m紧接着 N 行,每行的格式如下:
( E0 s7 J8 l' Z6 y! }0 o' y/ A& [: h
菜名(长度不超过 20 个字符) 价格(原价,整数) 是否荤菜( 1 表示是, 0 表示否) 是否辛辣( 1 表示是, 0 表示否) 7 H* v6 @( G3 m R7 H, M9 K
' _2 S& o4 L$ s* P: _' l2 X% j
例:
* }, I, F$ | L( S _8 R* u2 D9 T; Y
水煮鱼 30 1 1
( j& V! L% L1 X2 {3 l
% X) T" y( ^! Y$ w: z4 P& A) \; p4 g紧接着是 a b c d 四个整数,分别表示需要点的荤菜,素菜,辛辣,清淡菜的数目。
" ~+ {: g9 [8 ~3 k9 ?4 Q" q# @. L1 D- H
输出数据:
9 s2 f D* `; V' L3 R- E/ D; I" D; k" R, X. k* F
对于每一测试数据,输出数据包含 M+1 行,前 M 行每行包含一个菜名(按菜名在原菜单的顺序排序)。第 M+1 行是人均消费,结果保留两位小数。 ; B6 W# X1 [9 s; Y3 T
# L+ l- K. t; V1 s( V
说明:
. c# }1 a' ]7 f& x! F) u4 }* ?4 a- o9 V
1 .结果菜单的数目应该恰好为 M ,荤菜,素菜,辛辣,清淡菜的数目恰好为 a , b , c , d 。在满足这样的前提下,选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。
+ Y7 b' d& f3 k( }! r+ A4 T
: z4 v) |7 ]4 \2 .每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。 / q% x0 ~) z3 k. r
! h! ]* L7 E: @8 r- L) \( z
输入样例 / \2 Z# b( e, Q6 w! b* s# s
3 2 2
/ }( o, }1 J3 ?2 C9 M: ~( c4 t, i' _
- M! u( k6 _; p/ M4 F水煮鱼 30 1 1 9 S C: ~0 y( ^+ d, n
' Q8 f! G b, ~口水鸡 18 1 1 : v+ }5 F5 n5 N) t% @! H
. o4 b/ R0 c. \( {# p清炖豆腐 12 0 0 $ p8 Y7 O S! T3 i
) G' W- e/ B! m$ P, {% R: R0 L1 1 1 1 $ u& W& Q. r, h& P2 p
5 y4 s- S) z' X7 W* V* ^& H6 t
) o; @! W7 B5 S" \ N输出样例 : U# {/ x1 H+ k/ d) Z
口水鸡
# y) c6 k; d$ `- m
^ Q1 H1 t1 B4 F& z5 D清炖豆腐
5 }2 Y+ G2 ` ?$ ~8 ^3 c
: v" V: ~* U3 a1 R M, p' e12.00 K, }$ G( @- I* N
- y; s# o0 J6 ^; ~5 j C9 i
3 b5 f7 u0 g4 P+ P* S5 L. y/ a! @7 V, e
时间要求: 1S 之内 : ?3 n3 L% J! a* X0 d7 v
8 L" L& E7 \; t- T1 r1 p! f" n
example:
6 P0 e; J# q! m4 k#include <cstdlib>4 P0 q7 p ~5 J7 Z- |/ Y! L
#include <iostream>
1 q, p3 B: l% c# P6 V5 F- q
, I1 x# M L4 o% p, Gusing namespace std;5 k- i, q2 b1 Z6 ?( h5 [
/ w( F$ U" B. H$ q+ x0 }, d: B9 {4 Z/ T% w9 Y0 d8 w
struct cai
$ e0 c E" M) s' @2 U5 v{( y; T! M5 `9 \
string cainame;5 r# m* U3 L5 I- {2 c6 s% _
int price;
! Q- [; B, S K- n$ a int hun;
7 }) f/ n& i$ L- w int la;
+ A s# G0 e! W a };& [- {- G% ]1 p, J% I
int* alltotal=new int[30];
. ^, D2 ~8 P7 d- z' y$ R6 u; ? U! hint pos=0;
9 i* \! ^% z$ z! w& `& j+ rcai* pcai; , C8 I6 g/ R( c( ^
int N=3; ; H- t; _) ^/ i y! Y
void fun(int * select,int n,int M,int a,int b,int c,int d,int total);
% l# p* G5 b/ A. k( i! ^int main(int argc, char *argv[])
! [) U3 S% r$ z* ^{
5 q% K% u5 |1 C+ y; N9 O int M=2,K=2;7 t! a$ @5 f6 ?3 }( Z6 D
int a=1,b=1,c=1,d=1;8 V( b' \( e/ {0 @1 k# I
pcai = new cai[N];
' X. l4 A8 r! i9 G& p; ~3 @. _ pcai[0].cainame="water fish";# c7 E5 ]# H& W
pcai[0].hun=1;
7 o% L- J4 ^3 t8 |. t# N pcai[0].la=1;
) e- W/ B6 u. ~ pcai[0].price=30;5 j0 [! D- G" d. b( g( d* ]
pcai[1].cainame="mouth fish";, V1 W1 `8 ^4 a, {5 j
pcai[1].hun=1;
7 {' k5 x2 l. }8 G pcai[1].la=1;
, m+ p) y7 ]. C" S pcai[1].price=18;
- y! @7 E) X# J pcai[2].cainame="doufu";
1 ?" { U6 P8 t: j. Q6 v( S& \ pcai[2].hun=0;
" B* C% i' S" J' b( i pcai[2].la=0;( H- R2 K7 b; U! i- g# z6 l
pcai[2].price=12; , I; e" Z+ T- g& f/ ?5 p
for(int i=0;i<N;i++)- d4 o+ w5 N5 V7 p+ C
{, f- z+ `, h6 g( \
if( (pcai.hun==1 && a>0) ||(pcai.hun==0 && b>0) || (pcai.la==1 && c>0) || (pcai.la==0 && d>0))4 c: [* N0 t6 _' |& W% C# R; D
{
% P ^2 Y; P+ L# d int ta=a,tb=b,tc=c,td=d;
6 k! R+ S1 |0 q( r5 {5 P1 X' S int* select=new int[1];
- N4 P# G, g @ select[0]=i;
7 Z. u, L2 D6 e3 u" i; Y/ M7 _ if(pcai.hun==1)ta--;else tb--;
5 q. ~7 h/ |( O5 v( g if(pcai.la==1)tc--;else td--;
- b: A6 e% F% `6 }# F fun(select,1,M-1,ta,tb,tc,td,pcai.price);
' T9 ?6 }" M+ I5 H9 m delete[] select;
: ^4 ^" j$ M/ c" F/ U }. B, v5 e# K7 m( b% T" C- V
}
# {. ^* ?0 n% M# S5 f for(int i=0;i<pos;i++)
' h0 d/ O, {/ c( a" @6 v5 l1 W cout<<alltotal<<endl;+ u/ u) h% t B
delete alltotal;
1 e' o: ]" t: F' ] delete []pcai;
7 Y2 c* ?2 X+ h; E system("PAUSE");7 |/ n7 j" c" O6 ]9 r
return EXIT_SUCCESS;. u/ h% j" K% P% n9 J
}' l/ S3 X( Y: v% p# z$ B! P
void fun(int * select,int n,int M,int a,int b,int c,int d,int total)
- I) S X, Y- S" Y0 N: z# ]5 i{/ D$ G3 ~5 D4 U
//if(a<=0&&b<=0&&c<=0&&d<=0)return 0;
. U/ P+ {* Y+ [! i1 z, C! j //getchar();& m( [2 j: u' H. z$ Z. J
//cout<<n<<"|"<<M<<"|"<<a<<"|"<<b<<"|"<<c<<"|"<<d<<"|"<<total<<"|"<<endl;7 l8 W- p! L1 X. T2 f7 A
if(M<=0 && (a>0||b>0||c>0||d>0)){cout<<"impossible"<<endl;return;}5 y' z2 [, b9 {2 n. i% i2 ^1 h
if(M<=0 && (a<=0&&b<=0&&c<=0&&d<=0)){cout<<total<<endl;alltotal[pos++]=total;return;}
. R8 A: v+ N* @. k for(int i=select[n-1];i<N;i++)8 q6 {; J$ Z) D9 ^1 A7 G* Q
{* t+ X$ h/ H5 i2 k" t
for(int j=0;j<n;j++)if(select[j]==i)continue;" D- V. N4 Q8 y( w# l5 R
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 c% T; Q9 f* M
{6 g) A' V! C6 u4 ~! U' V
int ta=a,tb=b,tc=c,td=d;. b) }6 o0 R# {
int* myselect=new int[n+1]; 7 U/ Z1 I8 w ? J2 z, B; V o
for(int k=0;k<n;k++)myselect[k]=select[k];
1 `, R; P0 E! X6 f myselect[n]=i;3 j; ?* Y9 S( W+ X: l% `
if(pcai.hun==1)ta--;else tb--;
3 V/ g( a; ]2 J6 B( K if(pcai.la==1)tc--;else td--;/ o) h7 D9 U2 B# m
fun(myselect,n+1,M-1,ta,tb,tc,td,total+pcai.price);' H( a; q: T/ v+ a& M/ ], l
delete[] myselect;
0 L5 F1 a! i8 a5 H" x) M { }
6 @! G' Q/ H6 d# F( V+ d" |9 W, \% w }2 Q- i9 T, W) R J/ h; G
} |