找连续数 HDU - 5247-白红宇

找连续数 HDU - 5247

阅读量：4114 次

发布时间：2019-05-25

本文共 1120 字，大约阅读时间需要 3 分钟。

小度熊拿到了一个无序的数组，对于这个数组，小度熊想知道是否能找到一个k 的区间，里面的 k 个数字排完序后是连续的。

现在小度熊增加题目难度，他不想知道是否有这样的 k 的区间，而是想知道有几个这样的 k 的区间。

Input输入包含一组测试数据。

第一行包含两个整数n，m，n代表数组中有多少个数字，m 代表针对于此数组的询问次数，n不会超过10的4次方，m 不会超过1000。第二行包含n个正整数，第 I 个数字代表无序数组的第 I 位上的数字，数字大小不会超过2的31次方。接下来 m 行，每行一个正整数 k，含义详见题目描述，k 的大小不会超过1000。

Output第一行输"Case #i:"。(由于只有一组样例，只输出”Case #1:”即可)

然后对于每个询问的 k，输出一行包含一个整数，代表数组中满足条件的 k 的大小的区间的数量。

Sample Input

6 23 2 1 4 3 534

Sample Output

Case #1:22

思路：当时做这个题的时候忘记预处理这件事情了，一开始用线段树后来用的优先队列，但是都TLE了，然后才想起来预处理这个东西。。。。。。我们可以离线处理一下，把所有满足条件的区间都找出来，我们可以直接用set进行处理。

1.如果当前区间内已经包含过这个数，则这个区间肯定不满足条件，break

2.判断当前区间内最大值与最小值之差+1==s.size()；

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             using namespace std;const int maxn=1e4+10;int a[maxn];int num[maxn];set
             
               s;int main(){ int m,n; memset(num,0,sizeof(num)); cout<<"Case #1:"<
              
               >n>>m; for(int i=0; i

::iterator it; if(s.find(a[j])!=s.end()) { break; } s.insert(a[j]); it=s.end(); --it; int minn=*(s.begin()); int maxx=*it; if(maxx-minn+1==s.size()) num[s.size()]++; } } for(int i=0; i

>k; cout<

转载地址：http://dbgsi.baihongyu.com/

你可能感兴趣的文章

TinyMCE 富文本编辑器 ━━ （Version: 5.0.4）内含icon对照表（转载）