Sicily 1222 单词选择 (SOJ 1222)「堆 优先队列」

0.00 avg. rating (0% score) - 0 votes
转载请注明: 吹水小镇 | reetsee.com
原文链接地址: http://blog.reetsee.com/archives/195

原题地址:点击打开链接

今天我要发表一篇為什麼很多人都比较贱的演讲,因为有的人就是要到快走投无路或山穷水尽才懂得忽然拼命干正事,就像我。通常经常这样做的结果有两种——1 就是短命+每次拼都成功了;2 就是短命+不是每次都成功了。  暂时我是属于第一种,但是即将又有另外一个挑战,我觉得我真的比较贱,因为这样的生活我觉得不是正常的,我还要照顾妹子,我怎么能让身体经常受这样的折腾?所以这一次无论怎么样,我必须要平时要多下把功夫,希望应对各种挑战时投入精力的曲线能比较平滑,不要那么陡峭。

现在每天的计划非常重,杀手哥叶大神笑话我怎么来到北京还要做宅男。

每天看PAPER,实在不喜欢,我还是要敲程序的人,我TM就是去当工程师的……希望川神能顺利推我,我也能顺利通过。扯远了,下面是正文……

——————正文——————

(PS:后来发现这题有更好的解法,迟一点找个时间更新……现在还没更新)

这题看了很久,但是是在前几天,应该说是在MSRA入职后的第2天,才想到一个比较好的方法,而且讽刺的是我还是从我看的paper里面获得idea的……

思路背景:通常,给定一篇文章,我们知道里面有许多的单词,那么我们对于一个单词t在什么地方出现,可以使用一串整数来表示,例如 t: 1 3 7 10 21,就表示单词t出现在文章中的第1,3,7,10,21个单词的位置。

好了,现在就把这种思想应用到这一题,我以本题的测试样例举例。很显然,按照我刚才的方法,有如下排列:

hot : 0 4

dog: 1 2

milk: 3

其实,我们只要找出题目所说的文章中有哪些要背的单词,都可以列出上面这个表,列出上面这个表有什么用?犀利咯!你有没有发现,任意从每一行选一个数字,然后用最大的减最小的再加1,就是肯定包含了这几个单词的一段文章的长度?现在的问题就是,你用什么策略去选择这些数,或者不说选择,而是检查适合的数字们是什么。

我们首先建立一个小根堆,将每个单词开头的数字0,1,3入堆的同时,检查得到当前的最小长度是(3-0+1)=4 。 这个时候,我们我们将堆的最小元素出堆,同时检查到该元素是属于hot的,那么我们将hot的下一个元素4入堆,然后当前堆中的元素就是1,3,4,此时长度是(4-1+1)=4,没有变化,然后此时最小元素是1,出堆,同时发现1是属于dog的,而dog后面还有元素,于是将2入堆,现在堆元素为2,3,4,此时长度是(4-2+1)=3,更新当前的最小距离为3。然后我们将元素2出堆,元素2是属于dog的,但是2后面已经没有元素,我们结束计算,于是就得到最小距离3.

為什麼这个算法是正确的?要注意到,每次堆中的所有元素(实际是某个单词对应的下标),肯定覆盖了所有文章中出现的要背的单词,所以我们只需要计算堆中的最大元素和最小元素的差,再加1,就可以得到一个长度,这个范围里肯定包含了所有的单词。為什麼每次都要将最小的元素出堆,然后挑选其下一个元素?因为只有这样,才有可能使得最小长度变小,如果出堆的不是最小的元素,那么再次进入堆中的元素肯定是大于当前堆的最小元素的,因此再计算最小长度,肯定是不行的,这也解释了為什麼当发现出堆的元素后面已经没有元素时,就可以结束算法。

我解释得不太好,但是基本思路就是这样,至于其它的方面,就是将单词映射为数字,例如hot是1,dog是2,milk是3,然后用一个vector v[4],v[1][0]就表示hot的第一个出现位置这样的,需要用到map,不过就用那么一小下,在建立好上面那个表后就不需要用了。其次是堆中存储的元素的数据结构,里面包含了下标,包含了当前下标对应的单词编号,以及当前下标在表中对应的下标是多少,例如对于0,就是存储了{0,1,0},对于2就是存储了{1,2,1}。我这么说可能更加乱……按照自己的思路写就好,毕竟最关键只是基本算法,细枝末节什么的,能实现就好。

这题需要注意的地方是,当文章中没有出现要背的单词,那么输出两个0就可以了,我因为这个runtime error了一次。

下面就贴代码了,我写得非常丑啊,而且堆这个数据结构也是手敲的,所以代码小长,但是结构还是比较清晰的。各位也可以使用STL中内置的优先队列,更加快更加短就能解出这题,只是我想写一下堆。果不其然,我真的写错了一次,后来又去翻算法导论这本书……

代码如下(VIM写的代码贴到这里全走样了):

#include<iostream>
#include<stdio.h>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#define MAX 0x7fffffff
#define MM 100005
#define MN 1005
using namespace std;
int n,m;
string s;
struct node
{
  int index,p,mark;
  node(){}
  node(int ii, int pp, int mm){
      index=ii;
      p=pp;
      mark=mm;
  }
}heap[2*MM];
int max_index;
int ans;
vector<node> v[MN];
int heap_size;
int l,r;
void enHeap(node &e)
{
   max_index = max(max_index,e.index);
   heap[++heap_size]=e;
   int cur=heap_size;
   while(cur>1)
   {
     if(heap[cur].index<heap[cur/2].index) 
     {
        swap(heap[cur],heap[cur/2]);
        cur=cur/2;
     }
     else
           break;
   }
}
void popHeap()
{
     int p=heap[1].p;
     int mm=heap[1].mark+1;
     if(mm==v[p].size())
     {
         heap_size--;
         return;
     }
     heap[1]=v[p][mm];
     max_index=max(heap[1].index,max_index);
     int cur=1;
     int smallest,l,r;
     while(cur*2<=heap_size)
     {
         smallest=cur;
         l=cur*2;
         r=cur*2+1;
         if(heap[l].index<heap[smallest].index)
         {
             smallest=l;
         }
         if(r<=heap_size && heap[r].index<heap[smallest].index)
         {
             smallest=r;
         }
         if(smallest==cur)
           break;
         swap(heap[cur],heap[smallest]);
         cur=smallest;
     }
}
int main()
{
    //freopen("in","r",stdin);
    //freopen("out","w",stdout);
    map<string, int> mp;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        cin>>s;
        mp[s]=i+1;
    }

    int tmp;
    scanf("%d",&m);
    for(int i=0;i<m;i++)
    {
      cin>>s;
      if(tmp=mp[s])
        v[tmp].push_back(node(i,tmp,v[tmp].size()));
    }

    int cnt=0;
    for(int i=0;i<=n;i++)
    {
      if(v[i].size())
        {
          cnt++;
          if(heap_size)
            enHeap(v[i][0]);
          else
            heap[++heap_size]=v[i][0];
        }
    }
    if(cnt==0)
    {
      printf("0\n0\n");
        return 0;
    }
    ans=MAX;
    while(heap_size==cnt)
    {
      ans=min(ans, max_index-heap[1].index+1);
      popHeap();
    }
    printf("%d\n%d\n",cnt,ans);
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注