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]]);
}