数学建模社区-数学中国

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

---

作者: 厚积薄发    时间: 2010-5-6 18:56
标题: 2006 年百度之星程序设计大赛初赛题目 1
饭团的烦恼
8 Z! ^2 E) g# \  A8 |1 C0 ^, }
“午餐饭团“是百度内部参与人数最多的民间组织。
! U, P( r3 O" ^3 L' ?, X$ u
同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。

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

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

1 e) d* A5 I4 y饭团点菜的需求如下：
+ L: j" _" C& G1 v9 Q2 H: ]7 E5 j
1 ． 经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近 12 元越好。

2 ． 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。
1 _+ O9 J% d4 r& O1 S
3 ． 请紧记，百度饭团在各大餐馆享受 8 折优惠。

, O; `4 a9 `: `# l. [输入数据描述如下：

第一行包含三个整数 N ， M ， K （ 0<N<=16 ， 0<M<=N ， 0<K<=12 ），分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数。
6 @" d+ Y0 d7 u6 @
, Y' a0 T: H- r紧接着 N 行，每行的格式如下：

菜名（长度不超过 20 个字符） 价格（原价，整数） 是否荤菜（ 1 表示是， 0 表示否） 是否辛辣（ 1 表示是， 0 表示否）
$ ?. C( r& j2 j# W
例：

. N5 M. M9 [  f0 b3 h4 ~% W1 _水煮鱼 30 1 1
4 x# Z" P: G: ]
5 X4 l- p' k, L- t' M紧接着是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。

输出数据：

2 j4 R! V5 g6 y: s2 E# N* O5 k2 `对于每一测试数据，输出数据包含 M+1 行，前 M 行每行包含一个菜名（按菜名在原菜单的顺序排序）。第 M+1 行是人均消费，结果保留两位小数。

0 E+ d# }3 L8 E2 @# p说明：

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

$ Z* f* e; g0 y' p2 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。

  h8 ^* j) ~5 X5 u输入样例

# R" |) M5 j/ l7 O' u' n$ L) A) n3 2 2

6 c) {# a  @8 A1 ?4 b$ q! V5 k1 ~水煮鱼 30 1 1

% k2 W( a4 [& F% M1 r口水鸡 18 1 1

清炖豆腐 12 0 0

7 |% m' f1 d: M7 H: k1 1 1 1

2 }6 j+ t8 R/ d' X
7 ^2 g0 _7 i# ]' [- ^  {8 U" J! }输出样例

口水鸡
# l6 a4 f+ A# d4 s4 p9 O3 n3 p
. q$ _* _& f' X$ Y. v清炖豆腐

12.00
' d7 K8 E3 A+ z: A. F' A' i, t, u; V% p

8 B+ f8 r7 r% H* K. [
) v* ^2 p5 ]9 N% E
9 j7 Z! }" S6 ^: ?  u  j+ Q$ `" Y时间要求： 1S 之内

. d' v2 g$ r: j# L) eexample：
3 {8 u4 u- k. K7 D5 W5 ]#include <cstdlib>
: }4 A# X, ?. V' a( `#include <iostream>

5 [) q% J7 k0 ^! J. musing namespace std;

* |' ^  H1 M0 W, \3 ^) H8 r
struct cai
{
       string cainame;
  s9 k0 r7 }$ w  h1 S       int price;
       int hun;
9 T" K- v5 X( F/ q; X* n, a: U6 R, u       int la;
       };
int* alltotal=new int[30];
int pos=0;
cai* pcai;
int N=3;  
* e( i# |' v6 t- w: @% [# |void fun(int * select,int n,int M,int a,int b,int c,int d,int total);
int main(int argc, char *argv[])
/ z, n" r0 c2 d% A{
    int M=2,K=2;
4 m  |% u# a* \2 V! e* P    int a=1,b=1,c=1,d=1;
    pcai = new cai[N];
    pcai[0].cainame="water fish";
- a5 ?  k  x- x    pcai[0].hun=1;
& |7 [1 G& U0 ?! O) s# O; |    pcai[0].la=1;
    pcai[0].price=30;
    pcai[1].cainame="mouth fish";
" \" F6 c: i, d    pcai[1].hun=1;
    pcai[1].la=1;
( l! o& h% d# C4 T& {% x# z+ W$ E. M    pcai[1].price=18;
+ ]+ ?" p; P2 y" Q- n. Q  A" Z    pcai[2].cainame="doufu";
    pcai[2].hun=0;
6 n. G! [* O" _. M1 |& F5 ]$ N9 \    pcai[2].la=0;
    pcai[2].price=12;
    for(int i=0;i<N;i++)
0 P- M% R( t/ t+ i' u' g6 n: }    {
        if( (pcai.hun==1 && a>0) ||(pcai.hun==0 && b>0) || (pcai.la==1 && c>0) || (pcai.la==0 && d>0))
% }' m; G0 o. C- E& n9 ]        {
        int ta=a,tb=b,tc=c,td=d;   
. T8 m( l' e  x: Y3 p        int* select=new int[1];   
        select[0]=i;
        if(pcai.hun==1)ta--;else tb--;
        if(pcai.la==1)tc--;else td--;
        fun(select,1,M-1,ta,tb,tc,td,pcai.price);
        delete[] select;
* c; N6 q) F; M& r* `, D        }
) }- V3 A$ R* k2 G0 e/ e    }
    for(int i=0;i<pos;i++)
4 v& g. G2 F5 c1 y    cout<<alltotal<<endl;
4 P: I8 E. P8 D4 q: G: G- K    delete alltotal;
    delete []pcai;
    system("PAUSE");
" ~4 R; h! U3 _$ B; X    return EXIT_SUCCESS;
- ?/ O6 o% J4 k, [, o}
! X/ h$ a9 k' E/ I4 E; Z; X' Yvoid fun(int * select,int n,int M,int a,int b,int c,int d,int total)
* N% l/ w4 Q1 T( P{
    //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;
    //getchar();
: Y& D, m) f/ i0 p& f0 n' v    //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;}
    for(int i=select[n-1];i<N;i++)
* H, A. K2 Z! r3 `' X1 }3 k    {
         for(int j=0;j<n;j++)if(select[j]==i)continue;
5 X+ x5 o# _8 i" g        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))
        {
- H0 Q! G) M0 \        int ta=a,tb=b,tc=c,td=d;
        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--;
% m1 j7 X$ f% T) |# @        if(pcai.la==1)tc--;else td--;
2 Z- \! C8 D3 n6 n5 ]" l8 C# a        fun(myselect,n+1,M-1,ta,tb,tc,td,total+pcai.price);
        delete[] myselect;
        }
! [1 u* J! W6 G- T- q    }
}

---

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

---

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

Powered by Discuz! X2.5