水 P4432 【ZigZag】

greenheadstrange · 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;
}