P2237 [USACO14FEB]自动完成Auto-complete

  题意大概就是:给出n个字符串,有m个询问:每次给出字符串s,整数k,问在所有以s为前缀的字符串中,字典序第k大的,是那n个串中的第几个。

  我一开始做的时候忽略了一个问题:就是对于两个串a,b,你直接输出 a >  b 是有值的。也就是说,字符串是可以直接比较的,我们能O(1)两个串比较大小(因为就是asic码不是嘛)。

  显然,我们是要在以s为前缀的这个连续的整体里去判断。那么既然字符串的比较和整型变量一样,可以排序——这样就得到了连续的一段。

  这之后,我们只需要二分找第一个前缀 >= k 的,判断从这个开始第k个,和s是否相等就可以了。

  复杂度:O(1000 m log(n) ),没有问题。

  代码时间——

  

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<string>
#include<vector>
using namespace std;
#define maxn 50000
struct node
{
  string s;
  int id;
  friend bool operator < (node a,node b)
  {
    return a.s < b.s;
  }
} q[maxn];
int n,m;
int match(int p,string s)
{
  if(s.length()>q[p].s.length()) return -1;
  bool flag=0;
  for(int i=0;i<s.length();i++)
      if(q[p].s[i]!=s[i]) 
      {
          flag=1;
          break;
    }
    if(flag) return -1;
    return q[p].id;
}
int find(string s)
{
    int L=1,R=n;
    int ans=0;
    while(L<=R)
    {
        int mid=(L+R)>>1;
        if(q[mid].s>=s) 
        {
            ans=mid;
            R=mid-1;
        }
        else L=mid+1;
    }
    return ans;
}
int solve(string s,int x)
{
  int p=find(s);
  if(p>n) return -1;
  p+=x-1;
  return match(p,s);
}
int main()
{
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++)
  {
    cin>>q[i].s;
    q[i].id=i;
  }
  sort(q+1,q+n+1);
  for(int i=1;i<=m;i++)
    {
      string s;
      int x;
      cin>>x>>s;
      cout<<solve(s,x)<<endl;
    }
  return 0;
}

 

  

上一篇:华工软院IBM LinuxONE Community Cloud云计算实验


下一篇:代码大全 code complete 阅读笔记-5 第十六章 循环结构