题解 P6244 【[USACO06OPEN]County Fair Events S】

lingfunny · 2020-03-28 08:54:39 · 题解

题意理解

在一个数轴上，有N条线段，每条线段的起点为T，长度为L，求不相交的线段最多有几条。

算法分析

很简单的贪心。假设我们每次要选择终点为E的线段，当然是要使这个E尽可能小。因为当E最小的时候，你能选择的线段肯定会更多。

代码构造

分析过后，很明显我们要按结束时间从小到大排序。然后记录下上一次选择线段的终点，然后依次对比起点。

代码

#include <iostream>
#include <algorithm>        //sort要用
using namespace std;
struct node{
    int strat;
    int end;                //这是终点，而不是长度
};                          //结点结构体
bool cmp(node x,node y){
    return x.end<y.end;     //按照刚才分析的，要选择终点尽可能小的
}
node f[10005];
int n;
int ans;                    //总共能选择多少条
int end;                    //上一次选择线段的终点
int main(){
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>f[i].strat;
        cin>>f[i].end;
        f[i].end+=f[i].strat;//将长度转化为终点
    }
    sort(f+1,f+n+1,cmp);    //排序
    ans=1;                  //首先肯定要选择重点最近的那个，也就是f[i]
    end=f[1].end;           //终点设置
    for(int i=2;i<=n;++i){
        if(end<=f[i].strat){//如果之前选择的的终点小于等于现在的起点，也就是这两条线段不相交
            ++ans;          //选择了
            end=f[i].end;   //更新end
        }
    }
    cout<<ans;
    return 0;
}

比较简单的一题贪心，稍加思考就可以想出来。

完结撒花✿