贪心

 

区间相关问题

选择不相交区间：

hdu 2037

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

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

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

#include 
     
      ​using namespace std;​struct Node {    int l,r;    bool operator < (const Node & rhs) const {        return r < rhs.r;    }}nodes[105];​int n;​int main(){    while(scanf("%d",&n),n) {        for(int i = 0; i < n; i++) scanf("%d%d",&nodes[i].l,&nodes[i].r);        sort(nodes,nodes+n);        int pos = nodes[0].r;​        int ans = 1;        for(int i = 1; i < n; i++) {            if(nodes[i].l>=pos) {                ans ++;                pos = nodes[i].r;            }        }​        printf("%d\n",ans);​    }    return 0;}
     

 

区间选点

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

多年前写的代码了~

#include 
     
      #include 
      
       #include 
       
        ​using namespace std;​const int maxn = 10005;​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=0; i
        
         =lines[i].x&&cur<=lines[i].y)                continue;            else {                cur = lines[i].y;                ans++;            }        }        printf("%d\n",ans);    }    return 0;}
        
       
      
     

 

 

区间覆盖问题

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

 

扫描线

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

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

#include 
     
      ​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
      
        v;        for(int i = 0; i < n; i++) {            scanf("%d%d%d",&l,&r,&w);            v.push_back(Node{l,w,1});            v.push_back(Node{r,w,-1});        }​        sort(v.begin(),v.end());        int ans = 0;        int tmp = 0;        for(int i = 0; i < 2*n; i++) {            if(v[i].flag==1) {                tmp += v[i].w;                ans = max(ans,tmp);            }            else {                tmp -=v[i].w;            }        }        printf("%d\n",ans);    }    puts("*");    return 0;}
      
     

 

 

扫描法

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

uva 11054

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

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

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

 

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

#include 
     
      using namespace std;typedef long long ll;int main() {    int n;    while(scanf("%d",&n),n) {        ll ans = 0,a,last = 0;​        for(int i = 0; i < n; i++) {            cin>>a;            ans += abs(last);            last +=a;        }        cout<
      
       <