数学建模社区-数学中国

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

---

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

/ y1 B4 j% k# F/ v0 b* L“午餐饭团“是百度内部参与人数最多的民间组织。
# l6 b. P) i- |! n9 Q
同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。

* m( f: R) K/ T  d  R7 e参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。
4 W, |# A# j7 }" _' U
- L& Z8 g: ]/ |8 H5 g但是，随着百度的员工越来越多，各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口，饭团的点菜负责人背负的责任越来越大。现在，这个重担落在百度之星的肩上，因为，你们将要为所有的百度饭团设计一个自动点菜的算法。
9 ]8 P3 U: e3 Q
饭团点菜的需求如下：

1 ． 经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近 12 元越好。

7 z( u. Y( f, u2 ． 菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。
. P5 @4 _0 l1 [0 E3 J! o+ J1 n  m
/ x  j( S( Z! ^' C: p3 ． 请紧记，百度饭团在各大餐馆享受 8 折优惠。
5 Z1 B" V# B& s
输入数据描述如下：

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

- U/ @( Z% c9 A9 A紧接着 N 行，每行的格式如下：

菜名（长度不超过 20 个字符） 价格（原价，整数） 是否荤菜（ 1 表示是， 0 表示否） 是否辛辣（ 1 表示是， 0 表示否）

0 a$ c; c8 h& r/ ]! K& a例：

5 g. p/ V; Z# p2 W. d3 Y9 \( D水煮鱼 30 1 1

+ Z( h# l2 u/ {% g& a  d/ q7 [紧接着是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。

输出数据：
0 [, T& t6 v, @; L; R* P3 @
对于每一测试数据，输出数据包含 M+1 行，前 M 行每行包含一个菜名（按菜名在原菜单的顺序排序）。第 M+1 行是人均消费，结果保留两位小数。
! X8 ^+ z' _# O
3 H- p/ l  C" u, d& s! a  |说明：
! I9 X6 Q5 m; O- y) |
1 ．结果菜单的数目应该恰好为 M ，荤菜，素菜，辛辣，清淡菜的数目恰好为 a ， b ， c ， d 。在满足这样的前提下，选择人均消费最接近 12 元的点菜方案。题目数据保证有且仅有一个解。

. z- [5 T: g2 k$ M, T2 j/ ~2 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。
( i8 N7 ^  k8 b- `) ~
输入样例

7 p( j8 g( {- j/ D3 2 2
) r3 _% D& T) ^5 `0 U) L
" X$ B* C# k( |) R水煮鱼 30 1 1
# n; z. g# |2 Y1 n+ g
& I( {1 q2 l2 H6 V7 H& m口水鸡 18 1 1
+ @4 e$ ~/ W: P; M9 d( ]$ ]: @
清炖豆腐 12 0 0
, K: y( \- l/ G& _( Z# o/ W4 k
' ^& f2 L, U6 ^6 ^5 c1 T1 1 1 1
& j2 ], v4 O- l: o4 {1 N+ k

/ q% v, p$ q5 Q
7 ~1 Y6 W6 K, k输出样例

口水鸡
7 c8 G' }( K( {
清炖豆腐

: C" z* w* w7 L+ x) {% q12.00
3 I, G0 }$ o- W; v

4 M5 N8 \+ S( K& k, j
8 t+ |6 ^$ W4 a* x! V
9 e# P: e; @/ L- N. b时间要求： 1S 之内
" n4 Z$ {4 P1 r2 e
. ?# x, G' [- e2 Texample：
% P# P, I4 [7 F#include <cstdlib>
0 E9 @3 ^6 Y) }# }, i+ Z( e- k  q7 {#include <iostream>

using namespace std;
$ d( D! d! \3 c/ M% k$ f
6 z% S9 Z0 t6 R! V( j: K1 j" s, F* C
struct cai
{
       string cainame;
       int price;
5 |- D8 H+ _2 a2 H% D       int hun;
3 t$ ]) t1 \9 V       int la;
       };
int* alltotal=new int[30];
& h1 |2 `( x# ]int pos=0;
cai* pcai;
int N=3;  
void fun(int * select,int n,int M,int a,int b,int c,int d,int total);
2 B6 `& i1 A1 k1 G9 h- B* `8 A3 Qint main(int argc, char *argv[])
) @9 \- H1 T, S  M{
; m) r- k" w; K0 C6 n    int M=2,K=2;
    int a=1,b=1,c=1,d=1;
    pcai = new cai[N];
, x- _3 \- K. `* |- o) ~    pcai[0].cainame="water fish";
    pcai[0].hun=1;
/ Q8 d/ t8 s8 v4 p, i& h    pcai[0].la=1;
1 m4 o& ~, g3 X0 |& {, B    pcai[0].price=30;
( E1 V0 S$ u: \5 g. c3 v" U3 }    pcai[1].cainame="mouth fish";
* w# }. g7 z6 d    pcai[1].hun=1;
8 m. B* a  k% B+ K) v( R    pcai[1].la=1;
    pcai[1].price=18;
    pcai[2].cainame="doufu";
% J3 I  b4 w9 X, w+ x7 \    pcai[2].hun=0;
    pcai[2].la=0;
    pcai[2].price=12;
  B/ ]. ^, a# }    for(int i=0;i<N;i++)
$ a! p7 F7 v7 T# c# T6 O    {
( j( V1 H1 y5 N! y0 U( h. h; B8 b3 [        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--;
& f6 q1 A. }3 d3 c9 ^% w4 ]        if(pcai.la==1)tc--;else td--;
        fun(select,1,M-1,ta,tb,tc,td,pcai.price);
        delete[] select;
        }
    }
$ a5 `9 o. c! \) t; G    for(int i=0;i<pos;i++)
    cout<<alltotal<<endl;
0 j, g# H1 g% X    delete alltotal;
- N* H7 ^! n1 x: D' A* j    delete []pcai;
# J$ b8 }. _% @8 b& }    system("PAUSE");
# l2 N  t( B2 T    return EXIT_SUCCESS;
% k. l0 l1 a; {}
! f0 s  G8 h0 Z% Q) i0 Uvoid fun(int * select,int n,int M,int a,int b,int c,int d,int total)
{
1 q  S4 l( F, ~% e/ V% m1 W    //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;
    //getchar();
6 `& \2 g9 E, H4 P& a  r$ Z    //cout<<n<<"|"<<M<<"|"<<a<<"|"<<b<<"|"<<c<<"|"<<d<<"|"<<total<<"|"<<endl;
    if(M<=0 && (a>0||b>0||c>0||d>0)){cout<<"impossible"<<endl;return;}
0 E1 H. d. h- k3 v    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++)
% r) H& T% H: `! Q/ l+ l    {
         for(int j=0;j<n;j++)if(select[j]==i)continue;
        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))
3 X$ ^# H& {2 `( s6 b5 y        {
, U. h# G0 x9 |. A8 n        int ta=a,tb=b,tc=c,td=d;
        int* myselect=new int[n+1];   
* |' o/ b. l  R1 Q; z& g# B        for(int k=0;k<n;k++)myselect[k]=select[k];
        myselect[n]=i;
. G* R8 b: P9 A& O        if(pcai.hun==1)ta--;else tb--;
! e5 M9 L' X* I( ~9 D: {        if(pcai.la==1)tc--;else td--;
        fun(myselect,n+1,M-1,ta,tb,tc,td,total+pcai.price);
, f+ R) U( W( u+ y$ Y. g# ~- B        delete[] myselect;
; I2 G& C2 p4 P; A        }
    }
}

---

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

---

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

Powered by Discuz! X2.5