2020 GDUT Rating Contest Ⅰ G.Livestock Lineup

G.Livestock Lineup

链接

题目描述

有八头有名字的牛，要求在满足限制条件的同时尽可能按照字典序从小到大输出他们的名字，限制条件的格式类似“ a牛 要在 b牛 旁边”这样。

题目分析

参考dl的代码后发现，有一个神奇的函数next_permutation()，可以让原序列变成离原序列最近而字典序又大于原序列的序列(语文能力有限见谅，想了解可看看大佬的博客)。

这题只有8头牛，最多也就4w左右种序列(8的阶乘)，可以直接利用该函数列出可能的序列，再用限制条件判断，即可找出答案。

//本来还想一个个分别排好，思路混乱写了100行还是没过，丢人…

代码

#include <bits/stdc++.h>

using namespace std;

char cow[8][11]={"Beatrice","Belinda","Bella","Bessie","Betsy","Blue","Buttercup","Sue"};

struct beside{
	int a;
	int b;
};

beside be[8];
int p=0;

int found(char* a)
{
	for(int i=0;i<8;i++)
		if(!strcmp(a,cow[i]))
			return i;
}

int main()
{
	int ans[10];//不设成8是因为下面判断时会到j-1,j+1
	for(int i=1;i<=8;i++)
		ans[i]=i-1;
	ans[0]=-1,ans[9]=-1;
	int n,c1,c2;
	char t1[11],t2[11];
	cin>>n;
	for(int i=0;i<n;i++){
		scanf("%s must be milked beside %s",t1,t2);//本来还想按空格分的，看dl代码发现直接这样就可
		c1=found(t1),c2=found(t2);
		be[p].a=c1,be[p].b=c2,p++;
	}
	do{
		bool yes=1;
		for(int i=0;i<p&&yes;i++){
			for(int j=1;j<=8&&yes;j++){
				if(ans[j]==be[i].a){
					int ttt=be[i].b;
					if(ans[j-1]!=ttt&&ans[j+1]!=ttt)
						yes=0;
				}
			}
		}
		if(yes)
			break;
	}while(next_permutation(ans+1,ans+9));
	for(int i=1;i<=8;i++)
		printf("%s\n",cow[ans[i]]);
}