# 找连续数

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 179    Accepted Submission(s): 65

Problem Description

Input

Output

Sample Input
6 2 3 2 1 4 3 5 3 4

Sample Output
Case #1: 2 2

Mean:

analyse:

Time complexity: O(n)

Source code:

/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-05-30-22.26
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define  LL long long
#define  ULL unsigned long long
using namespace std;
const int MAXN=10010;
int m,n,k,Ans;
int flag;
long long num[MAXN];
long long minNum,sumNum;

map<long long,int> Hash;
long long tHash[MAXN*2];
int tot;

long long sum[MAXN];

int vis[MAXN*2];

long long stTableMin[MAXN][35],preLog2[MAXN];
void StPrepare(){
preLog2[1]=0;
for(int i=2;i<=n;i++){
preLog2[i]=preLog2[i-1];
if((1<<preLog2[i]+1)==i) preLog2[i]++;
}
for(int i=n;i>=0;--i){
stTableMin[i][0]=num[i];
for(int j=1;(i+(1<<j)-1)<=n;++j)
stTableMin[i][j]=min(stTableMin[i][j-1],stTableMin[i+(1<<j-1)][j-1]);
}
}
int queryMin(int l,int r){
int len=r-l+1,k=preLog2[len];
return min(stTableMin[l][k],stTableMin[r-(1<<k)+1][k]);
}

int main()
{
printf("Case #1:\n");
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%I64d",&num[i]);
for (int i=1;i<=n;i++)
{tHash[i*2-1]=num[i];tHash[i*2]=num[i]+1;}
sort(tHash+1,tHash+n*2+1);
tHash[0]=-1;
for (int i=1;i<=n*2;i++)
{
if (tHash[i]!=tHash[i-1])Hash[tHash[i]]=++tot;
}

for (int i=1;i<=n;i++) num[i]=Hash[num[i]];

sum[0]=0;
for (int i=1;i<=n;i++) sum[i]+=sum[i-1]+num[i];
StPrepare();

for (int i=1;i<=m;i++)
{
scanf("%d",&k);
Ans=0;flag=0;
memset(vis,0,sizeof(vis));
for (int j=1;j<=k;j++)
{
vis[num[j]]++;
if (vis[num[j]]==2) flag++;
}
if (!flag)
{
minNum=queryMin(1,k);
sumNum=sum[k]-sum[0];
if (sumNum==(long long)(minNum+minNum+k-1)*(long long)k/(long long)2) Ans++;
}

for (int left=2;left<=n;left++)
{
int right=left+k-1;
if (right>n) break;

vis[num[left-1]]--;
if (vis[num[left-1]]==1) flag--;
vis[num[right]]++;
if (vis[num[right]]==2) flag++;

if (!flag)
{
minNum=queryMin(left,right);
sumNum=sum[right]-sum[left-1];
if (sumNum==(long long)(minNum+minNum+k-1)*(long long)k/(long long)2) Ans++;
}
}
printf("%d\n",Ans);
}

return 0;
}
View Code

|
11月前
|

323 0
|
9月前
|

27 0
|
9月前
|

51 0
|
9月前
|

45 0
|
9月前
|

52 0
|
9月前
|

82 0
|

(dfs）（枚举）第十四届蓝桥杯第三次模拟赛：9.最大滑雪长度
(dfs）（枚举）第十四届蓝桥杯第三次模拟赛：9.最大滑雪长度
111 0
[#4练习赛]选代表

74 0
|

Interview：算法岗位面试—10.30上午上海某信息公司(偏图算法)技术面试之单链表反转、给定整型数组和目标值 二分法查找+下午上海某金融公司(AI岗位，上市)CTO和主管技术面试之Xcepti
Interview：算法岗位面试—10.30上午上海某信息公司(偏图算法)技术面试之单链表反转、给定整型数组和目标值 二分法查找+下午上海某金融公司(AI岗位，上市)CTO和主管技术面试之Xcepti
112 0
|

【云栖号案例 | 新零售】三只松鼠2019年全平台双11用时19分23秒破亿的秘诀

2320 0