饭团的烦恼 ' R+ v8 |% d9 [7 q' m n6 G
" S/ y9 S' x9 b' l
“午餐饭团“是百度内部参与人数最多的民间组织。
2 l( A0 S$ X( U" e% u* _. M' y% i, L+ A
同一个部门的,同一间大学的,同一年出生的,用同一种型号电脑的,员工们总是以各种理由,各种借口组织各种长久的,临时的饭团。 0 ` y, v7 j' `+ @" n. @. M3 }
7 s& n' F& F j6 E# Y1 |; C ~
参加饭团,不仅可以以优惠的价格尝到更加丰富的菜式,还可以在吃饭的时候和同事们唠唠嗑,吹吹水,增进感情。 4 d5 _: n. O9 y, U4 j
g. E* J% {7 \: ^4 D但是,随着百度的员工越来越多,各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口,饭团的点菜负责人背负的责任越来越大。现在,这个重担落在百度之星的肩上,因为,你们将要为所有的百度饭团设计一个自动点菜的算法。
) `# B. _0 I( \; E: B' _+ s8 z, ?9 q+ y( s! g* \/ V1 |0 U0 C
饭团点菜的需求如下:
/ F9 R& G$ W1 R6 V' o5 I) o9 [0 D
+ W4 r+ Y+ K* f9 e3 E9 J1 . 经济是我们要考虑的一个因素,既要充分利用百度员工的午餐补助,又不能铺张浪费。因此,我们希望最后的人均费用越接近 12 元越好。
) Z9 ~# d0 B& ?6 R# P/ z* p3 w* F- K" G6 F6 L! G
2 . 菜式丰富是我们要考虑的另一个因素。为简单起见,我们将各种菜肴的属性归结为荤菜,素菜,辛辣,清淡,并且每个菜只能点一次。
5 k* U3 E( \0 R/ e: f
; t, K8 U, J5 |/ B5 l3 . 请紧记,百度饭团在各大餐馆享受 8 折优惠。
% n, g1 Q1 n# Z$ w9 I6 I! o2 k6 X/ e# d7 G9 y N# J
输入数据描述如下: ; k, J: w: c5 i; v
/ t; G) H3 T2 G) }' _7 X第一行包含三个整数 N , M , K ( 0<N<=16 , 0<M<=N , 0<K<=12 ),分别表示菜单上菜的数目,饭团需要点的菜的数目,就餐的人数。
/ A, H* W* ]2 a' G6 I( u* a1 D2 w9 |
5 m+ m# d, h! o紧接着 N 行,每行的格式如下: 0 x/ x0 u) \: @! E0 w
5 J& X9 v N! S4 h: ]菜名(长度不超过 20 个字符) 价格(原价,整数) 是否荤菜( 1 表示是, 0 表示否) 是否辛辣( 1 表示是, 0 表示否)
* C* J2 b y: y( E3 J' d0 i- s, b* u# D( D6 Z+ l
例:
% }1 W: \ V5 w% ?$ \' n* m1 x2 g4 G9 U L
水煮鱼 30 1 1 * q: i$ K; Z4 b9 h* W) {
; t2 `6 J& n1 W; ^% h" T: B+ ?% y! B, w
紧接着是 a b c d 四个整数,分别表示需要点的荤菜,素菜,辛辣,清淡菜的数目。
) [8 G) ^3 O, [' @$ O5 m4 R9 y$ ?8 p+ S+ g
输出数据:
( l e% a, E; i6 |( ]7 P
b1 g. q' C( n( x0 H9 r0 ^. @4 D对于每一测试数据,输出数据包含 M+1 行,前 M 行每行包含一个菜名(按菜名在原菜单的顺序排序)。第 M+1 行是人均消费,结果保留两位小数。 3 E/ a) r# t% o, g
! U0 u9 v, v- X5 D2 |! P说明: # q0 F7 l& H9 Q
' r x+ q% L( N2 d/ Q% a1 .结果菜单的数目应该恰好为 M ,荤菜,素菜,辛辣,清淡菜的数目恰好为 a , b , c , d 。在满足这样的前提下,选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。 " ~+ V0 G- [6 C$ N- Z
9 B4 Q7 B% S0 m# @1 t
2 .每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。
' b' K7 T4 B+ y/ Z' A4 ]% K1 c0 m- U! z3 z
输入样例 8 g# ~; h1 l$ r- l
3 2 2 5 V5 N+ V. c3 L" l- ~) {
3 J1 x& j, l* c% E/ s0 K+ a水煮鱼 30 1 1
/ d2 s& |- e5 P% X9 H0 k1 N( Q, h
) Y4 S7 ]* N- e2 D+ k5 `; W口水鸡 18 1 1 . q: K9 k4 ^- f! X0 D; C
! ]5 \7 j* m/ @0 x2 a清炖豆腐 12 0 0
9 K+ k7 ~' D {+ V5 E! i5 Q7 d4 }, I) q, z6 i' ]% W
1 1 1 1 C5 [, R' U7 \6 Y
8 b2 }! d0 E2 F8 V! S4 P# Y6 Z
+ X, m; }' I( O4 f) {1 M& d输出样例
$ H9 V9 a; N, G8 t `/ S) D3 n口水鸡 ( v0 V* E4 ^# j4 r2 W
9 U2 N8 x: y. l4 `# b$ x8 u清炖豆腐
& \% y7 @9 a4 l( |; z i( A
$ c4 I. D+ x3 ?, |: M$ V12.00
3 c2 z! A, ^6 n, Y
, ^8 b G: a6 S' l* G+ h# X/ x( r. b/ m; E& e
0 O) V9 g3 x: F( I: P# z时间要求: 1S 之内 $ z& `2 Q9 J( w& p& U, ~9 J8 B( J
* G$ X% R& F! _. c
example:
/ q# u3 k. N5 b$ d% n# i#include <cstdlib>
8 Z8 E1 k! y |% }. l! r' k% y#include <iostream>' c4 M# G/ v( ~, L
0 K% k0 l6 u9 |using namespace std;
! w s n* @+ _/ x7 ?. h% |4 W) V- e5 B9 A2 U
/ Q. |) H4 A, e8 w
struct cai+ v4 a+ {' I% u: o+ w6 V
{/ e& d& b$ o0 Q; S1 `6 Y9 X, u- q
string cainame;
+ B$ a; Y6 C6 g# q int price;$ I! n( J( `- Q1 m1 O
int hun;% C9 B A. M4 {4 w0 T* Z ^
int la;
7 Z% s" Z* V9 w P% j6 P1 B };, M/ x! }3 b& k8 W
int* alltotal=new int[30];
: a( r! Q( R- ~ Fint pos=0;
' t# F: F, D) F- _! Rcai* pcai; ; m2 U# h' a' E+ Q) T1 ^
int N=3; 5 Q% ?! c$ Y! D" }8 V
void fun(int * select,int n,int M,int a,int b,int c,int d,int total);
+ V) h4 w! R4 N& X2 L) a+ Jint main(int argc, char *argv[]). S, {0 B9 d4 F. P. g0 x0 M
{: C( N3 |: V7 e9 }
int M=2,K=2;' ^4 [. J, f3 }- ^6 _ Z+ s( z) B9 I4 _
int a=1,b=1,c=1,d=1;0 q1 z5 C) H% N# g' c2 @0 n% v1 R
pcai = new cai[N];5 K! C& I) ~8 r; o- ^" A! v& Z& |
pcai[0].cainame="water fish";: }3 Q# G. n3 p% S
pcai[0].hun=1;
: R7 @' v! [; q8 w pcai[0].la=1;
4 \4 k, U/ j( a8 W pcai[0].price=30;
[6 y9 i" [% @" u( o% | pcai[1].cainame="mouth fish";6 V# m- S4 A# @" W9 @, e
pcai[1].hun=1;
1 \4 Z. w6 X) v% w. n pcai[1].la=1;
* n' S. y$ S1 i4 b f pcai[1].price=18; / v% I* H Y/ |+ o; A+ D+ t
pcai[2].cainame="doufu";
5 Y: p% z" q: h3 [, J pcai[2].hun=0;
% r3 x8 |0 x1 D1 [. l pcai[2].la=0;
. E' L7 ~5 K1 z; R$ D% { pcai[2].price=12; 2 u0 \: l' g1 b! s# z4 @* x
for(int i=0;i<N;i++)3 w& u+ v* ?8 M2 i Z! g
{0 s9 X- B- f- _5 O" ]9 q5 `; ^
if( (pcai.hun==1 && a>0) ||(pcai.hun==0 && b>0) || (pcai.la==1 && c>0) || (pcai.la==0 && d>0))
& h9 N1 A n$ e; o/ L7 j {/ n0 j8 H; ~. S% {/ [8 w# H0 w
int ta=a,tb=b,tc=c,td=d;
- I5 R% S& U' X3 k N int* select=new int[1]; 8 S* h8 g9 s( ~ a& `% j8 Z
select[0]=i;& N9 r) @, a+ l
if(pcai.hun==1)ta--;else tb--;& d8 Z# s: C5 \/ u
if(pcai.la==1)tc--;else td--;6 F& M: M2 v8 [9 u: z
fun(select,1,M-1,ta,tb,tc,td,pcai.price);1 ]* l8 _; u9 u/ F) N1 [
delete[] select;
5 h0 x6 q2 u; ]+ o; M+ \$ V/ u& O }
7 ]/ g$ w8 t) _9 O$ }! B }6 g) R8 V: w8 P3 F9 j$ ^9 _. Q$ t
for(int i=0;i<pos;i++)
' Z4 I4 _+ j1 q2 L8 D cout<<alltotal<<endl;
& P5 R$ s' ]0 k4 K) Y4 A& b delete alltotal;
, j7 H' r: |2 A! d; K/ X delete []pcai;
% r e4 J- d @! O- ]- R$ W/ Y8 r0 a system("PAUSE");& Z5 A6 H$ n- Z+ H0 `( P
return EXIT_SUCCESS;
' J- L. r: Q3 _3 E& H) \}
# ?% i T, F7 G- [5 B- e; Lvoid fun(int * select,int n,int M,int a,int b,int c,int d,int total)
8 Q' H" a$ T2 p" v1 C{
' M$ r& m7 y. R //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;' y9 {, z9 u& B j& h
//getchar();9 C- ` a3 Y9 ^/ F8 {8 o9 r$ b
//cout<<n<<"|"<<M<<"|"<<a<<"|"<<b<<"|"<<c<<"|"<<d<<"|"<<total<<"|"<<endl;! Z. J# R, [ R. G
if(M<=0 && (a>0||b>0||c>0||d>0)){cout<<"impossible"<<endl;return;}) J2 f- v W3 R/ x/ [
if(M<=0 && (a<=0&&b<=0&&c<=0&&d<=0)){cout<<total<<endl;alltotal[pos++]=total;return;}4 c6 ]7 y; ]) {# M. I% p
for(int i=select[n-1];i<N;i++)
K: v0 V; w9 {/ z8 q: i* y* H7 Q" ? {
5 S. D0 R# w. z' K6 w. J) `' L/ u for(int j=0;j<n;j++)if(select[j]==i)continue;
/ b2 a3 Q) S/ r/ s& L$ g& j 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))
6 \/ O. L2 v, x$ [6 t {5 V* s& @5 K. Z! [; G1 E @
int ta=a,tb=b,tc=c,td=d;
0 R! D) b& Q" l) e5 U int* myselect=new int[n+1]; G; `* K6 {+ p$ r( ]4 {$ i: W
for(int k=0;k<n;k++)myselect[k]=select[k];: ?8 e% l# F9 J( F+ `3 |
myselect[n]=i;5 V( K# Z( |8 ?$ W( ~; H' t
if(pcai.hun==1)ta--;else tb--;
. I; F: l* f6 L6 e* P if(pcai.la==1)tc--;else td--;% T/ ^; t4 P- r! t( G2 f
fun(myselect,n+1,M-1,ta,tb,tc,td,total+pcai.price);
" [, F4 n: ?9 | delete[] myselect;. h7 u* I, ~3 D- a
}
1 M: \* j8 ]+ r }/ f# l' E" O: J6 z
} |