hiho一下第224周《Split Array》题目分析

3
0

《Split Array》题目分析

本题是比较简单的贪心题目。

假设X是A数组中的最小值。那么我们就检查A数组中是不是包含子数组B = [X, X+1, X+2, ... X+K-1]。

如果A不包含B,那么X一定不能凑成"顺子",直接返回NO。

否则我们可以把B从A中删除,然后重复这一步骤即可。

  • 这个数组一定是连续的吗(相邻相差0或者是1) 如果输入是: 4 2 1 10 20 30 这样输出NO? 但是感觉满足要求的,输出YES

  • 添加评论
  • reply

3 answer(s)

0

这样时间复杂度是 n/k * n 吗? n是数组元素个数,k是子数组元素个数

  • 取决于“检查A数组中是不是包含子数组B”这一步怎么实现的。我们可以把A数组相同的值合并,用(值,数量)来存储。比如[(1, 2), (2, 2), (3, 3)]表示2个1,2个2,3个3。这样检查这一步就是O(K)的了。总复杂度是N / K * K 也就是O(N)的。

  • value-count的存储方式,并不能提高时间效率吧,如果【1,2,3,5,6,7,11,12,13】这种无重复的话,那就不是O(K)的效率了。

  • 是O(K)的。比如你给的数据K=3的话,最小的是a[0]=1,这时看a[1]是不是2,a[2]是不是3,不是的话就返回NO。是的话从下一个a[3]=5再继续检查。

  • 总体时间复杂度是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就好了

  • 添加评论
  • reply
2
   我们可以用一个桶来存储个数,这个数组中最大的数记做mx,我们按1到mx建造一棵用来查询个数最小值的线段树。到第i个位置的时候,我们先查询一下i位置的值,记做minus,然后区间查询(i + 1, i + k -1)区间的最小值是不是都大于minus,如果不是直接输出NO,都大于的话这段区间减掉minus。最后判断一下整个区间是不是都是0即可。时间复杂度O(n*log(mx)),空间复杂度比较大,约为(1e7)。
2

楼上的代码

#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;
}

write answer 切换为英文 切换为中文


转发分享