hdu 5247 找連續數（思維）

找連續數

Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1207Accepted Submission(s): 435  
Problem Description 小度熊拿到了一個無序的數組，對於這個數組，小度熊想知道是否能找到一個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 2 3 2 1 4 3 5 3 4
Sample Output

Case #1: 2 2
Source 2015年百度之星程序設計大賽 - 初賽(1) 題目大意：有多少個長度與為k的區間數連續的。

解題思路：按照長度一段一段截取出來，在判斷是否連續，這樣的數據規模超時了==

首先解決是否連續的問題：我采用這個區間的最大值-最小值和長度進行比較，如果相等就是連續的~~但是這樣依舊超時！

超時的原因是：沒詢問一次兩個for循環，所以要解決這個問題，相當於打表。

采用一個vis來標記這個數是否出現過，如果出現過就不用再找下去了，出現兩個相同數字怎麼可能連續下去呢，這裡很容易理解。

再用一個ans的數組來記錄長度為1~k的分別有多少個~~這樣就可以AC了。

詳見代碼。

#include 
#include 
#include 
#include 

using namespace std;

void isSubstr(int st,int len,int c[],int a[])
{
    int k=1;
    for (int i=st; i<=st+len-1; i++)
    {
        c[k++]=a[i];
    }
}

int main()
{
    int n,m,k;
    int a[10010],ans[10010];
    int vis[100010];
    while (~scanf("%d%d",&n,&m))
    {
        for (int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
        }
        printf ("Case #1:\n");
        memset(ans,0,sizeof(ans));
        for (int i=1; i<=n; i++)
        {
            memset(vis,0,sizeof(vis));
            int Max=0,Min=9999999;
            for (int j=i; j<=n; j++)
            {
                Max=Maxa[j]?a[j]:Min;
                int l=Max-Min+1;
                if (!vis[a[j]])
                {
                    if (j-i+1==l)
                        ans[l]++;
                    vis[a[j]]=1;
                }
                else
                    break;
            }
        }
        while (m--)
        {
            scanf("%d",&k);
            cout<