2022 02 24 字节跳动2019春招 万万mei想到之抓捕孔连顺

 2022 02 24 字节跳动2019春招 万万mei想到之抓捕孔连顺

 2022 02 24 字节跳动2019春招 万万mei想到之抓捕孔连顺

 2022 02 24 字节跳动2019春招 万万mei想到之抓捕孔连顺

 2022 02 24 字节跳动2019春招 万万mei想到之抓捕孔连顺

 很有意思的一道题,时间复杂度卡得很死,求组合数的函数返回值是int的话会有两组数据过不了;还有第21行的j=0 的位置也很妙,如果放到for循环里面,每次循环j从0开始的话也会有一组数据过不了。

基本思想就是:要求三个满足条件的位置,那么只需要三个数里面的最大值和最小值满足条件即可,然后固定最大值的位置,加上 从满足条件的区域中任取两个数 的情况即可;

关于j的取值,有滑动窗口的说法,因为数据是递增的,对于前一个i,满足条件的p[i]-p[j]的最小值已经是j,那么相对于i+1,p[i+1]>p[i],所以要寻找满足条件的j,只需从上一轮循环的j开始找即可,所以j=0应该放在for循环外。

#include<iostream>
using namespace std;

int N, D;
const int NUM = 1000005;
long long p[NUM];

long long zuheshu(long long n)
{
	return n * (n - 1) / 2;
}
int main()
{
	cin >> N >> D;
	int i, j;
	for (i = 0; i < N; i++)
		cin >> p[i];

	long long sum = 0;
    
	j = 0;
	for (i = 2; i < N; i++)
	{
		while ((p[i] - p[j]) > D)
			j++;
		sum += zuheshu(i-j);
	}
	sum %= 99997867;
	cout << sum;
	return 0;
}

 

上一篇:Add to Square


下一篇:C语言-八进制转十进制