《Split Array》题目分析
本题是比较简单的贪心题目。
假设X是A数组中的最小值。那么我们就检查A数组中是不是包含子数组B = [X, X+1, X+2, ... X+K-1]。
如果A不包含B，那么X一定不能凑成"顺子"，直接返回NO。
否则我们可以把B从A中删除，然后重复这一步骤即可。
hiho一下第224周《Split Array》题目分析
3 answer(s)
楼上的代码
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int bucket[1000005];
int Tree[1000005 << 2];
int lz[1000005 << 2];
void update(int rt, int l, int r, int L, int R, int val){
if(L <= l && R >= r){
Tree[rt] += val;
lz[rt] += val;
return;
}
if(lz[rt] != 0){
Tree[rt << 1] += lz[rt];
Tree[rt << 1|1] += lz[rt];
lz[rt << 1] += lz[rt];
lz[rt << 1|1] += lz[rt];
lz[rt] = 0;
}
int mid = (l + r) >> 1;
if(mid >= L) update(rt << 1, l, mid, L, R, val);
if(mid < R) update(rt << 1|1, mid + 1, r, L, R, val);
Tree[rt] = min(Tree[rt << 1], Tree[rt << 1|1]);
}
int query(int rt, int l, int r, int L, int R){
if(L <= l && R >= r){
return Tree[rt];
}
if(lz[rt] != 0){
Tree[rt << 1] += lz[rt];
Tree[rt << 1|1] += lz[rt];
lz[rt << 1] += lz[rt];
lz[rt << 1|1] += lz[rt];
lz[rt] = 0;
}
int mid = (l + r) >> 1, mi = 0x3f3f3f3f;
if(mid >= L) mi = min(mi, query(rt << 1, l, mid, L, R));
if(mid < R) mi = min(mi, query(rt << 1|1, mid + 1, r, L, R));
return mi;
}
int main(){
int T;
scanf("%d", &T);
while(T--){
memset(bucket, 0, sizeof bucket);
memset(Tree, 0, sizeof Tree);
memset(lz, 0, sizeof lz);
int n, k;
scanf("%d%d", &n, &k);
int mx = 0;
for(int i = 0; i < n; i++){
int x;
scanf("%d", &x);
mx = max(x, mx);
bucket[x]++;
}
if(k == 1){
printf("YES\n");
continue;
}
for(int i = 1; i <= mx; i++) update(1, 1, mx, i, i, bucket[i]);
int flag = 0;
for(int i = 1; i <= mx - k + 1; i++){
int minnus = query(1, 1, mx, i, i);
if(query(1, 1, mx, i + 1, i + k - 1) < minnus){
flag = 1;
break;
}
update(1, 1, mx, i, i + k - 1, -minnus);
}
if(query(1, 1, mx, 1, mx) != 0) flag = 1;
if(flag) printf("NO\n");
else printf("YES\n");
}
return 0;
}
-
- 2018-10-17
楼上你也是
- 添加评论
这样时间复杂度是 n/k * n 吗? n是数组元素个数,k是子数组元素个数
-
- 2018-10-14
取决于“检查A数组中是不是包含子数组B”这一步怎么实现的。我们可以把A数组相同的值合并，用(值，数量)来存储。比如[(1, 2), (2, 2), (3, 3)]表示2个1，2个2，3个3。这样检查这一步就是O(K)的了。总复杂度是N / K * K 也就是O(N)的。
-
- 2018-10-16
value-count的存储方式，并不能提高时间效率吧，如果【1,2,3,5,6,7,11,12,13】这种无重复的话，那就不是O(K)的效率了。
-
- 2018-10-17
是O(K)的。比如你给的数据K=3的话，最小的是a[0]=1，这时看a[1]是不是2，a[2]是不是3，不是的话就返回NO。是的话从下一个a[3]=5再继续检查。
-
- 2018-11-13
总体时间复杂度是O(N)的。 可以这么想。如 (1,2) (2,3) (3,3)....（第一个数是值，第二个数是个数），一开始肯定是尝试“从1开始的连续k个数，每个个数都减去2”。这样的单次操作是O(K). 而总体复杂度可以这么考虑，最坏情况下是每次减的数都是1，然后最坏情况的复杂度就是所有（V[i],Cnt[i]）的序偶对中的cnt[i]的和，这个和就是N 而“从v[i]开始的连续k个数，每个序偶的cnt都减去cnt[i]”的操作只需要i从头到尾扫一遍就OK了，复杂度最坏也是O(N). 当然，这个复杂度的估计是基于cnt[i]已经为0的时候不执行O(k)的修改操作，直接continue就好了
- 添加评论
这个数组一定是连续的吗（相邻相差0或者是1） 如果输入是： 4 2 1 10 20 30 这样输出NO？ 但是感觉满足要求的，输出YES