# 挤奶顺序

2024-02-05 17:12
文章标签 顺序 挤奶

本文主要是介绍# 挤奶顺序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

每天,FarmerJohn都要给他的8头奶牛挤奶。她们的名字分别是Bessie,Buttercup,Belinda,Beatrice,Bella,Blue,Betsy,和Sue。

不幸的是,这些奶牛相当难以伺候,她们要求FarmerJohn以一种符合N条限制的顺序给她们挤奶(1≤N≤7)。每条限制的形式为“X必须紧邻着Y挤奶”,要求奶牛X在挤奶顺序中必须紧接在奶牛Y之后,或者紧接在奶牛Y之前。

请帮助FarmerJohn求出一种满足所有限制的奶牛挤奶顺序。保证这样的顺序是存在的。如果有多种顺序都满足要求,请输出字典序最小的一种。也就是说,第一头奶牛需要是所有可能排在任意合法奶牛顺序的第一位的奶牛中名字字典序最小的。在所有合法的以这头字典序最小的奶牛为首的奶牛顺序中,第二头奶牛需要是字典序最小的,以此类推。

输入格式

输入的第一行包含N。以下N行每行包含一句句子,以"XmustbemilkedbesideY"的格式描述了一条限制,其中X和Y为FarmerJohn的某些奶牛的名字(上文列举了八个可能的名字)。

输出格式

请用8行输出一个奶牛的顺序,每行输出一头奶牛的名字,满足所有的限制。如果由多种顺序符合要求,输出字典序最小的奶牛顺序。

样例输入
3
Buttercup must be milked beside Bella 
Blue must be milked beside Bella
Sue must be milked beside Beatrice
样例输出
Beatrice
Sue
Belinda
Bessie
Betsy
Blue
Bella
Buttercup

答案_

#include<bits/stdc++.h>
using namespace std;
/*	Beatrice :1Belinda : 2Bella : 3Bessie : 4Betsy : 5Blue : 6Buttercup : 7Sue : 8   */
string s1, s2, s3, s4, s5, s6; 
int n, x[10], y[10], a[10], p[10], s[10]; int f(string s) {if (s == "Beatrice") return 1;if (s == "Belinda") return 2;if (s == "Bella") return 3;if (s == "Bessie") return 4;if (s == "Betsy") return 5;if (s == "Blue") return 6;if (s == "Buttercup") return 7;if (s == "Sue") return 8;
}bool ok() {for (int i=1;i<=8;i++) p[i] = 0;for (int i=1;i<=8;i++) p[a[i]] ++; // 统计每个数的出现次数for (int i=1;i<=8;i++) if (p[i]!=1) return 0; // 判断每个数的出现次数是不是1 return 1;
} bool check() {// 先求出每个数的位置 for (int i=1;i<=8;i++) s[a[i]] = i; // a[i]这个牛的位置是第i个for (int i=1;i<=n;i++) {// 判断x[i]牛 和 y[i]牛是不是相邻if (s[x[i]] != s[y[i]] + 1 && s[x[i]] != s[y[i]] - 1) return 0;  } return 1;
} void printout() {for (int i=1;i<=8;i++) {if (a[i] == 1) printf("Beatrice\n");if (a[i] == 2) printf("Belinda\n");if (a[i] == 3) printf("Bella\n");if (a[i] == 4) printf("Bessie\n");if (a[i] == 5) printf("Betsy\n");if (a[i] == 6) printf("Blue\n");if (a[i] == 7) printf("Buttercup\n");if (a[i] == 8) printf("Sue\n");}
}int main() {scanf("%d", &n);for (int i=1;i<=n;i++) {cin >> s1 >> s2 >> s3 >> s4 >> s5 >> s6;x[i] = f(s1);y[i] = f(s6);}for (int a1=1;a1<=8;a1++) for (int a2=1;a2<=8;a2++) for (int a3=1;a3<=8;a3++) for (int a4=1;a4<=8;a4++) for (int a5=1;a5<=8;a5++) for (int a6=1;a6<=8;a6++)for (int a7=1;a7<=8;a7++) for (int a8=1;a8<=8;a8++) {// 判断a1~a8,是一个1~8的排列,且满足每一条需求a[1] = a1; a[2] = a2; a[3] = a3; a[4] = a4;a[5] = a5; a[6] = a6; a[7] = a7; a[8] = a8;if (check() && ok()) { // 判断 printout();  return 0; // 打印  结束 }}return 0;
}

这篇关于# 挤奶顺序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/681615

相关文章

顺序表之创建,判满,插入,输出

文章目录 🍊自我介绍🍊创建一个空的顺序表,为结构体在堆区分配空间🍊插入数据🍊输出数据🍊判断顺序表是否满了,满了返回值1,否则返回0🍊main函数 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以:点赞+关注+评论+收藏(一键四连)哦~ 🍊自我介绍   Hello,大家好,我是小珑也要变强(也是小珑),我是易编程·终身成长社群的一名“创始团队·嘉宾”

web群集--nginx配置文件location匹配符的优先级顺序详解及验证

文章目录 前言优先级顺序优先级顺序(详解)1. 精确匹配(Exact Match)2. 正则表达式匹配(Regex Match)3. 前缀匹配(Prefix Match) 匹配规则的综合应用验证优先级 前言 location的作用 在 NGINX 中,location 指令用于定义如何处理特定的请求 URI。由于网站往往需要不同的处理方式来适应各种请求,NGINX 提供了多种匹

[数据结构]队列之顺序队列的类模板实现

队列是一种限定存取位置的线性表,允许插入的一端叫做队尾(rear),允许删除的一端叫做队首(front)。 队列具有FIFO的性质 队列的存储表示也有两种方式:基于数组的,基于列表的。基于数组的叫做顺序队列,基于列表的叫做链式队列。 一下是基于动态数组的顺序队列的模板类的实现。 顺序队列的抽象基类如下所示:只提供了接口和显式的默认构造函数和析构函数,在派生类中调用。 #i

[数据结构]栈之顺序栈的类模板实现

栈的数组实现形式,采用动态分配数组,不够时可以调整栈的大小。 Stack.h文件:主要定义栈的抽象基类,提供公共的接口函数。 #ifndef STACK#define STACK//栈的抽象基类template<class T>class Stack{public:Stack(){}~Stack(){}virtual void Push(const T& x)=0;virt

C++中类的构造函数调用顺序

当建立一个对象时,首先调用基类的构造函数,然后调用下一个派生类的 构造函数,依次类推,直至到达派生类次数最多的派生次数最多的类的构造函数为止。 简而言之,对象是由“底层向上”开始构造的。因为,构造函数一开始构造时,总是 要调用它的基类的构造函数,然后才开始执行其构造函数体,调用直接基类构造函数时, 如果无专门说明,就调用直接基类的默认构造函数。在对象析构时,其顺序正好相反。

七、Maven继承和聚合关系、及Maven的仓库及查找顺序

1.继承   2.聚合   3.Maven的仓库及查找顺序

线性表中顺序表的合并

对两个顺序表进行合并,算法的复杂度为O(La.size+Lb.size)。 已知: 顺序线性表La和Lb的元素按值非递减排列 归并La和Lb得到的顺序线性表Lc,Lc的元素也按值非递减排列。 代码定义: void mergeList(SeqList *La,SeqList *Lb,SeqList *Lc){Lc->capacity = La->size + Lb->size;Lc->b

理解C++全局对象析构顺序与 IPC 资源管理:避免 coredump

文章目录 0. 概述1. 问题背景2. 问题分析3. 解决方案:手动释放资源4. 深入剖析:为什么手动调用 `reset()` 有效?5. 延伸思考:如何避免全局对象带来的问题?6. 总结 0. 概述 在编写 C++ 程序时,使用全局或静态对象有时可能会导致不可预期的崩溃(如 coredump)。这类崩溃通常源于对象的析构顺序、资源的管理方式,以及底层资源(如 IPC 通道或共

逆序和顺序创建单链表

单链表是一种顺序的存储方式,数据结构学的不好,考研又是必考内容,只好从头开始学习,相信不断地积累会有更好的爆发! 首先单链表的创建,单链表是建立在结构体的基础上,要创建单链表首先要建立起一个储存数据的结构体: struct node{int elem;node *next;};elem是数据域,用来存放你要输入的数据,next是指向下个存放数据节点的指针同为node 类型; 下面是

程序存储器编址及程序执行顺序

对于内部有ROM的芯片,根据情况也可以扩展外部ROM,虽然内、外程序存储器总容量可以超过64KB,但其有效存储空间只有64KB,内、外程序存储器逻辑上将共用64K存储空间。片内程序存储器地址空间和片外程序存储器的低地址空间重叠。51子系列重叠区域为0000H~0FFFH,52子系列重叠区域为0000H~1FFFH。        单片机在执行指令时,对于低地址部分,是从片内程序存