牛客练习赛3 F - 监视任务—

题目

$Reki$ 在课余会接受一些民间的鹰眼类委托，即远距离的狙击监视防卫.。$Reki$ 一共接收到$m$份委托，这些委托与 $n$ 个直线排布的监视点相关。第 $i$ 份委托的内容为：对于区间 $[r_i, \ j_i]$ 中的监视点，至少要防卫其中的 $k_i$ 个点。$Reki$ 必须完成全部委托，并希望选取尽量少的监视点来防卫。（$n \leq 500000, \ m \leq 1000000$）。

分析

一眼看，发现是道差分约束的裸题。设点i的值为sum[i]，如果l-r中至少有x个，就是sum[r]-sum[l-1]>=x。

我们把区间根据右端点大小排序。对于每一个区间，若这个区间满足条件就continue，如果不满足就尽量填在右边。

我们采用树状数组来维护，对相应的点进行加1操作、对区间求和操作。最多修改 $n$ 个点，时间复杂度为$O(n \log n)$.

#include<bits/stdc++.h>

using namespace std;

const int maxn =  + ;

const int maxm =  + ;

int a[maxn], n, m;

bool vis[maxn];

struct Node

{

    int l, r, k;

    bool operator< (const Node& b) const

    {

        if(r != b.r)  return r < b.r;

        if(l != b.l )  return l < b.l;

        return k > b.k;

    }

}q[maxm];

struct BIT

{

    int C[maxn];

    void init()

    {

        memset(C, , sizeof(C));

        //for (int i = 1; i <= n; i++)

          //  add(i, a[i]);

    }

    int lowbit(int x)

    {

        return x & -x;

    }

    int sum(int x)

    {

        int ret = ;

        while (x > )

        {

            ret += C[x];

            x -= lowbit(x);

        }

        return ret;

    }

    void add(int x, int d)

    {

        while (x <= n)

        {

            C[x] += d;

            x += lowbit(x);

        }

    }

}bit;

int main()

{

    scanf("%d%d", &n, &m);

    for(int i=;i < m;i++)  scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].k);

    sort(q, q+m);

    bit.init();

    for(int i = ;i < m;i++)

    {

        int l = q[i].l, r = q[i].r, k = q[i].k;

        int num = bit.sum(r) - bit.sum(l-);

        if(num >= k)  continue;   //如果已经满足要求，啥事不管

        for(int j =  r;j >= l;j--)  //从右往左枚举

        {

            if(!vis[j])

            {

                vis[j] = true;

                num++;

                bit.add(j, );

                if(num == k)  break;

            }

        }

    }

    printf("%d\n", bit.sum(n));

    return ;

}

参考链接：

1. https://ac.nowcoder.com/discuss/172020

2. https://www.codetd.com/article/4710306

巴特西

牛客练习赛3 F - 监视任务——贪心&&树状数组

题目

分析

最新文章

热门文章