题目要求我们求连号的区间数，即这个区间内的数字经过排序之后，是连号的，若用暴力的做法枚举加排序进行判断的话自然会超出时间限制，由此可以在判断的这步内想办法进行优化。仔细观察我们想到，当一个区间是连续的话，那么这个区间内数的个数就是其中最大值减去最小值后再加一恰好就是这个区间的个数，由此便可以省去判断时大部分的时间，只需要在枚举的时候将最大最小值记录下来就可以了。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N = 10010; int n; int s[N]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &s[i]); } int ans = 0; for (int i = 0; i < n; i++) //枚举区间 { int max = 0, min = N; for (int j = i; j < n; j++) //一个数也满足要求由此从i开始 { if (s[j] > max) //记录最大最小 { max = s[j]; } if (s[j] < min) { min = s[j]; } if ((max - min) == (j - i)) //判断当前区间是否符合要求 { ans++; } } } printf("%d", ans); return 0; }
在三个数组之中，求能够找到多少个三元组满足Ai<Bj<Ck，由于数据非常大，若三个数组都枚举的话则会严重超时，根据时间复杂度的计算最多只能够枚举一个数组，但由规律可知，当Bj确定下来的时候，Ai是必须大于Bj且Ck要大于Bj的。由此问题可以转化成b中的每一个数，大于A中的元素数量，且小于C中的元素数量之积的和。此时便有两种方式可以进行实现，第一种便是先排序后二分，第二种就是使用前缀和进行统计。这里使用前缀和的方式进行说明。需要两个数组，一个表示a中小于x的个数，第二个表示c中大于x的个数，计算完前缀和之后依序遍历数组b即可得到结果。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; const int N = 100010; int n; int a[N], b[N], c[N]; int as[N]; // as[i]表示在A[]中有多少个数小于b[i] int cs[N]; // cs[i]表示在C[]中有多少个数大于b[i] int cnt[N], s[N]; int main() { scanf("%d", &n); for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]), a[i] ++ ; for (int i = 0; i < n; i ++ ) scanf("%d", &b[i]), b[i] ++ ; for (int i = 0; i < n; i ++ ) scanf("%d", &c[i]), c[i] ++ ; //求a中小于b[i]的个数 for (int i = 0; i < n; i ++ ) cnt[a[i]] ++ ; //前缀和数组是从1开始的由此要先+1 for (int i = 1; i < N; i ++ ) s[i] = s[i - 1] + cnt[i]; //计算前缀和 for (int i = 0; i < n; i ++ ) as[i] = s[b[i] - 1]; //计算比b[i]小的数 memset(cnt, 0, sizeof cnt); memset(s, 0, sizeof s); for (int i = 0; i < n; i ++ ) cnt[c[i]] ++ ; for (int i = 1; i < N; i ++ ) s[i] = s[i - 1] + cnt[i]; for (int i = 0; i < n; i ++ ) cs[i] = s[N - 1] - s[b[i]]; //计算比b[i]大的数 LL res = 0; //答案会爆int所以用long long存 for (int i = 0; i < n; i ++ ) res += (LL)as[i] * cs[i]; cout << res << endl; return 0; }
