贪心

区间相关问题

选择不相交区间：

hdu 2037

给定一些区间，选择尽量多的区间，他们互相不交叉。（活动安排问题）

分析：贪心思路是解决活动安排问题的好方案。

按照区间右端点排序，从前往后遍历，给后面的选择留出更多的时间。

#include <bits/stdc++.h>



using namespace std;



struct Node {

    int l,r;

    bool operator < (const Node & rhs) const {

        return r < rhs.r;

    }

}nodes[];



int n;



int main()

{

    while(scanf("%d",&n),n) {

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

        sort(nodes,nodes+n);

        int pos = nodes[].r;



        int ans = ;

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

            if(nodes[i].l>=pos) {

                ans ++;

                pos = nodes[i].r;

            }

        }



        printf("%d\n",ans);



    }

    return ;

}

区间选点

数轴上有n个闭区间，取尽量少的点，使得每个区间内都至少有一个点（pku 3485）

多年前写的代码了~

#include <cstdio>

#include <cmath>

#include <algorithm>



using namespace std;



const int maxn = ;



struct Point {

    double x,y;

} points[maxn];



struct Line {

    double x,y;

} lines[maxn];



bool cmp(Line a,Line b) {

    return a.y < b.y;

}



int main()

{

    double s;

    double d;

    while(~scanf("%lf%lf",&s,&d)) {

        int n;

        scanf("%d",&n);

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

            scanf("%lf%lf",&points[i].x,&points[i].y);

            lines[i].x = points[i].x - sqrt(d*d-points[i].y*points[i].y);

            lines[i].y = points[i].x + sqrt(d*d-points[i].y*points[i].y);

        }



        sort(lines,lines+n,cmp);

        int ans = ;

        double cur = lines[].y;

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

            if(cur>=lines[i].x&&cur<=lines[i].y)

                continue;

            else {

                cur = lines[i].y;

                ans++;

            }

        }

        printf("%d\n",ans);

    }

    return ;

}

区间覆盖问题

数轴上有n个闭区间，选择尽量少的区间去覆盖一条指定线段[s,t]。紫书P233。

扫描线

https://nanti.jisuanke.com/t/17309

题意：有N个站台，每个站台有一些人要上车，上车的人是从某一站台到某一个站台[l,r]区间，有w个人，求最少安排多少个位置。

此题是个大坑货~之前WA了，一直以为我的扫描线写错了，原来是一个排序因子，当时间相等时，先下车再上车。

#include <bits/stdc++.h>



using namespace std;



struct Node {

    int l,w,flag;

    bool operator < (const Node & rhs) const {

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

        else return flag < rhs.flag;

    }

};



int main()

{

    int n;

    while(scanf("%d",&n),n) {



        int l,r,w;

        vector<Node> v;

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

            scanf("%d%d%d",&l,&r,&w);

            v.push_back(Node{l,w,});

            v.push_back(Node{r,w,-});

        }



        sort(v.begin(),v.end());

        int ans = ;

        int tmp = ;

        for(int i = ; i < *n; i++) {

            if(v[i].flag==) {

                tmp += v[i].w;

                ans = max(ans,tmp);

            }

            else {

                tmp -=v[i].w;

            }

        }

        printf("%d\n",ans);

    }

    puts("*");

    return ;

}

扫描法

相比于扫描线还是很简单的，不过还是主要看思路。

uva 11054

题意：有n 个酒庄，有的酒庄需要货，有的酒庄卖货，将一单位的酒从一个地方放到相邻地方耗费1；

求平衡供需关系的最小花费。

对于一号酒庄，他要等于0，那么一定是从2号搬进，或者搬出去。这样就有子问题产生了。

扫描法和普通枚举，在于要维护一些重要的值，简化计算。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {

    int n;

    while(scanf("%d",&n),n) {

        ll ans = ,a,last = ;



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

            cin>>a;

            ans += abs(last);

            last +=a;

        }

        cout<<ans<<endl;

    }

    return ;

}

巴特西

ACM-ICPC(10/23)

贪心

区间相关问题

选择不相交区间：

区间选点

区间覆盖问题

扫描线

扫描法

最新文章

热门文章