小度熊拿到了一个无序的数组,对于这个数组,小度熊想知道是否能找到一个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
#include<iostream> #include<map> #include<stdio.h> #include<string.h> #include <climits> using namespace std; const int maxn = 12000; int n, m, k; int main() { int arr[maxn]; int store[1020]; int cas = 1; int maxx=INT_MIN, minn=INT_MAX; std::map<int, bool>mapp; while (cin >> n >> m) { for (int i = 0; i < n; i++) cin >> arr[i]; memset(store, 0, sizeof(store)); for (int i = 0; i < n; i++) { maxx = arr[i]; minn = arr[i]; mapp.clear(); for (int j = i; j < n; j++) { if (maxx < arr[j]) maxx = arr[j]; if (minn > arr[j]) minn = arr[j]; mapp[arr[j]] = true; if (maxx - minn == j - i ) if(maxx - minn + 1 == mapp.size()) store[mapp.size()]++; if (j - i > 1000) break; } } printf("Case #%d:\n", cas++); for (int i = 0; i < m; i++) { cin >> k; printf("%d\n", store[k]); } } return 0; }