首页 > 名作之壁
开通博客写题解
头像 黑布林大狸子
发表于 2020-08-22 23:54:43
题目大意   给定一个序列，求有多少个区间满足区间最大值减区间最小值大于k。 解题思路   可以从反面入手来解决这个问题，就是把答案变成区间个数减去区间最大值减最小值小于等于k的区间个数，求后者我们可以通过枚举区间的右端点找区间左端点有多少种可能的情况，然后累加起来就行了。我们可以发现如果区间 满足 展开全文
去ta的博客 赞 (7) 回复(0) 收起
头像 璃墨韵
发表于 2020-08-25 11:20:05
由于n<=10^7，所以只能够是线性复杂度的做法，题意里涉及维护最大值，最小值，考虑使用单调队列维护最大值和最小值，而若[l,r]满足题意，显然【l,R】(R>r)也满足题意（因为新的最大值只会大于等于原最大值，新最小值小于等于原最小值），所以当[l,r]满足题意时，则会由n-r+1个区 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 bai_qi
发表于 2020-09-07 17:33:23
题目描述《无限的斯特拉托斯》又称之为名作之壁，其销量一直被圈内人士津津乐道。给你n个数字，第i个数字a[i]表示名作之壁第ii天的销量。若某段区间[l,r][l,r]中最大值和最小值之差大于kk，则称该区间为畅销区间。请问一共有多少个区间为畅销区间？思路：两个单调队列，记录最大值最小值，然后比较记录 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”