作者：有有1988_540 | 来源：互联网 | 2023-09-17 17:59
原题链接
1275 连续子段的差异
题目来源&＃xff1a; Codility
基准时间限制&＃xff1a;1 秒 空间限制&＃xff1a;131072 KB 分值: 80 难度&＃xff1a;5级算法题
给出一个包括N个元素的整数数组A&＃xff0c;包括A本身在内&＃xff0c;共有 (N&＃43;1)*N / 2个非空子段。例如&＃xff1a;1 3 2的子段为{1} {3} {2} {1 3} {3 2} {1 3 2}。在这些子段中&＃xff0c;如果最大值同最小值的差异不超过K&＃xff0c;则认为这是一个合格的子段。给出数组A和K&＃xff0c;求有多少符合条件的子段。例如&＃xff1a;3 5 7 6 3&＃xff0c;K &＃61; 2&＃xff0c;符合条件的子段包括&＃xff1a;{3} {5} {7} {6} {3} {3 5} {5 7} {7 6} {5 7 6}&＃xff0c;共9个。
Input
第1行&＃xff1a;2个数N, K&＃xff08;1 <&＃61; N <&＃61; 50000, 0 <&＃61; K <&＃61; 10^9)
第2 - N &＃43; 1行&＃xff1a;每行1个数&＃xff0c;对应数组的元素Ai(0 <&＃61; A[i] <&＃61; 10^9)
Output
输出符合条件的子段数量。
Input示例
5 2
3
5
7
6
2
Output示例
9
#include
#include
#include
#include
#define maxn 50005
using namespace std;
typedef long long ll;int deq1[maxn], deq2[maxn];
int num[maxn];
ll f(int n){return ((ll)n &＃43; 1) * n / 2;
}
int main(){// freopen("in.txt", "r", stdin);int n, k, l1 &＃61; 0, r1 &＃61; 0, l2 &＃61; 0, r2 &＃61; 0;int pre &＃61; 0;ll ans &＃61; 0, d &＃61; 0;scanf("%d%d", &n, &k);for(int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;)scanf("%d", num&＃43;i);for(int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;){while(l1 !&＃61; r1 && num[deq1[r1-1]] num[i])r2--;deq1[r1&＃43;&＃43;] &＃61; i;deq2[r2&＃43;&＃43;] &＃61; i;if(abs(num[deq1[l1]] - num[deq2[l2]] > k)){int maxs &＃61; max(deq1[l1], deq2[l2]) - 1;ans &＃43;&＃61; f(maxs - pre);ans -&＃61; d;int sign &＃61; -1;while(l1 !&＃61; r1 && num[deq1[l1]] - num[deq2[l2]] > k){if(deq1[l1] > deq2[l2]){l2&＃43;&＃43;;sign &＃61; 0;}else if(deq1[l1] }
收藏
关注
京公网安备 11010802041100号