程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 5247 找連續數(思維)

hdu 5247 找連續數(思維)

編輯:C++入門知識

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<

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved