P1250 种树（差分约束 / 贪心）

题目描述

一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号成1…N。每个部分为一个单位尺寸大小并最多可种一棵树。每个居民想在门前种些树并指定了三个号码B，E，T。这三个数表示该居民想在B和E之间最少种T棵树。当然，B≤E，居民必须记住在指定区不能种多于区域地块数的树，所以T≤E-B+l。居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。

写一个程序完成以下工作：

输入格式第一行包含数据N，区域的个数(0<N≤30000)；

第二行包含H，房子的数目(0<H≤5000)；

下面的H行描述居民们的需要：B E T，0<B≤E≤30000，T≤E-B+1。

输出格式输出文件只有一行写有树的数目

输入输出样例

思路（差分约束）

其实本题没有什么要多想的，就一些东西要注意：

首先本题让求的是 “最小种树数量”，既然是最小那么我们就要我们就要用 Spfa 跑 “最长路径”（具体为啥可以参考我的理解）。
把所给的（隐藏的和直接给出来的）不等式全部变 “ >= ” 的形式
找出题目上给的（包括题目中隐藏的约束不等式条件找出来）
- 对于输入的不等式条件：假定为： u, v, w ；那么我们可以列出不等式：v - (u-1) >= w,那么我们直接建边 (u - 1) -> v 其权值为 w
- 对于题意中（每个部分为一个单位尺寸大小并最多可种一棵树）的不等式：对于任意一个距离点：u 我们考虑: 0 <= u - (u-1)<= 1,我可以把它变成两个不等式： u - (u-1) >=0 、u - (u-1) <= 1 , 将他们变成 “ >= ”的形式为：u = (u-1) + 0、(u-1) >= u - 1,因此对于一个点u我们可以建了两条边：(u-1) -> u 权值为 0、 u ->(u-1) 权值为 -1…//////////////最后 u的取值范围为 1～n, 所以一次便利所有可能的u，把边都建立上就行了
- 最后别忘了，考虑一下“超级源点”在这一题中为 0。。。。。。

最后贴出 luogu 大佬的思路

题解

#include<iostream>

#include<queue>

#include<algorithm>

#include<cstring>

using namespace std;

#define INF 0x3f3f3f3f

const int maxn = 300005;

const int maxm = 300000;

int m,n;

struct Edge

{

    int v,w,next;

} edge[maxm];

int head[maxn], dis[maxn];

int k = 0;

void Add(int u, int v, int w)

{

    edge[++ k] = (Edge){ v, w, head[u]}; head[u] = k;

}

int Spfa(int s, int e)

{

    int use[maxn] = {0};

    queue<int> q;

    q.push(s);

    int u,v,w;

    while(! q.empty())

    {

        u = q.front(); q.pop();

        use[u] = 0;

        for(int i = head[u]; i != -1; i = edge[i].next)

        {

            v = edge[i].v;

            w = edge[i].w;

            if(dis[v] < dis[u] + w)

            {

                dis[v] = dis[u] + w;

                if(! use[v])

                {

                    q.push(v);

                    use[v] = 1;

                }

            }

        }

    }

    return dis[n];

}

void init()

{

    k = 0;

    for(int i = 0; i <= n; i ++)

        head[i] = -1, dis[i] = -INF;

    dis[0] = 0;

}

int main()

{

    ios::sync_with_stdio(false); cin.tie(0);

    //freopen("T.txt","r",stdin);

    cin >> n >> m;

    init();

    int u,v,w;

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

    {

        cin >> u >> v >> w;

        // v - u >= w

        Add(u-1, v, w);

    }

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

    {

        Add(i-1, i, 0);

        Add(i, i-1,-1);

        // a - b >= 0  a >= b

        // a - b <= 1  b >= a - 1

    }

    cout << Spfa(0, n) << endl;

    return 0;

}

思路（贪心）

这题可以用贪心的思想去考虑这个问题，这里可以部分借鉴：“贪心区间选点问题”的一下思路，，，，我们可以题目所给的区间（u，v）按结束位置v从小到大排序，如果两个区间结束位置相同，那么按照区间开始的位置u 从大到小排序，，，排序完之后，我们考虑要想种植最少的树，那么一棵树就要尽可能多的被多个的区间利用, 而在该区间种树的位置，越靠近区间后面的位置有越大的概率，被下一区间重复利用，而我需要的就是这个重复利用，所以我们在选择中树的时候，应该从后往前植树，对于第一区间，它需要多少棵树就从后往前种多少棵树（其实是做标记），对于以后的区间，缺树我们就中树，不缺就继续遍历下一个空间。。。。

具体步骤

对区间排序
对每个区间依次处理

1.从前往后在当前区间中已经有的树（标记）的数量

2.若树（标记）的数量小于要当前区间要求种植的数量，从后往前种植树（做标记）

 3.输入ans

题解

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxm = 30005;

int n,m;

struct Edge

{

    int u,v,w;

    bool operator <(const Edge& a) const

    {

        if(v == a.v)

            return u > a.u;

        return v < a.v;

    }

} edge[maxm];

int area[maxm];

int main()

{

    ios::sync_with_stdio(false); cin.tie(0);

    //freopen("T.txt","r",stdin);

    cin >> n >> m;

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

        cin >> edge[i].u >> edge[i].v >> edge[i].w;

    sort(edge, edge + m);

    int u,v,w;

    int ans = 0;

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

    {

        int cnt = 0;

        u = edge[i].u; v = edge[i].v; w = edge[i].w;

        //cnt统计已有的标记的个数

        for(int j = u; j <= v; j ++) if(area[j]) cnt ++;

        //在区域的尾部添加数

        for(int j = v; j >= u; j --)

        {

            if(cnt >= w)

                break;

            if(! area[j])

            {

                area[j] = 1;

                cnt ++;

                ans ++;

            }

        }

    }

    cout << ans << endl;

    return 0;

}

巴特西

P1250 种树（差分约束 / 贪心）

思路（差分约束）

题解

思路（贪心）

题解

最新文章

热门文章