第3题 完美区间 查看测评数据信息
有n个五颜六色的宝石挂成一排。小明觉得,对于每个宝石来说,只有它和前一个颜色相同的宝石距离不超过K才是好看的。(当这个宝石之前没有和他颜色相同的宝石时,这个宝石也勉强算好看吧,不然难看的宝石也太多了,小明如是说。)小明需要选取一个区间的宝石来布置他屋子,所以他需要选择一个完美的区间,即将这个区间截取出来之后满足每个宝石都是好看的。现在对于这一排宝石,小明想知道,有多少个完美的区间。
输入格式
第一行输入两个数n,k
第二行输入n个整数color[i],color[i]表示第i个宝石的颜色
1<=n,k,color[i]<=1e5
输出格式
一个正整数,表示完美区间的个数
输入/输出例子1
输入:
8 3
1 4 3 2 1 4 1 2
输出:
27
样例解释
比如:区间[1,6],气球颜色分别为[1,4,3,2,1,4],因为第5个气球与第一个1气球颜色相同但是距离大于了3,所以不是完美区间。区间[4,7],气球颜色分别为[2,1,4,1],是完美区间。
看到题目,就感觉可以枚举L,R端点,暴力去做(类似dp嘛),但是肯定超时,所以。对于这种数据范围大的区间的题,我们可以很自然的想到一种思想,当然对于我来说我是新思路
区间类题目思路:枚举合法区间的左端点,看看右端点是否合法(例如可以用二分枚举右端点,又或者kmp的跳一跳思想)
我们考虑答案会由什么贡献而来。
考虑每一个宝石:
1.单独的一个宝石,也就是第一次出现的宝石,肯定合法
2.在这个宝石的前面有与它颜色相同的宝石,且距离<=k,肯定合法
所以我们的答案贡献肯定来自于这两种情况
对于第二种情况,我们可以记录一下前一个宝石所在位置,不然没办法计算
预处理b[i] ,表示a[i]前面最近的与a[i]颜色相等的下标,这个下标与i的差值>k才记录(因为是不合法的才记录,这样便于我们后续求答案,因为直接求合法的太麻烦了,属于是转化问题了)
前面没有a[i]的这种颜色(第一次出现):b[i]=0
预处理c[i],表示b数组的前缀最大值
为什么开c数组?
如果b数组每个值都是散开的,不方便统计答案,毕竟统计答案的是一个区间啊
对于一个区间(例如3~5),如果它是不合法的,那么比这个区间大的区间(例如2~9,或者3~6)也肯定是不合法的,所以带有一种”继承性“
现在可以枚举L,看哪些R合法
如果L~R中每个 c[i]<L,那就合法(因为只要c数组有标记过的都是距离>k的,如果是=L的话也在L的区间,也是不合法的)
举个例,假设现在枚举的区间是2~5,L=2,R=5(红色线),是合法的,满足所有 c[i]<L
假设现在枚举的区间是2~5,L=2,R=7(蓝色线),是不合法的,因为 c[6]>=L
Code
#include <bits/stdc++.h> using namespace std; const int N=1e5+5; int n, k, a[N], fst[N], b[N], c[N], ans=0; int main() { scanf("%d%d", &n, &k); for (int i=1; i<=n; i++) { scanf("%d", &a[i]); if (i-fst[a[i]]>k) b[i]=fst[a[i]]; fst[a[i]]=i; } c[1]=b[1]; for (int i=2; i<=n; i++) c[i]=max(b[i], c[i-1]); for (int i=1; i<=n; i++) { int L=i, R=n, j=0; while (L<=R) { int mid=(L+R)>>1; if (c[mid]<i) j=mid, L=mid+1; else R=mid-1; } ans+=j-i+1; } printf("%d", ans); return 0; }
标签:思想,宝石,完美,合法,int,枚举,区间 From: https://www.cnblogs.com/didiao233/p/18361695