自动搬运

查看原文

来自洛谷，原作者为

	greenheadstrange 这个家伙很菜，什么也没有留下

搬运于2025-08-24 22:00:07，当前版本为作者最后更新于2019-06-11 22:41:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本蒟蒻开始时被题目的zig，zag吓住了

其实这道题并不是splay，只是简单的推理哦！

分析：

既然题目中已经说了：先考虑使用的次数最少的单词

当我们将开头字母相同的字符串合并到一个数组，再按字典序排完序后，每个字符串都是排着队去取。

例如：split和sisak

排完序后是sisak，split

1. 第一次，次数一样，取字典序小的sisak

2. 第二次，split的次数为0，取split

3. 第三次，次数又一样，取字典序小的sisak

……

小提示

sort可以直接将字符串按字典序进行排序的qwq

下面是本蒟蒻的丑代码：（喜欢请点个赞哦）

#include<bits/stdc++.h>
using namespace std;
string s[30][10005],S;
char ch;
int n,m,num[30],p[30];//p[i]为以i开头的字符串的个数，ans[i]是一个小指针 
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>S;
		int bj=S[0]-'a'+1;
		s[bj][++num[bj]]=S;//将首字母相同的合并到一个数组中 
	}
	for(int i=1;i<=26;i++)sort(s[i]+1,s[i]+num[i]+1);//使数组中的字符有序 
	while(m--){
		ch=getchar();
		while(ch<'a'||ch>'z')ch=getchar();//快速读入，节省时间 
		int bj=ch-'a'+1;
		p[bj]++;
		if(p[bj]>num[bj])p[bj]=1;//访问完了，该回到第一个了 
		cout<<s[bj][p[bj]]<<'\n';
	}
	return 0;
}