将字符串的信息放到trie树以后，贪心地合并深度最深的姓名和笔名。若某深度中有一些姓名和笔名剩余，那么就将剩余的部分上传至深度减一的节点中去，企图与深度减一的姓名和笔名进行合并。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=8e5+5;
int n;
ll ans;
int tot,ch[N][26];
vector<int>cnt[N][2];
string s;
struct node{int x,y;};
vector<node>anss;
void dfs(int u,int dep)
{
for (register int i=0; i<26; ++i)
{
int v=ch[u][i];
if (v)
{
dfs(v,dep+1);
for (register int j=0; j<cnt[v][0].size(); ++j) cnt[u][0].push_back(cnt[v][0][j]);
for (register int j=0; j<cnt[v][1].size(); ++j) cnt[u][1].push_back(cnt[v][1][j]);
}
}
int now=min(cnt[u][0].size(),cnt[u][1].size());
ans+=(ll)now*dep;
for (register int i=1; i<=now; ++i)
{
anss.push_back((node){cnt[u][0][cnt[u][0].size()-1],cnt[u][1][cnt[u][1].size()-1]});
cnt[u][0].pop_back(); cnt[u][1].pop_back();
}
}
int main(){
scanf("%d",&n);
for (register int i=1; i<=n; ++i)
{
cin>>s;
int len=s.length();
int now=0;
for (register int j=0; j<len; ++j)
{
int x=s[j]-'a';
if (!ch[now][x]) ch[now][x]=++tot;
now=ch[now][x];
}
cnt[now][0].push_back(i);
}
for (register int i=1; i<=n; ++i)
{
cin>>s;
int len=s.length();
int now=0;
for (register int j=0; j<len; ++j)
{
int x=s[j]-'a';
if (!ch[now][x]) ch[now][x]=++tot;
now=ch[now][x];
}
cnt[now][1].push_back(i);
}
dfs(0,0);
printf("%lld\n",ans);
for (register int i=0; i<anss.size(); ++i) printf("%d %d\n",anss[i].x,anss[i].y);
return 0;
}
Processed:
0.016, SQL:
8
