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

输入样例

) x8 U4 s+ ~- F, k1 [
3 2 2
% S- J0 h/ T+ W4 x) g. x9 v K# T: T+ w, A+ X) c8 P. s8 `
水煮鱼 30 1 1
9 c4 B, o, d& Y4 D- x; M: w0 o3 b+ l/ E
口水鸡 18 1 1
2 I5 n4 f% m, M! m1 V: U
$ `2 I8 d. c1 U8 O" l清炖豆腐 12 0 0 & V% D+ G1 K* q- z/ w9 C
$ T" y+ k1 n1 m2 ~* [) }
1 1 1 1
# Y% ^4 s7 f6 H* Q* `# p+ Y' U

输出样例

5 f4 k8 m" z2 R- S1 p
口水鸡 ; P1 C- ~( a z n2 q- H' i
* y" p: F" j4 e% Y1 \
清炖豆腐
2 u: M: s2 P$ `2 s# S. p3 B! G
8 l! u- m* V9 i: X9 x12.00
; C8 h; U# c( z7 a' l6 M& V

时间要求： 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))
# V: R4 z+ P8 p. C       {5 y; N! F" b7 w3 {, {( ]6 h6 [
      int ta=a,tb=b,tc=c,td=d; * C$ i! g/ O* i8 b5 ~) {6 x
      int* select=new int[1]; 0 b# z# S5 H. s! ^" i
      select[0]=i;
( v) [6 A6 K7 W5 w# }, Q) Z       if(pcai.hun==1)ta--;else tb--;3 Z  {: i4 K. |: W2 ^; u
      if(pcai.la==1)tc--;else td--;
, I$ `* O3 y4 P2 ^1 c- d       fun(select,1,M-1,ta,tb,tc,td,pcai.price);- y" t3 i2 ~6 T0 F8 l: ?+ E# i
      delete[] select;
. ^5 [5 S  [, \2 U& o4 c4 I       }& x, J, d4 z1 [6 c$ c) ~5 f: o
}5 j) y( J+ p- [. f  B$ J& Q" V
for(int i=0;i<pos;i++)
0 U% k. I7 I2 p, B  r: n. }/ O cout<<alltotal<<endl;
& a8 {$ i7 N4 C+ x! d delete alltotal;
/ T( h! f. ]) ]- W/ j( M- O2 [ delete []pcai;8 n2 `8 C6 z8 D+ y5 H1 ?
system("PAUSE");
! o9 e1 `# X- ^# L6 C% ^8 E  v return EXIT_SUCCESS;7 ^' p6 w0 N( V9 E
}# Z2 v0 p6 B3 g8 ?. E
void fun(int * select,int n,int M,int a,int b,int c,int d,int total)
) r; w' w" y# M1 J' T) K  J; _{
6 S) w* m( U- O! ]9 u4 ? //if(a<=0&&b<=0&&c<=0&&d<=0)return 0;
1 ]& r& Y1 y& F+ ?) _ //getchar();% M0 s+ G- k8 a4 m+ ]  A) L* p
//cout<<n<<"|"<<M<<"|"<<a<<"|"<<b<<"|"<<c<<"|"<<d<<"|"<<total<<"|"<<endl;. [5 G( j$ v$ x! O
if(M<=0 && (a>0||b>0||c>0||d>0)){cout<<"impossible"<<endl;return;}) `* Y) ]; u( \" O+ o
if(M<=0 && (a<=0&&b<=0&&c<=0&&d<=0)){cout<<total<<endl;alltotal[pos++]=total;return;}! Q4 l. o: j2 _
for(int i=select[n-1];i<N;i++)( m1 L  `9 b: {
{; |) A" [/ G4 I
      for(int j=0;j<n;j++)if(select[j]==i)continue;6 y5 D2 F* g1 e% W
      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))) w) ~$ M& O0 G% Q( T
      {
# G- Y2 R) ^- P+ O       int ta=a,tb=b,tc=c,td=d;
- w. y2 U! `. i2 I3 t, \       int* myselect=new int[n+1];
6 }9 ~- r: w6 m) O' ]1 d% K8 t; e* {       for(int k=0;k<n;k++)myselect[k]=select[k];
, [" \2 W* _" R+ x! e) H4 I       myselect[n]=i;+ D+ d6 Z: r6 t; L  ^& \
      if(pcai.hun==1)ta--;else tb--;
7 C9 d& H, x; j8 y; {       if(pcai.la==1)tc--;else td--;$ H) n+ ?9 _1 F4 h, p  [3 c: q
      fun(myselect,n+1,M-1,ta,tb,tc,td,total+pcai.price);' k7 a, B8 K* m) p) ?" y  C$ M; x& o
      delete[] myselect;
$ }. i3 Z' @! l- G       }
/ ]0 d" i% A4 _) t' h }
* Q) ^" x, w/ h+ e  Y+ `8 G}