yasuo

累死我了,代码完全是自己写的,只为给你压缩流的代码👀️ !

#include <iostream>
#include <algorithm>
struct node{int l,r;}a[105];
bool yasuo(node q,node a){return q.l<a.l;}
int main(){
    int q,s,t,num=0;std::cin>>s>>t>>q;
    for(int i=0;i<q;i++) std::cin>>a[i].l>>a[i].r;
    std::sort(a,a+q,yasuo);
    for(int i=0;i<q;i++){
        if(a[i].l>s){std::cout<<"-1";return 0;}
        int maxn=-1;
        for(int j=i;j<q&&a[j].l<=s;j++)
            if(maxn<a[j].r){maxn=a[j].r;i=j;}
        s=maxn;num++;
        if(s>=t) break;} 
    if(s>=t) std::cout<<num;
    else std::cout<<"-1";
    return 0;}

#include<iostream>
#include<algorithm>
using namespace std;
struct line
{
    int l;
    int r;
};
line a[105];
bool cmp(line x,line y)
{
    return x.l<y.l;
}
int main()
{
    int s;
    int t;
    int n;
    cin>>s;
    cin>>t;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].l;
        cin>>a[i].r;
    }
    sort(a+1,a+n+1,cmp);
    int ans;
    ans=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i].l>s)
        {
            cout<<'-';
            cout<<'1';
            return 0;
        }
        int maxn;
        maxn=0;
        for(int j=1;j<=n&&a[j].l<=s;j++)
        {
            maxn=max(a[j].r,maxn);
        }
        s=maxn;
        ans++;
        if(s>=t)
        {
            break;
        }
    }
    if(s>=t)
    {
        cout<<ans;
    }
    else
    {
        cout<<'-';
        cout<<'1';
    }
    return 0;
}

解 压 缩 流

思路：

将输入数据按左端点大小由小到大排序

选择线段时遵循以下几个条件：

如果在未被选择的线段中，左端点最小的线段>已被覆盖的区间的右端点，说明无法覆盖，直接输出-1结束

否则，在剩下的线段中，选取左端点<=已被覆盖区间的右端点且右端点最大的线段

选取玩以后，将已被覆盖的区域的右端点更新到被选择的线段右端点的位置，并将计数变量+1（此时又选择了一条线段）

最后输出时，判断已被覆盖的区间的右端点是否>=整个区间的右端点，如果成立，说明整个区间都被覆盖了，输出计数变量，如果不成立，说明没有被覆盖，输出-1

题解：

#include <iostream>
#include <algorithm>
using namespace std;
struct line
{
    int l, r;
};
line a[105];
bool cmp(line x, line y)
{
    return x.l < y.l;//由小到大排序
}
int main()
{
    int s,t,n;
    cin >> s >> t;
    cin >> n;
    for(int i = 0;i < n;i++)
        cin >> a[i].l >> a[i].r;
    sort(a,a + n,cmp);
    int ans = 0;
    for(int i = 0;i < n;i++)
    {
        if(a[i].l > s)//如果左端点最小的线段>已被覆盖的区间的右端点
        {
            cout << "-1";
            return 0;
        }
        int maxn = 0;
        //求在满足线段左端点<=被覆盖区间左端点的情况下右端点最大是多少
        for(int j = 0;j < n && a[j].l <= s;j++)
        {
            maxn = max(a[j].r,maxn);
        }
        s = maxn;//更新被覆盖区域右端点
        ans++;
        if(s >= t)//如果已经完成覆盖，则不需要继续判断
            break;
    }
    if(s >= t)
        cout << ans;
    else
        cout << "-1";
    return 0;
}

解析：

对于所有左端点小于等于区间左端点的线段，都有可能成为选中的线段，其中最优秀的线段，它必须是右端点最长的线段。

如果选择了这条线段，那新的区间左端点，就是该线段的右端点。

按照这样的规则维护完了所有线段，如果区间左端点大于区间右端点，就证明可以覆盖

题解

#include <iostream>
#include <algorithm>
using namespace std;
struct node
{
    int l, r;
};
node a[105];
bool cmp(node x, node y)
{
    return x.l < y.l;
}
int main()
{
    int s, t, n;
    cin >> s >> t;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].l >> a[i].r;
    }
    sort(a + 1, a + n + 1, cmp);
    int l = s;
    int num = 0;
    for (int i = 1; i <= n; i++)
    {
        // 如果当前线段的左端点在l的右侧则输出 -1，并结束程序
        if (a[i].l > l)
        {
            cout << "-1";
            return 0;
        }
        int maxn = -1;
        // 在左端点都小于或等于 l 的情况下取最大的区间右端点更新 l
        for (int j = i; j <= n && a[j].l <= l; j++)
        {
            if (maxn < a[j].r)
            {
                maxn = a[j].r;
                i = j;
            }
        }
        l = maxn;
        num++; // l 每被更新一次，则表示选择了一个线段，即num ++;
        // 如果当前的 l 已经更新到 r 或者 r 的右侧则跳出
        if (l >= t)
            break;
    }
    if (l >= t)
        cout << num;
    else
        cout << "-1";
    return 0;
}