51nod 1526 分配笔名（Trie树+贪心）

建出Trie树然后求出一个点子树中有多少笔名和真名。然后贪心匹配即可。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

const int N=810000;

int ans,n;

char s[N];

struct trie{

	int trans[N][27],tot,size[N][2],len[N];

	void ins(char *s,int k){

		int L=strlen(s+1);

		int now=0,lon=0;

		for(int i=1;i<=L;i++){

			if(trans[now][s[i]-'a'+1]==0)trans[now][s[i]-'a'+1]=++tot,len[tot]=len[now]+1;

			now=trans[now][s[i]-'a'+1];

		}

		size[now][k]++;

	}

	void dfs(int u){

		for(int i=1;i<=26;i++){

			int v=trans[u][i];

			if(v==0)continue;

			dfs(v);

			size[u][0]+=size[v][0];

			size[u][1]+=size[v][1];

		}

		int tmp=min(size[u][0],size[u][1]);

		ans+=tmp*len[u];

		size[u][0]-=tmp;size[u][1]-=tmp;

	}

}trie;

int main(){

	scanf("%d",&n);

	for(int i=1;i<=n;i++){

		scanf("%s",s+1);

		trie.ins(s,0);

	}

	for(int i=1;i<=n;i++){

		scanf("%s",s+1);

		trie.ins(s,1);

	}

	trie.dfs(0);

	printf("%d",ans);

	return 0;

}

巴特西

51nod 1526 分配笔名（Trie树+贪心）

最新文章

热门文章