离散化+差分的坑

4月24日，周赛题T4。
https://leetcode-cn.com/problems/number-of-flowers-in-full-bloom/
根据题目，想到离散化+差分处理。
tle代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
public:
    int a[300005];
    vector<int>alls;
    int find(int x)
    {
        int l = 0;
        int r = alls.size()-1;
        while(l<r)
        {
            int mid = (l+r)>>1;
            if(alls[mid]>=x) r= mid;
            else l = l+1;
        }
        return l;
    }
    vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& persons) {
        vector<pair<int,int>>add;
        int n =persons.size();
        for(int i=0;i<flowers.size();i++)
        {
            int l = flowers[i][0];
            int r = flowers[i][1];
            add.push_back({l,r});
            alls.push_back(l);
            alls.push_back(r);
        }
        for(int i=0;i<persons.size();i++)
        {
            int q = persons[i];
            alls.push_back(q);
        }
        sort(alls.begin(),alls.end());
        alls.erase(unique(alls.begin(),alls.end()),alls.end());
        // for(int i=0;i<alls.size();i++)
        // {
        //     cout<<alls[i]<<" ";
        // }
        // cout<<endl;
        for(int i=0;i<add.size();i++)
        {
            int l = find(add[i].first);
            int r =find(add[i].second);
            a[l]+=1;
            a[r+1]-=1;
        }
        for(int i=1;i<=alls.size();i++)
        {
            a[i] += a[i-1];
        }
        // for(int i=0;i<=alls.size();i++)
        // {
        //     cout<<a[i]<<" ";
        // }
        vector<int>ans(n);
        for(int i=0;i<n;i++)
        {
            ans[i]=a[find(persons[i])];
        }
        return ans;

    }
};

超时原因，离散化后进行差分时 r+1的度量是不一样的，所以要对r+1也进行离散化。
因此代码改为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
public:
    int a[300005];
    vector<int>alls;
    int find(int x)
    {
        int l =0;
        int r= alls.size();
        while(l<r)
        {
            int mid =(l+r)>>1;
            if(alls[mid]>=x) r =mid;
            else l =mid+1;
        }
        return l;
    }
    vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& persons) {
        int n=persons.size();
        vector<pair<int,int>>add;
        for(int i=0;i<flowers.size();i++)
        {
            int l  =flowers[i][0];
            int r =flowers[i][1];
            add.push_back({l,r});
            alls.push_back(l);
            alls.push_back(r);
        }
        for(int i=0;i<n;i++)
        {
            alls.push_back(persons[i]);
        }

        sort(alls.begin(),alls.end());
        alls.erase(unique(alls.begin(),alls.end()),alls.end());
        for(auto&p:add)
        {
            int l = find(p.first);
            int r = find(p.second+1);
            a[l]+=1;
            a[r]-=1;
        }
        for(int i=1;i<alls.size();i++)
        {
            a[i]+=a[i-1];
        }
        //cout<<a[0]<<" ";
        // for(int i=1;i<alls.size();i++)
        // {
        //     cout<<a[i]<<" ";
        // }
        vector<int>ans(n);
        for(int i=0;i<n;i++)
        {
            ans[i] = a[find(persons[i])];
        }
        return ans;
    }
};

顺利通过

算法
离散化+差分的坑
http://jty-123.github.io/2021/04/24/离散化+差分的坑/
作者
Jty
发布于
2021年4月24日
许可协议