查看: 12144|回复: 1

2006 年百度之星程序设计大赛初赛题目 1

[复制链接]

字体大小: 正常放大

厚积薄发

1341 主题	738 听众	2万积分

数学中国总编辑

TA的每日心情

	衰 2016-11-18 10:46

签到天数: 206 天

[LV.7]常住居民III

超级版主

群组: 2011年第一期数学建模

群组: 第一期sas基础实训课堂

群组: 第二届数模基础实训

群组: 2012第二期MCM/ICM优秀

群组: MCM优秀论文解析专题

电梯直达

1^#

发表于 2010-5-6 18:56 |只看该作者 |倒序浏览

|招呼Ta 关注Ta |邮箱已经成功绑定

饭团的烦恼

“午餐饭团“是百度内部参与人数最多的民间组织。

同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。

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

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

饭团点菜的需求如下：

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

2 ．菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。

3 ．请紧记，百度饭团在各大餐馆享受 8 折优惠。

输入数据描述如下：

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

紧接着 N 行，每行的格式如下：

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

例：

水煮鱼 30 1 1

紧接着是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。

输出数据：

对于每一测试数据，输出数据包含 M+1 行，前 M 行每行包含一个菜名（按菜名在原菜单的顺序排序）。第 M+1 行是人均消费，结果保留两位小数。

说明：

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

2 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。

输入样例

1 g& v7 f/ j# `. f6 M3 2 2 4 p- s' x7 w3 |4 I4 U1 B0 B9 X1 w
- x& B  j% ?' E7 m1 l$ ]
水煮鱼 30 1 1
6 U6 [- r3 f7 I3 K
# K' l! }4 i& f7 B& s  B+ g" F+ q口水鸡 18 1 1
+ M$ T- M: ?# s- G! }, B  [! N
清炖豆腐 12 0 0
3 B# F. }: B; Q8 O0 J5 G9 m& Q& q
1 1 1 1 # B0 s6 F9 b; Z- T6 v

输出样例

G! V7 ]# P8 }# E. P- d口水鸡
' C# w' O6 K# P2 X1 q P( E8 }3 ?) l( s4 n
清炖豆腐 4 |1 t# t) b( O0 U; z
2 ]4 k/ [5 s# H5 P% q, u
12.00
. P; u3 J1 t0 r# u) f/ ^' Z

时间要求： 1S 之内

example：
#include <cstdlib>
#include <iostream>

using namespace std;

struct cai
{
   string cainame;
   int price;
   int hun;
   int la;
   };
int* alltotal=new int[30];
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);
int main(int argc, char *argv[])
{
int M=2,K=2;
int a=1,b=1,c=1,d=1;
pcai = new cai[N];
pcai[0].cainame="water fish";
pcai[0].hun=1;
pcai[0].la=1;
pcai[0].price=30;
pcai[1].cainame="mouth fish";
pcai[1].hun=1;
pcai[1].la=1;
pcai[1].price=18;
pcai[2].cainame="doufu";
pcai[2].hun=0;
pcai[2].la=0;
pcai[2].price=12;
for(int i=0;i<N;i++)
{
      if( (pcai.hun==1 && a>0) ||(pcai.hun==0 && b>0) || (pcai.la==1 && c>0) || (pcai.la==0 && d>0))
  L0 I6 l1 t9 W. Q, Q6 r       {1 ]8 v: e& ~! k  b' J
      int ta=a,tb=b,tc=c,td=d;
; f+ T% q9 G8 o! g5 d+ e2 r       int* select=new int[1]; ( B; ^: h% l1 b
      select[0]=i;
' J( E* R/ `; ^0 K+ ]       if(pcai.hun==1)ta--;else tb--;
) R5 |( M$ S" n  n       if(pcai.la==1)tc--;else td--;2 c+ d1 U7 ?0 ?8 F0 H2 J0 }/ k
      fun(select,1,M-1,ta,tb,tc,td,pcai.price);! ?  B6 L- }5 ~7 k  ^  g4 y
      delete[] select;
+ e! b; _: B; z/ d1 U' N- o       }( [1 i# z3 i  I. P5 l; P* K0 o* o  j
}& {# H7 l8 V& s/ k3 B
for(int i=0;i<pos;i++)$ I1 U' J( q" m. l
cout<<alltotal<<endl;
5 G, R! O  t; Y6 t, L* Y delete alltotal;
9 p8 l/ C$ S) K delete []pcai;
; Z7 X7 v& A0 m6 ` system("PAUSE");
. {+ n/ n! b# [! @ return EXIT_SUCCESS;
% I6 A" u  h/ a1 T! t( q: Y}
  O2 A; v2 V3 o0 S: s/ P& c- M: Gvoid fun(int * select,int n,int M,int a,int b,int c,int d,int total)! ?( J; C( S$ G) Q$ f6 o% K
{
2 t' }; N0 i) b8 Q* T //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;' a1 G) K, X4 [8 q8 c! K
//getchar();
/ P) @6 _/ s, ]' ]4 w //cout<<n<<"|"<<M<<"|"<<a<<"|"<<b<<"|"<<c<<"|"<<d<<"|"<<total<<"|"<<endl;, y3 k. S* p* }3 Y; Q5 M
if(M<=0 && (a>0||b>0||c>0||d>0)){cout<<"impossible"<<endl;return;}) D& I, U2 H# _. c$ q  b
if(M<=0 && (a<=0&&b<=0&&c<=0&&d<=0)){cout<<total<<endl;alltotal[pos++]=total;return;}4 g0 Q+ O" @$ I
for(int i=select[n-1];i<N;i++)" |! n8 W' V8 P: o! G3 v6 o3 I
{
& i$ u9 H0 T) S9 p  ]       for(int j=0;j<n;j++)if(select[j]==i)continue;
' `0 @) e. ?8 t       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))
* B7 k% r5 o/ j       {
# j9 @; W5 e7 y  m' z3 w7 v       int ta=a,tb=b,tc=c,td=d;  i1 w) m$ I# W
      int* myselect=new int[n+1]; ( U( I9 r. T9 K% _
      for(int k=0;k<n;k++)myselect[k]=select[k];8 H0 Z8 R, B% {0 e0 V
      myselect[n]=i;
; e6 d! b+ x6 m! U6 C2 l7 i! Q  v       if(pcai.hun==1)ta--;else tb--;
' m( \" C- j6 b; q; W       if(pcai.la==1)tc--;else td--;
% v+ f' g) p* R9 j9 R; _4 T" i7 ~       fun(myselect,n+1,M-1,ta,tb,tc,td,total+pcai.price);7 o, l) b  U7 m) M; [' _: H
      delete[] myselect;# I) t6 V( a+ X2 h( _" c- D2 Z* ~
      }* \+ N" E" o# F) y' _  Q
}4 A  _) _7 ]2 @/ c1 T6 F, ^! ]
}