查看: 11749|回复: 3

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 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。

输入样例

t7 D7 J/ j" P! {# J3 2 2
1 U; Y5 i# u" N" N3 p: W' t& m1 i. U2 B
水煮鱼 30 1 1
+ i+ E8 m. e3 p" Z6 L0 Q8 h
$ g( y* D4 A& z% x& V4 Q! c, B口水鸡 18 1 1
. S8 [8 H1 b/ V( H5 y
. t C$ _7 r1 R8 X' j% _: ~清炖豆腐 12 0 0
) r! q. a; v6 n
9 q1 }2 F5 z* X6 x* o: L% W1 1 1 1
- W2 Z6 y5 M& N8 R/ C

输出样例

' _3 p& D0 P5 r9 f& @口水鸡 ' D: U7 y# A) f/ l9 ?" b
: `3 }( L0 W4 P3 I
清炖豆腐
7 h! J/ W z1 O3 c4 p' r+ J0 M G6 O9 @
12.00 3 Q$ j# W3 P @! Q7 P' |2 r

时间要求： 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))3 T+ f1 D' v& [1 V, ]
      {/ k" E4 V0 c3 Y9 l7 F
      int ta=a,tb=b,tc=c,td=d;
: K2 Q5 |% U; U# k# w% i8 V8 [       int* select=new int[1]; 6 S& E* v% N$ \7 \0 {! S+ Z
      select[0]=i;
  x2 R+ o4 q( i4 O" O       if(pcai.hun==1)ta--;else tb--;
% l2 O, n. i0 e' P" y       if(pcai.la==1)tc--;else td--;+ N9 h6 o5 O2 M  o. [: }) A
      fun(select,1,M-1,ta,tb,tc,td,pcai.price);
" q& ~, L6 Y; q  w: W+ ^       delete[] select;! C1 B1 `5 x3 Z% o
      }
  J8 o2 c! Z4 z* [& l: h }
' v4 l: }5 c4 y  | for(int i=0;i<pos;i++)
2 b4 G  r, Z& O1 _# X& Z' X cout<<alltotal<<endl;/ g" F3 u4 ?& Z
delete alltotal;- \/ ]/ J9 A+ H5 N
delete []pcai;- Q4 E: {9 H" `/ C9 t
system("PAUSE");% |5 H: Z: `' `! B2 _
return EXIT_SUCCESS;
8 s( O: }$ p  z4 {4 m9 @}: r1 l, U- {' I: X  w% I
void fun(int * select,int n,int M,int a,int b,int c,int d,int total)( _- P- I1 ~$ J) q0 q4 b6 N) l) T0 O
{
/ t1 d0 H+ ~% ]) Q //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;
# {0 r4 _0 z. m3 H3 d& o: G //getchar();
1 t1 X7 R- }% w, b2 G& r //cout<<n<<"|"<<M<<"|"<<a<<"|"<<b<<"|"<<c<<"|"<<d<<"|"<<total<<"|"<<endl;
( ^/ g# m' y. y if(M<=0 && (a>0||b>0||c>0||d>0)){cout<<"impossible"<<endl;return;}3 \) A( ?9 M, A, ^
if(M<=0 && (a<=0&&b<=0&&c<=0&&d<=0)){cout<<total<<endl;alltotal[pos++]=total;return;}# c/ B, u9 w6 y4 O6 m
for(int i=select[n-1];i<N;i++)' I5 r6 n5 ^2 k: h3 k. f
{- h. c$ v- n: A. `
      for(int j=0;j<n;j++)if(select[j]==i)continue;  Q, `. z7 }. s; h* k1 [( C6 J
      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))9 x$ k3 f( a5 }6 p
      {
3 a: g5 Y8 q1 K; w       int ta=a,tb=b,tc=c,td=d;
# F! a* @- Q. m9 ?       int* myselect=new int[n+1];
& ]3 k0 B1 y' N# [, ]- y3 v       for(int k=0;k<n;k++)myselect[k]=select[k];: f; q7 y) m* O
      myselect[n]=i;; S7 D) q9 r  m) `% d
      if(pcai.hun==1)ta--;else tb--;; F; Q: G$ N* p& `  E! z4 A* Y$ z
      if(pcai.la==1)tc--;else td--;3 m+ _" e: z. H3 i  c8 f
      fun(myselect,n+1,M-1,ta,tb,tc,td,total+pcai.price);$ K0 x9 p, ~( L$ o8 g' g$ G  x9 K
      delete[] myselect;6 X: n) o* E$ i- o9 z. Z6 u% j
      }' D3 I8 ?) ~# V' s8 @
}+ K, ~4 V; w; {3 ~- Z
}