饭团的烦恼
& W! N+ k1 P# U# _ P" r9 p6 ?& X
“午餐饭团“是百度内部参与人数最多的民间组织。
) a; }) F# a5 y* r/ _! ?& |; `' s1 ]7 R4 \" N" J
同一个部门的,同一间大学的,同一年出生的,用同一种型号电脑的,员工们总是以各种理由,各种借口组织各种长久的,临时的饭团。
4 M6 f( n: U8 W5 b( ?% E* E
6 S% I$ q: t4 a2 V6 k% [7 Y参加饭团,不仅可以以优惠的价格尝到更加丰富的菜式,还可以在吃饭的时候和同事们唠唠嗑,吹吹水,增进感情。 + C9 N* F1 L+ v9 n0 A$ M- f& H
+ J! k4 T; f- P2 i9 O$ g
但是,随着百度的员工越来越多,各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口,饭团的点菜负责人背负的责任越来越大。现在,这个重担落在百度之星的肩上,因为,你们将要为所有的百度饭团设计一个自动点菜的算法。
; Q' x9 `+ E9 o2 C0 B5 X, }
) y- ^7 U0 J1 X( [! h7 D+ V# y3 A! H饭团点菜的需求如下: 6 W {: M. f5 y. z. n* @" p0 T
5 r/ Z) Z8 w1 I4 j/ }- R1 . 经济是我们要考虑的一个因素,既要充分利用百度员工的午餐补助,又不能铺张浪费。因此,我们希望最后的人均费用越接近 12 元越好。
# G/ ]" T, }' _+ X: D7 M8 h0 N o0 ^8 H4 h' s! f% y/ r
2 . 菜式丰富是我们要考虑的另一个因素。为简单起见,我们将各种菜肴的属性归结为荤菜,素菜,辛辣,清淡,并且每个菜只能点一次。
9 r0 o( c5 ^' V; Y& e; Q: D+ G# a+ K' E0 C6 A. b8 ?9 _
3 . 请紧记,百度饭团在各大餐馆享受 8 折优惠。
0 Y% l G& u7 t7 A$ B% X* ~* A t
6 [# {! I0 g) h. `; {输入数据描述如下:
1 H6 J4 g7 l& {( L9 T9 i" N+ W& T2 H) J' x
第一行包含三个整数 N , M , K ( 0<N<=16 , 0<M<=N , 0<K<=12 ),分别表示菜单上菜的数目,饭团需要点的菜的数目,就餐的人数。 . N% m9 x2 ]; Z' a# C; p
9 ~ M# L1 h; q9 _: @6 o/ k0 s
紧接着 N 行,每行的格式如下: : l. O" X* ?9 r/ A
, ^: K8 y& m& ?+ [! z菜名(长度不超过 20 个字符) 价格(原价,整数) 是否荤菜( 1 表示是, 0 表示否) 是否辛辣( 1 表示是, 0 表示否) 5 L+ z. T8 ?. d6 Q/ [) f
/ t3 ?2 u$ V5 N* m例:
& m" ] K$ u& r$ a* F
$ f' B3 {! }- [4 c# n水煮鱼 30 1 1
+ `% ]4 w2 k, E1 E* D7 `5 l4 S& ^4 X. u! m3 l+ g' Q& A d; p
紧接着是 a b c d 四个整数,分别表示需要点的荤菜,素菜,辛辣,清淡菜的数目。
y; b' |7 ?0 Q6 A1 g* F X
, E2 E+ U9 \4 |: p, o: L+ j输出数据:
- B2 [1 _8 q9 V* B7 N6 X( F# h7 D8 S& ]- F* d& ]( ]/ p/ \
对于每一测试数据,输出数据包含 M+1 行,前 M 行每行包含一个菜名(按菜名在原菜单的顺序排序)。第 M+1 行是人均消费,结果保留两位小数。 ' w1 C3 m1 ? r4 C0 n" R( e
$ K5 M7 @ N2 ^
说明:
) v' U8 L- L2 B; y9 X3 L1 H$ [
9 _, r. f u) @1 .结果菜单的数目应该恰好为 M ,荤菜,素菜,辛辣,清淡菜的数目恰好为 a , b , c , d 。在满足这样的前提下,选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。 $ z( S% S7 O1 Q, d# c
% U! \% g% k" x9 }2 .每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。
) J( B- `- _, c! Q" \6 e; F# b8 c
, I; u; J) Y* \) f! L' u6 q输入样例 6 r% B1 k; _- h
3 2 2 # d+ ~. f& u+ I
) H3 ` X, j: y) [2 v* N7 C6 B水煮鱼 30 1 1 $ J( f( C: E% ?) V8 i6 Z4 n3 g
. H3 \! ]% [& x9 T; y7 o, _- m口水鸡 18 1 1 " M0 r8 q$ K: L( B: D8 i9 v
6 h" a; k* A& N0 U" _0 A- _
清炖豆腐 12 0 0 / S; a) ?: c1 |; Y. Z/ v; ]2 z
, S( ~1 f0 f4 Q L0 t1 1 1 1 & z" F, Y0 C. `/ m
5 }8 a& v! ]+ z ~
- K- ~% K4 U0 ?0 C输出样例
: b( T9 G+ S: z: c$ D4 k6 K/ }口水鸡
) N7 j) `* Q0 H" t! @
- N: p0 M+ {! Q2 R$ G! z5 D清炖豆腐 ! a0 q7 t9 i! D8 A+ S
( \8 a' Z) e. x; l" o4 D: |12.00 5 N- ]1 b6 c5 w' f7 g7 k
4 G7 C9 A9 h' q8 u' D% o3 q
. f, J% w( J$ q! Q. p2 N7 v
c0 i7 L6 ~4 k# }/ {5 f时间要求: 1S 之内 + S' [& R5 K% n1 F% v& _
3 \9 @4 k2 U/ D8 L" `% H/ Cexample: d+ W( [- w, {, I! |4 l
#include <cstdlib>
2 e- |2 F% @$ x; c& `" E#include <iostream>- J2 r/ j$ x1 C* N/ A$ U; {
& f9 W( E6 L4 h/ X% `using namespace std;
. o0 d, F& j4 O8 d" B0 b2 F, Y& p4 E8 d1 v
) E0 V1 h7 p0 U7 B! m1 q( u
struct cai
: H( f$ y9 K* q. L. ^{1 \3 z# g ^' d; o% I; P! P, K; T
string cainame;/ [* y- z5 C% }$ \ ^' G
int price;
1 o5 @; {4 \* c: e; s int hun;2 y. G; M. b3 e2 j
int la;
, B. L6 T3 K5 O+ a1 \9 G9 l* G };
# C, H& Q( I' e( d3 mint* alltotal=new int[30];
' ~5 e# y. _* S, }$ s) _int pos=0;
$ f- y5 c- K3 v% w* Vcai* pcai; q- S0 f! N7 \: ^
int N=3;
' x n1 ^# z6 D8 y% qvoid fun(int * select,int n,int M,int a,int b,int c,int d,int total);
0 }7 z( R, j+ p$ z" @9 N1 Uint main(int argc, char *argv[])
; u, \4 D8 j3 }4 c' N( _{6 b* G) L% i4 C9 O3 ~- G
int M=2,K=2;
9 ]( ?3 v# I9 y int a=1,b=1,c=1,d=1;
" @8 D( Q$ `7 Z) b# H# | pcai = new cai[N];6 C' \8 b3 p* d
pcai[0].cainame="water fish";
: a3 i/ [5 Z& q6 q pcai[0].hun=1;* U2 p2 O2 G4 j3 c4 p% y
pcai[0].la=1;, @! x* y, m. _. g- K
pcai[0].price=30;+ {$ `% [0 v. W+ B) Z# C3 n0 O
pcai[1].cainame="mouth fish";6 v1 h6 Q- L8 W+ q" ?8 v+ {3 f% d
pcai[1].hun=1;
5 O8 U9 g4 l: x/ c! h9 P' _ pcai[1].la=1;
- [3 `* s+ z, Q- Z& q0 x; Y6 W; j, ^! Y pcai[1].price=18;
0 }! V" x' g8 W; n$ S pcai[2].cainame="doufu";) b9 q( q- P# A; r9 B$ I7 q( w2 Y
pcai[2].hun=0;
. d. d& p1 A, p8 U* @1 d6 y O pcai[2].la=0;
( g. R! T0 t* t$ e' g. M pcai[2].price=12;
; L: W0 i+ r# E, r. u1 h, m3 w& k for(int i=0;i<N;i++)8 |% {( o# }& e' m2 a, m L# y5 h
{
. e" D& J+ c% Q% r5 R& o if( (pcai.hun==1 && a>0) ||(pcai.hun==0 && b>0) || (pcai.la==1 && c>0) || (pcai.la==0 && d>0))2 `" k4 ?( M4 F, P% h8 z
{! g% ]4 X3 a1 o/ m
int ta=a,tb=b,tc=c,td=d; $ V5 v- k: u0 C) n
int* select=new int[1]; 5 X: I( i! Z% P F8 ~8 m' y! a
select[0]=i;
0 F4 s# ~! k+ i w/ l if(pcai.hun==1)ta--;else tb--;
* K0 d$ E: S2 v if(pcai.la==1)tc--;else td--;
2 H' g" @+ _) q+ Q% C+ e2 n fun(select,1,M-1,ta,tb,tc,td,pcai.price); v. c& c( n$ T! u0 m
delete[] select;% x }# W2 Y7 k$ j
}! g6 t; O' j& N# S! u3 W
}
7 f6 u6 N$ G" R- B9 J% @! J3 n1 d for(int i=0;i<pos;i++)
9 e! K0 f! ~- z) K5 N cout<<alltotal<<endl;: H$ ?3 m- { U9 D: O. f% y
delete alltotal;5 }, X) e6 K: Y+ V, B1 g0 G) e
delete []pcai;0 [0 s+ n, G; Z0 q! w+ C1 ]
system("PAUSE");4 E- \' y3 [2 f8 ~
return EXIT_SUCCESS;5 F# t( C) p \! @0 t6 S
}, r G* i' V9 v; [4 Q2 O* N, k) W% d
void fun(int * select,int n,int M,int a,int b,int c,int d,int total)0 a* r, b9 Z' n7 ?) U6 l9 k
{
% @- _/ A& g( C* K y$ K. P* `9 t //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;
( f& k2 P& L6 T- j+ N5 y //getchar();( M3 \% H: }" z5 f9 b3 ?8 u
//cout<<n<<"|"<<M<<"|"<<a<<"|"<<b<<"|"<<c<<"|"<<d<<"|"<<total<<"|"<<endl;
- _5 X2 l# I! D# i0 S4 v; W0 @ if(M<=0 && (a>0||b>0||c>0||d>0)){cout<<"impossible"<<endl;return;}1 d& w' L8 u% I4 P: a
if(M<=0 && (a<=0&&b<=0&&c<=0&&d<=0)){cout<<total<<endl;alltotal[pos++]=total;return;} I& d. {& K p0 H7 R0 G! r
for(int i=select[n-1];i<N;i++), b2 p) h0 N: ]/ s1 \ [
{3 X5 ]8 ~% ~8 `. Z
for(int j=0;j<n;j++)if(select[j]==i)continue;* W+ T/ w! \& E8 O* ~$ 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))1 g9 y# Q- `) o% A" K# W9 e2 ^: g
{
5 B/ L, e2 i0 ]3 O0 n1 H int ta=a,tb=b,tc=c,td=d;5 P- k, n; }$ t
int* myselect=new int[n+1];
n3 T8 e2 ~9 d* }' ` for(int k=0;k<n;k++)myselect[k]=select[k];
6 r, x$ W8 S9 z# J/ _9 D myselect[n]=i;
) I: d( n' W4 s8 Z if(pcai.hun==1)ta--;else tb--;
/ B% I3 d* W" Y+ C% p0 d if(pcai.la==1)tc--;else td--;
& ?* v, V4 e B% \: w fun(myselect,n+1,M-1,ta,tb,tc,td,total+pcai.price);, h8 Z" B0 @( }- C; P
delete[] myselect;
* X7 o' `8 a9 U }! e0 D3 r' c* g
}! { B, @1 u7 {* Q
} |