数学建模社区-数学中国

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

---

作者: 厚积薄发    时间: 2010-5-6 18:56
标题: 2006 年百度之星程序设计大赛初赛题目 1
饭团的烦恼
! c: X  q# s8 I
5 z- N1 Q+ }9 B# u“午餐饭团“是百度内部参与人数最多的民间组织。
; M: Z5 `# E9 q3 R. c4 c; X
3 o4 ?1 A( n4 [2 |同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。

参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。

( B( i- Q$ e6 Y  B0 p2 e但是，随着百度的员工越来越多，各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口，饭团的点菜负责人背负的责任越来越大。现在，这个重担落在百度之星的肩上，因为，你们将要为所有的百度饭团设计一个自动点菜的算法。

饭团点菜的需求如下：
+ G  G6 c& s8 p, u  ?0 g* o/ z& i
1 ． 经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近 12 元越好。
$ D& W; X5 B' K
8 s  [4 c( L4 C$ w* D/ ^2 ． 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。
& K- I4 `# g/ W
3 ． 请紧记，百度饭团在各大餐馆享受 8 折优惠。

; j+ _: w3 ^6 x( j. [输入数据描述如下：
7 I  P4 p' R; l& o. `' Y" \
+ F+ |( o1 ~; A2 a9 ?第一行包含三个整数 N ， M ， K （ 0<N<=16 ， 0<M<=N ， 0<K<=12 ），分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。
+ |) H: j: ?/ }5 j% \
紧接着 N 行，每行的格式如下：

9 f: |. `2 u9 J7 o! A# v菜名（长度不超过 20 个字符） 价格（原价，整数） 是否荤菜（ 1 表示是， 0 表示否） 是否辛辣（ 1 表示是， 0 表示否）
+ w, Y4 v: E) }, B, Y; c, ^
2 f8 @* `) ~8 Q: m* K' C+ L! h例：

水煮鱼 30 1 1

3 s* A! f3 ]6 k" s# `9 S& B紧接着是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。

输出数据：

对于每一测试数据，输出数据包含 M+1 行，前 M 行每行包含一个菜名（按菜名在原菜单的顺序排序）。第 M+1 行是人均消费，结果保留两位小数。
& @# L! i$ b0 w; W
说明：
( Y  K; M% y1 X7 [
& J) X; S& H8 a! v1 ．结果菜单的数目应该恰好为 M ，荤菜，素菜，辛辣，清淡菜的数目恰好为 a ， b ， c ， d 。在满足这样的前提下，选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。
1 ?* q* T% E; d
2 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。

输入样例

1 n/ j( t+ \4 ~5 S: Z3 2 2
) A) T! X3 p/ S* b$ X+ l
( m. H1 @- t; T; |/ ^: S水煮鱼 30 1 1
/ N+ {. G9 J) C. O$ p& o
; G8 ^( X7 x# j口水鸡 18 1 1
8 p6 e& H- F! Y8 B
清炖豆腐 12 0 0

- _9 k" D5 A2 w  I4 {1 1 1 1

输出样例

$ i, T' o* c7 B5 N- N口水鸡

清炖豆腐
- e9 A! H$ b$ c6 X0 E: a9 s5 _" W
12.00

* ?( P6 g1 z3 t时间要求： 1S 之内
7 @0 `% I& T& X; t8 h0 ]
5 E, {5 G2 C0 f( E% rexample：
/ }# z  H  t; D9 s  ]" c#include <cstdlib>
#include <iostream>

1 s- P. J/ [" C; @- wusing namespace std;

/ N/ ?$ A2 o. u
struct cai
{
7 i& f* Z/ @" l) _6 I* A; _+ T       string cainame;
       int price;
3 i0 y3 D* e- `2 X- h       int hun;
9 n2 J5 h% I4 q* Q+ o& C& v       int la;
0 C- M! }  H' O' v0 A       };
  i4 X) @7 h3 q( x0 `6 T$ M( q* ^int* alltotal=new int[30];
8 V' G" f4 d1 G4 ^3 u+ l/ j1 aint pos=0;
; N; O4 ], j# T3 |2 F5 z0 Lcai* pcai;
int N=3;  
3 A4 s0 V' T# t7 P1 `; Uvoid fun(int * select,int n,int M,int a,int b,int c,int d,int total);
int main(int argc, char *argv[])
. z) m% D! G5 X9 }{
( q8 m) }9 A) h- y  I/ z    int M=2,K=2;
    int a=1,b=1,c=1,d=1;
$ z: b2 b6 x# J% u! W8 @) V    pcai = new cai[N];
2 k9 L6 O: q  \- \& ?# z    pcai[0].cainame="water fish";
    pcai[0].hun=1;
( Q6 S/ F3 T& p    pcai[0].la=1;
    pcai[0].price=30;
( |; |2 n- f1 K8 e+ h2 D    pcai[1].cainame="mouth fish";
( D: E, s3 o6 G& t' ^    pcai[1].hun=1;
3 m  R6 l4 g$ y+ h/ J2 a/ ?/ i* p+ l    pcai[1].la=1;
    pcai[1].price=18;
    pcai[2].cainame="doufu";
    pcai[2].hun=0;
  z3 _$ o" t' z( {2 z" q8 ^5 w    pcai[2].la=0;
/ @, O) F7 g& g5 j    pcai[2].price=12;
2 m) b9 i7 N$ V: ~/ D: f    for(int i=0;i<N;i++)
    {
+ r: z- K- P" R; n% ]: s% q( `        if( (pcai.hun==1 && a>0) ||(pcai.hun==0 && b>0) || (pcai.la==1 && c>0) || (pcai.la==0 && d>0))
        {
        int ta=a,tb=b,tc=c,td=d;   
        int* select=new int[1];   
        select[0]=i;
        if(pcai.hun==1)ta--;else tb--;
        if(pcai.la==1)tc--;else td--;
! p( W: ^0 c# I! J/ E        fun(select,1,M-1,ta,tb,tc,td,pcai.price);
& U& ~" K! W% U        delete[] select;
        }
* u. G( u% o; U7 G    }
# e5 D  k* Z' g    for(int i=0;i<pos;i++)
* \6 E8 C' R7 C# R' l% ~6 g    cout<<alltotal<<endl;
8 ]9 k6 Z: Y! {% [0 H# e2 E    delete alltotal;
! H: s8 r+ B* N& S* h% n/ \    delete []pcai;
    system("PAUSE");
    return EXIT_SUCCESS;
6 y3 }+ m. J% P( a}
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;
% W: T& R' ~* t6 e' A( q( J    //getchar();
    //cout<<n<<"|"<<M<<"|"<<a<<"|"<<b<<"|"<<c<<"|"<<d<<"|"<<total<<"|"<<endl;
    if(M<=0 && (a>0||b>0||c>0||d>0)){cout<<"impossible"<<endl;return;}
    if(M<=0 && (a<=0&&b<=0&&c<=0&&d<=0)){cout<<total<<endl;alltotal[pos++]=total;return;}
; C: l& X* f+ S4 B# n    for(int i=select[n-1];i<N;i++)
    {
  }- B3 d  ?% g5 H         for(int j=0;j<n;j++)if(select[j]==i)continue;
+ m2 Q$ H4 ~+ U# E        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))
        {
        int ta=a,tb=b,tc=c,td=d;
* ^6 n& z0 Z/ v4 _9 d3 x        int* myselect=new int[n+1];   
        for(int k=0;k<n;k++)myselect[k]=select[k];
        myselect[n]=i;
        if(pcai.hun==1)ta--;else tb--;
- X  f- e. V, I( I+ @        if(pcai.la==1)tc--;else td--;
1 T/ ]  x" X2 f' i$ D) A        fun(myselect,n+1,M-1,ta,tb,tc,td,total+pcai.price);
9 b0 V: [3 z& D% x" x7 p        delete[] myselect;
        }
    }
}

---

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

---

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

Powered by Discuz! X2.5