数学建模社区-数学中国

标题: 2006 年百度之星程序设计大赛初赛题目 1 [打印本页]

---

作者: 厚积薄发    时间: 2010-5-6 18:56
标题: 2006 年百度之星程序设计大赛初赛题目 1
饭团的烦恼

# }4 B1 W4 A/ A; E“午餐饭团“是百度内部参与人数最多的民间组织。
6 i( |( h( h" h1 p3 a, M) c! R
同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。

; D8 c/ r9 F% t: R& e. H- ^参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。

但是，随着百度的员工越来越多，各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口，饭团的点菜负责人背负的责任越来越大。现在，这个重担落在百度之星的肩上，因为，你们将要为所有的百度饭团设计一个自动点菜的算法。
# g4 t# C" q1 H' B
饭团点菜的需求如下：
$ F. t9 l. m9 D6 M6 |! X) T! S
( F6 L( B" T& {1 ． 经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近 12 元越好。
3 q8 J# S! z5 f. I
4 r  C) O* F( ]- F" `2 ． 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。
- ^$ g/ L3 W  q" Q/ `, z8 @
3 ． 请紧记，百度饭团在各大餐馆享受 8 折优惠。
7 @0 ^8 H% O- A0 H9 ]8 A: y7 N( Z
( Y$ A# w& s0 K6 p3 U, Z) ^输入数据描述如下：

第一行包含三个整数 N ， M ， K （ 0<N<=16 ， 0<M<=N ， 0<K<=12 ），分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。

紧接着 N 行，每行的格式如下：
+ T! l/ X" c8 |; j" X
/ E. d$ t" a& x+ d; u& }& c菜名（长度不超过 20 个字符） 价格（原价，整数） 是否荤菜（ 1 表示是， 0 表示否） 是否辛辣（ 1 表示是， 0 表示否）

例：
' W+ U* C$ \" f' `
水煮鱼 30 1 1
, A7 w4 {% N- q, |8 [, X, |) P) R
紧接着是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。
0 \  x. c9 x6 y) s
7 W. l& W9 h9 }3 [  X" D$ R9 D; _+ h输出数据：
# ^6 R0 n* {* f
  A0 _: H: v1 `; K- z1 O3 Z1 |对于每一测试数据，输出数据包含 M+1 行，前 M 行每行包含一个菜名（按菜名在原菜单的顺序排序）。第 M+1 行是人均消费，结果保留两位小数。
1 a; ?& \/ i: i, n2 S& |# c. P, k
6 t, ~/ X2 X0 H6 R$ b* X说明：

1 ．结果菜单的数目应该恰好为 M ，荤菜，素菜，辛辣，清淡菜的数目恰好为 a ， b ， c ， d 。在满足这样的前提下，选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。

) ]- \# i- b7 n3 [. L% p/ L5 u" r2 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。

输入样例

. k9 [3 B0 C( A: }9 D& o  b* i3 2 2
: w" x4 q5 E* c% x' T/ Y
4 ]( H' O; u/ @+ d; g  [水煮鱼 30 1 1

3 V$ _) z4 h: X8 g口水鸡 18 1 1
* X' [3 A/ i. j! n$ `1 C; J% y; P
) g" y4 y1 f/ I1 q清炖豆腐 12 0 0

8 P) G: B% A1 ^# H9 [. m8 Y% m1 1 1 1
- h8 B9 n7 {, W: z5 k7 X

) B+ [, [+ N) _+ C
输出样例

$ {& k" v, |. y& Q4 o3 [/ T口水鸡
7 }- Q7 y7 e. M! F
8 p  M# S$ m' N$ @3 v清炖豆腐
+ U8 H3 w+ H0 P4 N
12.00
! R& H& W0 ?9 n& K' E+ l

% i2 E" ?& H) M4 X1 p9 r/ ?$ r
8 e- v8 }$ L$ ^; A$ `# [/ U- d" c  _时间要求： 1S 之内
! f6 w( t! ]: o; D" w5 V# p7 N
example：
; l. V. C# U+ e2 q6 ?3 [#include <cstdlib>
#include <iostream>

using namespace std;
2 R' S. n, _  e: x1 }  e

struct cai
{
       string cainame;
       int price;
       int hun;
; B' O  W- Q1 x  Y" D3 }) X0 e       int la;
( N/ a& z' R, _" P       };
0 I! `7 R; f8 F7 f# Gint* alltotal=new int[30];
2 L* D$ w! G9 i6 `* M1 Qint pos=0;
6 E; [5 _8 F0 a: p8 l# Bcai* pcai;
) x8 f# Q/ ~  e5 g/ Jint N=3;  
4 a; M" W1 p/ O4 Gvoid fun(int * select,int n,int M,int a,int b,int c,int d,int total);
& k3 H0 t, W( Y& Nint main(int argc, char *argv[])
; G& ]; f* \* q- N{
    int M=2,K=2;
: k$ k6 j: \5 F, r, B" V1 Y6 V    int a=1,b=1,c=1,d=1;
( b. D7 c( r6 _( F7 @" Z    pcai = new cai[N];
    pcai[0].cainame="water fish";
) o# _7 F0 U! N    pcai[0].hun=1;
) c7 n- R1 ~1 j7 E$ D    pcai[0].la=1;
$ Y5 Z8 ?2 }9 k% f" s7 z% ]    pcai[0].price=30;
    pcai[1].cainame="mouth fish";
    pcai[1].hun=1;
    pcai[1].la=1;
0 {" ^/ a2 Z! d% b1 C    pcai[1].price=18;
    pcai[2].cainame="doufu";
" ?1 k* i3 h: J* Z1 p3 _: A    pcai[2].hun=0;
5 _2 q4 f' b. v' k- n. }    pcai[2].la=0;
8 @; O( H( B$ [9 a% i/ d    pcai[2].price=12;
    for(int i=0;i<N;i++)
    {
5 {: c( G: P1 \' a* \4 s        if( (pcai.hun==1 && a>0) ||(pcai.hun==0 && b>0) || (pcai.la==1 && c>0) || (pcai.la==0 && d>0))
) N* p' z6 g4 I9 K8 ]! J        {
/ T6 S* {! y$ c9 t9 r        int ta=a,tb=b,tc=c,td=d;   
! B: p8 W4 s1 n) F5 z/ m. L        int* select=new int[1];   
6 G) _) ]  k" j0 A- }+ \1 B7 G        select[0]=i;
, Y6 Q9 H9 w7 v2 Q7 W0 S- F        if(pcai.hun==1)ta--;else tb--;
        if(pcai.la==1)tc--;else td--;
0 q2 F& M% _7 a. a' v: y3 z        fun(select,1,M-1,ta,tb,tc,td,pcai.price);
        delete[] select;
  k: z4 `2 }+ u! N) f+ z( @        }
    }
  u$ r  x) x  o    for(int i=0;i<pos;i++)
    cout<<alltotal<<endl;
! z4 ~! D* s: V# b/ y" H  Z3 |    delete alltotal;
4 p4 o' @6 Z' c- E" {5 A    delete []pcai;
1 c. Q9 Y8 y0 y, G) o9 o1 \3 v    system("PAUSE");
    return EXIT_SUCCESS;
}
, i/ k& W: Q; N  ?1 k7 B) l0 _void fun(int * select,int n,int M,int a,int b,int c,int d,int total)
{
    //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;
, r( A' w/ z- x9 f2 z3 z    //getchar();
    //cout<<n<<"|"<<M<<"|"<<a<<"|"<<b<<"|"<<c<<"|"<<d<<"|"<<total<<"|"<<endl;
& Y5 z  E* J  G; g- g8 \: h    if(M<=0 && (a>0||b>0||c>0||d>0)){cout<<"impossible"<<endl;return;}
  G4 k7 p$ q: `' K, e    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. I( ?& g1 ]! J* J+ I         for(int j=0;j<n;j++)if(select[j]==i)continue;
& H7 }& p$ @8 v2 q5 ?% D) m        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))
0 w+ {! Z; U* {$ f1 T        {
+ L) Q) Z+ f' Q$ [$ E$ a        int ta=a,tb=b,tc=c,td=d;
9 \2 `1 ~0 C, t" S# X        int* myselect=new int[n+1];   
        for(int k=0;k<n;k++)myselect[k]=select[k];
5 j: R% {" Z1 d% ~/ j, d$ w        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);
" B" |. v. D6 ~4 @! w        delete[] myselect;
+ e) {0 E$ p8 l, j* ]        }
% r( u$ j+ S6 v  [    }
' l$ D- ^6 `8 l) ^4 d7 `}

---

作者: 928171481    时间: 2010-10-9 17:09
嗯，不错不错

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5