2006 年百度之星程序设计大赛初赛题目 1
饭团的烦恼“午餐饭团“是百度内部参与人数最多的民间组织。
同一个部门的，同一间大学的，同一年出生的，用同一种型号电脑的，员工们总是以各种理由，各种借口组织各种长久的，临时的饭团。
参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们唠唠嗑，吹吹水，增进感情。
但是，随着百度的员工越来越多，各个饭团的管理随即变得烦杂。特别是为了照顾员工们越来越挑剔的胃口，饭团的点菜负责人背负的责任越来越大。现在，这个重担落在百度之星的肩上，因为，你们将要为所有的百度饭团设计一个自动点菜的算法。
饭团点菜的需求如下：
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 ．每组测试数据的结果用一个空行隔开。末尾不要有多余的空行。
输入样例
3 2 2
水煮鱼 30 1 1
口水鸡 18 1 1
清炖豆腐 12 0 0
1 1 1 1
输出样例
口水鸡
清炖豆腐
12.00
时间要求： 1S 之内
example：
#include <cstdlib>
#include <iostream>
using namespace std;
struct cai
{
string cainame;
int price;
int hun;
int la;
};
int* alltotal=new int;
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;
pcai.cainame="water fish";
pcai.hun=1;
pcai.la=1;
pcai.price=30;
pcai.cainame="mouth fish";
pcai.hun=1;
pcai.la=1;
pcai.price=18;
pcai.cainame="doufu";
pcai.hun=0;
pcai.la=0;
pcai.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))
{
int ta=a,tb=b,tc=c,td=d;
int* select=new int;
select=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;
}
}
for(int i=0;i<pos;i++)
cout<<alltotal<<endl;
delete alltotal;
delete []pcai;
system("PAUSE");
return EXIT_SUCCESS;
}
void fun(int * select,int n,int M,int a,int b,int c,int d,int total)
{
//if(a<=0&&b<=0&&c<=0&&d<=0)return 0;
//getchar();
//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=total;return;}
for(int i=select;i<N;i++)
{
for(int j=0;j<n;j++)if(select==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))
{
int ta=a,tb=b,tc=c,td=d;
int* myselect=new int;
for(int k=0;k<n;k++)myselect=select;
myselect=i;
if(pcai.hun==1)ta--;else tb--;
if(pcai.la==1)tc--;else td--;
fun(myselect,n+1,M-1,ta,tb,tc,td,total+pcai.price);
delete[] myselect;
}
}
} 嗯，不错不错
页:
[1]