字节跳动2019第一次笔试题第四题

- 日理万妓 2022-02-20 10:50 237阅读 0赞

# 前言 #

我看了好多博客的解法都是  O ( n 2 ) O(n^2) O(n2) 复杂度的, 显然不对啊老哥们…

# 题目描述 #

两个长度为n的序列a，b。问有多少个区间\[l，r\]满足max(a\[l,r\])<min(b\[l,r\])即a区间的最大值小于b区间的最小值数据范围：n<1e5，a(i),b(i)<1e9

输入描述：

第一行一个整数n

第二行n个数，第i个为a(i)

第三行n个数，第i个为b(i)

0<1<=r<n

输出描述：

一行一个整数，表示答案

例1：输入

3 2 1

3 3 3

输出： 3

# 思路 #

一开始看这个题没反应过来, 以为是4层循环, 后来发现是在问同一区间内  m a x ( a ) < m i n ( b ) max(a)< min(b) max(a)<min(b), 那么思路就来了  
想象一下, 如果是同一区间 a 的最大值小于 b 的最小值, 那么 **这个区间内的 a 都小于 b**, 因此 **如果创建一个新的序列 c = b - a, 那么这个序列在对应区间上都是正数**. 那么如果这个区间长度是  n n n, 就对应了 n × ( n + 1 ) 2 \\frac\{n\\times(n+1)\}\{2\} 2n×(n\+1) 个子区间.  
所以, 思路就是, 从头遍历 c, 记录每段连续正数的长度, 然后计算这段区间对应的子区间总数.

# 代码 #

#include <stdio.h>
    
    int n;
    int a[100000];
    
    int main() { 
    	scanf("%d", &n);
    	for (int i = 0; i < n; i++) scanf("%d", a + i);
    	for (int i = 0; i < n; i++) { 
    		int tmp;
    		scanf("%d", &tmp);
    		// 我把a, b, c 3个数组压缩到1个
    		a[i] = tmp - a[i];
    	}
    	int count = 0;
    	int positive_count = 0;
    	for (int i = 0; i < n; i++) { 
    		if (a[i] > 0) positive_count++;
    		else if (positive_count > 0) { 
    			count += (positive_count * (positive_count + 1)) / 2;
    			positive_count = 0;
    		}
    	}
    	// 最后再计算一次
    	if (positive_count > 0) { 
    		count += (positive_count * (positive_count + 1)) / 2;
    	}
    	printf("%d", count);
    }