URAL 1542.Autocomplection(線分樹+STL)
n個の単語の中から、与えられた文字列をプレフィックスとする頻度が最も高い10個の単語を選択します.
最初に文字列で並べ替えます.線分樹で区間の一番高い10の単語を探しています.ツリーに文字列を直接保存することはできません.ポインタを使います.葛藤します
最初に文字列で並べ替えます.線分樹で区間の一番高い10の単語を探しています.ツリーに文字列を直接保存することはできません.ポインタを使います.葛藤します
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <deque>
#include <string>
#define LL long long
#define DB double
#define SI(a) scanf("%d",&a)
#define SD(a) scanf("%lf",&a)
#define SS(a) scanf("%s",a)
#define SF scanf
#define PF printf
#define MM(a,v) memset(a,v,sizeof(a))
#define REP(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define REPD(i,a,b) for(int (i)=(a);(i)>(b);(i)--)
#define N 100009
#define INF 0x3f3f3f3f
#define EPS 1e-8
#define bug puts("bug")
using namespace std;
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
struct nod{
string s;
bool operator<(const nod t )const
{
return s<t.s;
}
int k;
}re[N],ans[20];
struct TT{
int num;
nod *t[15];
} T[N<<2];
void update(int rt)
{
int a=0,b=0,cnt=0;
while(a<T[rt<<1].num||b<T[rt<<1|1].num)
{
if(b==T[rt<<1|1].num||a<T[rt<<1].num&&(T[rt<<1].t[a]->k>T[rt<<1|1].t[b]->k||
(T[rt<<1].t[a]->k==T[rt<<1|1].t[b]->k&&T[rt<<1].t[a]->s<T[rt<<1|1].t[b]->s)))
T[rt].t[cnt++] = T[rt<<1].t[a],a++;
else
T[rt].t[cnt++] = T[rt<<1|1].t[b],b++;
if(cnt>9) break;
}
T[rt].num = cnt;
}
void build(int rt,int l,int r)
{
if(l==r)
{
T[rt].num = 1;
T[rt].t[0] = &re[l];
return ;
}
int m = (l+r)>>1;
build(lson);
build(rson);
update(rt);
}
char ch[20];
int n,m;
int cmp1(nod d,nod c)
{
return d.s<c.s;
}
int cmp2(nod d,nod c)
{
REP(i,0,(int)d.s.length())
{
if(c.s[i]!=d.s[i])
return c.s[i]>d.s[i];
}
return 0;
}
int cnt;
void in(nod s)
{
ans[cnt++] = s;
REPD(i,cnt-1,0)
{
if(ans[i-1].k<ans[i].k||(ans[i-1].k==ans[i].k&&ans[i-1].s>ans[i].s))
swap(ans[i-1],ans[i]);
}
if(cnt>10) cnt--;
}
void selec(int L,int R,int rt,int l,int r)
{
if(L<=l&&r<=R)
{
REP(i,0,T[rt].num)
in(*T[rt].t[i]);
return ;
}
int m = (l+r)>>1;
if(L<=m) selec(L,R,lson);
if(R>m) selec(L,R,rson);
}
void solve()
{
string c = ch;
int f,t;
nod tmp;tmp.s = ch;
f = lower_bound(re,re+n,tmp,cmp1)-re;
t = upper_bound(re,re+n,tmp,cmp2)-re-1;
cnt = 0;
if(f<=t)
selec(f,t,1,0,n-1);
REP(i,0,cnt) cout<<ans[i].s<<endl;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
SI(n);
REP(i,0,n)
{
SS(ch);SI(re[i].k);
re[i].s = ch;
}
SI(m);
sort(re,re+n);
build(1,0,n-1);
while(m--)
{
SS(ch);
solve();
if(m) cout<<endl;
}
return 0;
}