[编程题]卡中心美食家
- 热度指数：256 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
在卡中心隐藏了很多美食，作为一名资深吃货，楼主告诉你需要去品尝n道美味才能达成“卡中心小小美食家”的成就。这些菜品被标号为 0 到 n-1 。正所谓美食家不是一口吃成个胖子的，每道美味的品尝顺序也是有讲究的，比如西餐的上菜顺序：头盘，汤，副菜，主菜，蔬菜类菜肴，甜品，咖啡或茶。有一些美味需要“前置菜肴”，比如如果你要吃菜品0，你需要先吃菜品1，我们用一个范式来表示这些规则：[0 1]。接下来给你菜品的总数量n和m个“前置菜肴”的范式，请编程输出你为了品尝完所有美味所安排的进餐顺序。可能会有多个正确的顺序，你只要输出一种就可以了。如果不可能品尝完所有美味，返回None。
输入描述:
输入的第一行为以空格分隔的两个正整数，第一个表示原始美味总数n，第二个表示前置菜肴范式总数m。 其后m行每行均为一个以空格分隔的范式说明，第一列为待吃菜肴的标号，第二列为前置菜肴的标号。
输出描述:
对每组测试数据，单独输出一行答案，菜肴标号之间用英文逗号分隔。
示例1
输入
4 4 1 0 2 0 3 1 3 2
输出
只需输出以下任一种结果即可 0,1,2,3 或 0,2,1,3
这道题是典型的拓扑排序问题。
思路：利用有向图来完成，每次有一个前后关系，则在节点上新建一条有向边（前置节点指向后置节点）。图建立完成，遍历一遍邻接表，查找入度为0的节点，表示无需前置菜品，放入栈中。栈初始化完毕之后。更新操作为：从栈中弹出栈顶元素，更新栈顶元素节点指向的那些节点的入度信息（也就是入度减1）。最后看是否所有的节点都入过栈。如果不是，则存在环，无法完成拓扑排序；否则输出信息。
#include <iostream>
#include <stack>#include <vector>
using namespace std;
//邻接表的弧结构
struct ArcNode {int index;
ArcNode *next;
ArcNode() :index(0), next(nullptr) {}
ArcNode(int i) :index(i), next(nullptr) {}
};
//邻接表的节点结构
struct VNode {
int index;
ArcNode *firArc;
int in_degree;
VNode() :index(0), firArc(nullptr), in_degree(0) {}
VNode(int i) :index(i), firArc(nullptr), in_degree(0) {}
};
//释放弧堆内存
void releaseArc(VNode &node)
{
ArcNode *pt = node.firArc;
while (pt!= nullptr && pt->next != nullptr)
{
ArcNode *qt = pt->next;
delete pt;
pt = qt;
}
delete pt;
node.firArc = nullptr;
}
//释放节点堆内存
void releaseNode(VNode *food, int n){
for (int i = 0; i < n; i++)
{
releaseArc(food[i]);
}
delete[]food;
}
int main()
{
int n, m;
cin >> n >> m;
VNode *food = new VNode[n];
for (int i = 0; i < n; i++)
{
food[i].index = i;
}
//创建邻接表
int index1, index2;
while (m--)
{
cin >> index1 >> index2;
if(food[index2].firArc == nullptr)
food[index2].firArc = new ArcNode(index1);
else
{
ArcNode *pre = food[index2].firArc;
while (pre->next != nullptr)
{
pre = pre->next;
}
pre ->next = new ArcNode(index1);
}
food[index1].in_degree++;
}
//查找入度为0的节点
stack<VNode> myStack;
for (int i = 0; i < n; i++)
{
if (food[i].in_degree == 0)
myStack.push(food[i]);
}
vector<int> res;
while (!myStack.empty()){
VNode topNode = myStack.top();
myStack.pop();
res.push_back(topNode.index);
ArcNode *linkNode = topNode.firArc;
while (linkNode != nullptr)
{
food[linkNode->index].in_degree--;
if (food[linkNode->index].in_degree == 0)
{
myStack.push(food[linkNode->index]);
}
linkNode = linkNode->next;
}
}
if (res.size() != n)
{
cout << "None" << endl;
}
else
{
for (int i = 0; i < n; i++)
{
if (i < n - 1)
cout << res[i] << ",";
else
cout << res[i] << endl;
}
}
releaseNode(food, n);
food = nullptr;
return 0;
}
发表于 2018-05-02 14:49:47
回复(0)
package zhaohang;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class ProblemMeishi {
//i:dish的下标、list 结果集
public static boolean process(int n, List<Integer> dish, List<Integer> beforeDish,
int[] beforeDishNum, int i, List<Integer> list, List<Integer> processList) {
if (processList.contains(beforeDish.get(i)))
// 如果成环了，就直接返回false
return false;
if (list.contains(beforeDish.get(i))) {
// 如果当前菜肴未吃，但前置菜肴已吃
if (beforeDishNum[dish.get(i)] == 1){
// 表示前置菜肴只需要1个
list.add(dish.get(i));
}
else
// 表示前置菜肴需要多个
beforeDishNum[dish.get(i)]--;
return true;
} else {
processList.add(dish.get(i));
if (process(n, dish, beforeDish, beforeDishNum, dish.indexOf(beforeDish.get(i)), list, processList)){
// 不成环，表示能吃完，做进一步处理
processList.remove(dish.get(i));
// 前置菜肴吃完，继续来吃这道菜
process(n, dish, beforeDish, beforeDishNum, i, list, processList);
}
}
return false;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 原始美味总数n
int n = sc.nextInt();
// 前置菜肴范式总数m
int m = sc.nextInt();
// 第一列待吃菜肴编号，下标无用
List<Integer> dish = new ArrayList<>();
// 第二列前置菜肴编号，下标无用
List<Integer> beforeDish = new ArrayList<>();
// 每种菜需要的前置菜个数，下标对应着菜肴标号
int[] beforeDishNum = new int[n];
for (int i = 0; i < m; i++) {
dish.add(sc.nextInt());
beforeDish.add(sc.nextInt());
beforeDishNum[dish.get(i)]++;
}
for (int i = 0; i < m; i++) {
// 如果前置菜肴是自己 则不可能吃完
if (dish.get(i) == beforeDish.get(i)) {
System.out.println("None");
return;
}
}
List<Integer> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (beforeDishNum[i] == 0) {
// 如果不需要前置菜肴，直接吃，记录到list里
list.add(i);
}
}
// 防止成环
List<Integer> processList = new ArrayList<>();
// m个菜肴都是需要前置菜肴的
for (int i = 0; i < m; i++) {
if (list.contains(dish.get(i)))
// 如果菜肴已在递归中吃过，则跳过该菜肴
continue;
process(n, dish, beforeDish, beforeDishNum, i, list, processList);
}
// 打印
if (list.size() == n) {
for (int i = 0; i < list.size() - 1; i++) {
System.out.print(list.get(i) + ",");
}
System.out.print(list.get(list.size() - 1));
} else
System.out.println("None");
}
}
发表于 2018-04-07 12:20:38
回复(2)
#include <bits/stdc++.h>
using namespace std;
vector<int> path;//存储吃东西顺序的路径
int n, m;
bool found;//是否已找到解
vector<unordered_set<int> > limit;//limit[i]:存吃第i个东西前必须先吃的
bool find(int index, int dest) {//此函数用于搜寻某号食物是否已经吃了
bool ans = false;
for (int i = 0; i < index; ++i) {
if (path[i] == dest) {
ans = true;
break;
}
}
return ans;
}
void dfs(int index) {//深度优先搜索
if (!found) {
if (index >= n) {//如果已经到了最后，打印结果并将found置true
for (int i = 0; i < n; ++i)
printf("%d%c", path[i], i==n-1 ? '\n' : ',');
found = true;
} else {//否则要作进一步搜索
for (int i = 0; i < n; ++i) {
if (find(index, i))//如果编号为i的东西已经吃了，则跳过
continue;
bool visitable = true;
//visitable用来确定吃i号东西前要先吃的东西有没有吃
for (auto it = limit[i].begin(); it != limit[i].end(); ++it) {
if (!find(index, *it)) {
visitable = false;
break;
}
}
if (visitable) {
path[index] = i;
dfs(index + 1);
}
}
}
}
}
int main() {
while (scanf("%d %d", &n, &m) != EOF) {
found = false;
path.clear();
path.resize(n, -1);
limit.clear();
limit.resize(n);
int x, y;
for (int i = 0; i < m; ++i) {
scanf("%d %d", &x, &y);
limit[x].insert(y);
}
dfs(0);
if (!found)
printf("None\n");
}
return 0;
}
发表于 2018-07-10 22:04:24
回复(0)
#include <stdio.h>
#include <iostream>
int isEated(int *Eated,int Eatedcount,int cookname)//已经被品尝过了吗？
{
int i;
for(i=0;i<Eatedcount;i++)
{
if(Eated[i]==cookname)
return 1;
}
return 0;
}
int CanEat(int (*menu)[2],int *Eated,int m,int cookname,int Eatedcount)//可以吃吗？
{
int flag = 1;
//如果已经被吃掉了，那就不能被吃
if(isEated(Eated,Eatedcount,cookname))//1表示已经被吃掉了
flag = 0;
//如果该菜品在范式左侧，并且其右侧的菜品未被吃,那就不可以吃
for(i=0;i<m;i++)
{
if(menu[i][0]==cookname)
{
if(isEated(Eated,Eatedcount,menu[i][1])!=1)
flag = 0;
}
}
return flag;
}
void RepeatEat(int (*menu)[2],int *Eated,int Eatedcount,int n,int m)
{
int i,j;
int Eatedtemp[n];
//复制一份已经吃掉的菜单记录
for(i=0;i<n;i++)
{
Eatedtemp[i]=Eated[i];
}
//只打印一个
if(flagover ==1)
return;
//结束条件
if(Eatedcount==n)
{
for(i=0;i<n-1;i++)
{
printf("%d,",Eated[i]);
}
printf("%d",Eated[n-1]);
flagover = 1;
}
else
{
int temp;
//尚未结束时
//取菜品
for(i=0;i<m;i++)
{
for(j=0;j<2;j++)
{
temp = menu[i][j];
//如果可以被吃掉
if(CanEat(menu,Eated,m,temp,Eatedcount))
{
//进入“已经被吃掉菜品”数组，记录
Eated[Eatedcount] = temp;
Eatedcount++;
//递归
RepeatEat(menu,Eated,Eatedcount,n,m);
Eatedcount--;
}
}
}
}
}
int main(){
int n,m,i,j;
int Eatedcount = 0;
cin>>n;//菜品数目 = n
cin>>m;//范式数目 = m；
//顺序范式
int menu[m][2];
//被吃了之后的菜品数量
int Eated[n];
//范式初始化
for(i=0;i<m;i++)
{
scanf("%d %d",&menu[i][0],&menu[i][1]);
}
RepeatEat(menu,Eated,0,n,m);
if(flagover == 0)
printf("None");
return 0;
}
#include <iostream>
using namespace std;int flagover = 0;
int isEated(int *Eated,int Eatedcount,int cookname)//已经被品尝过了吗？
{
int i;
for(i=0;i<Eatedcount;i++)
{
if(Eated[i]==cookname)
return 1;
}
return 0;
}
int CanEat(int (*menu)[2],int *Eated,int m,int cookname,int Eatedcount)//可以吃吗？
{
int flag = 1;
int i,j;
//1表示可以被吃掉//0表示不可以被吃掉
//如果已经被吃掉了，那就不能被吃
if(isEated(Eated,Eatedcount,cookname))//1表示已经被吃掉了
flag = 0;
//如果该菜品在范式左侧，并且其右侧的菜品未被吃,那就不可以吃
for(i=0;i<m;i++)
{
if(menu[i][0]==cookname)
{
if(isEated(Eated,Eatedcount,menu[i][1])!=1)
flag = 0;
}
}
return flag;
}
void RepeatEat(int (*menu)[2],int *Eated,int Eatedcount,int n,int m)
{
int i,j;
int Eatedtemp[n];
//复制一份已经吃掉的菜单记录
for(i=0;i<n;i++)
{
Eatedtemp[i]=Eated[i];
}
//只打印一个
if(flagover ==1)
return;
//结束条件
if(Eatedcount==n)
{
for(i=0;i<n-1;i++)
{
printf("%d,",Eated[i]);
}
printf("%d",Eated[n-1]);
flagover = 1;
}
else
{
int temp;
//尚未结束时
//取菜品
for(i=0;i<m;i++)
{
for(j=0;j<2;j++)
{
temp = menu[i][j];
//如果可以被吃掉
if(CanEat(menu,Eated,m,temp,Eatedcount))
{
//进入“已经被吃掉菜品”数组，记录
Eated[Eatedcount] = temp;
Eatedcount++;
//递归
RepeatEat(menu,Eated,Eatedcount,n,m);
Eatedcount--;
}
}
}
}
}
int main(){
int n,m,i,j;
int Eatedcount = 0;
cin>>n;//菜品数目 = n
cin>>m;//范式数目 = m；
//顺序范式
int menu[m][2];
//被吃了之后的菜品数量
int Eated[n];
//范式初始化
for(i=0;i<m;i++)
{
scanf("%d %d",&menu[i][0],&menu[i][1]);
}
RepeatEat(menu,Eated,0,n,m);
if(flagover == 0)
printf("None");
return 0;
}
发表于 2018-05-03 13:27:39
回复(1)
有80%的通过，不知道逻辑上还有什么漏洞，求大家指点！
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
class caipin{
int bianhao;
ArrayList<Integer> pre=new ArrayList();
public caipin(int a){
this.bianhao=a;
}
public void insert(int a){
pre.add(a);
}
}
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int number1=sc.nextInt();
int number2=sc.nextInt();
ArrayList<Integer> re=new ArrayList();
re.add(-1);
//定义caipin的对象数组
caipin [] rr=new caipin[number1];
//因为菜一定是n道菜
//所以先创建好对象数组
for(int i=0;i<number1;i++){
caipin a=new caipin(i);
rr[i]=a;
}
for(int i=0;i<number2;i++){
int origion=sc.nextInt();
int pre=sc.nextInt();
rr[origion].insert(pre);
}
//遍历对象数组，先判断是否能吃下所有美食
for(int i=0;i<number1;i++){
for(int j=0;j<rr[i].pre.size();j++){
//如果一个菜品的前置菜肴还包含它自己，那么就不可能吃到所有美食
if(rr[rr[i].pre.get(j)].pre.contains(i)){
System.out.println("None");
break;
}
else{
//如果可以的话，就给美食排顺序，
//排序的时候同样会出现无法吃到所有美食的情况
//首先判断我正要安置的美食是不是已经出现了
if(re.contains(rr[i].bianhao)){
//说明我当前要安置的美食，已经作为别人的前置美食了
//如果我要放置的美食的前置菜肴已经存在，并且就在我要安置的前面
if(re.contains(rr[i].pre.get(j))&&re.indexOf(rr[i].pre.get(j))<re.indexOf(rr[i].bianhao)){
//不用进行操作
}
else {
if(!re.contains(rr[i].pre.get(j))){
//如果不包含这个前置美食，就把它插入到，已存在的需要安置的美食的前面
re.add(re.indexOf(rr[i].bianhao),rr[i].pre.get(j));
}
else{
//如果包含这个前置美食，并且这个前置美食的位置还在我需要安放的美食的位置后面，
//尝试能不能把在后面的前置美食往前挪动，如果可以，挪到需要安放的美食前面就说明是可以的
int index1=re.indexOf(rr[i].bianhao);
int index2=re.indexOf(rr[i].pre.get(j));
//把后面的往前移动
int aa=0;
for(int a=index2-1;a>index1;a--){
if(rr[rr[i].pre.get(j)].pre.contains(re.get(a))){
//如果往前移动发现移动不了
aa=0;
break;
}
else{
aa=1;
}
}
int bb=0;
for(int b=index1+1;b<index2;b++){
if(rr[re.get(b)].pre.contains(rr[i].bianhao)){
bb=0;
break;
}
else{
bb=1;
}
}
if(aa==1||bb==1){
int tt=re.get(index1);
re.set(index1, re.get(index2));
re.set(index2, tt);
}
else {
System.out.println("None");
break;
}
}
}
}
else{
//如果需要放置的菜不包含
if(re.contains(rr[i].pre.get(j))){
//如果我放的这个美食的前置美食已经存在，不用操作，
}
else {
//如果不存在
re.add(rr[i].pre.get(j));
}
}
}
}
if(re.contains(rr[i].bianhao)){
}
else{
re.add(rr[i].bianhao);
}
}
String r=re.get(1)+"";
for(int i=2;i<re.size();i++){
r=r+","+re.get(i);
}
System.out.println(r);
}
}
发表于 2018-04-02 17:44:46
回复(0)
求测试用例，为什么考虑死锁前有80%case通过，考虑之后反而只有50%的通过
# -*- coding:utf-8 -*-
import sys
number, method = sys.stdin.readline().split()
n, m = int(number), int(method)
d = {}
res = []
'得到范式并合并存入字典'
for i in range(m):
key, value = sys.stdin.readline().split()
if d.has_key(key):
d[key].append(value)
else:
d[key] = [value]
#print n,m,d,len(d)
'按用餐先后顺序存编号'
def oder(x, flag):
'如果出现闭环结果中加入一个标记并停止递归'
if x in flag:
res.append('*')
else:
flag.append(x)
list = d[x]
for i in range(len(list)):
if not d.has_key(list[i]):
if list[i] not in res:
res.append(list[i])
else:
oder(list[i], flag)
if x not in res:
res.append(x)
for x in d:
flag = []
if x not in res:
oder(x, flag)
#print res
'打印出来'
string =''
if n >= 1 and m > n*(n-1):
print None
elif '*' in res or n == 0:
print None
else:
if len(res) < n:
for x in range(n):
if str(x) not in res:
res.append(str(x))
#print res
for number in res:
if string is not '':
string += ','+number
else:
string += number
print string
发表于 2018-03-29 20:36:18
回复(0)
问题信息
通过挑战的用户
-
2020-04-08 00:58:46
-
2018-09-08 09:16:04
-
2018-08-14 11:05:00
-
2018-08-12 21:13:22
-
2018-08-11 11:01:36
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
