题目大意:

给你n个区间,每个区间有一个对应的花费。现在给你一个固定区间长度x,让你找出不重叠的两个区间,他们的区间长度之和为x,并且花费之和最少,问你最少的花费为多少。

分析:

将所有端点的位置进行排序,之后从左到右遍历所有的端点,同时记录之前出现过的每个区间长度所需的最少花费。对于一个端点,如果他是右端点那么更新维护他所对应区间长度的最少花费;如果是左端点,就查一下之前与该区间恰好匹配的区间长度对应的最少花费。同时更新维护得到x长度的最少花费。

代码:

#include<bits/stdc++.h>
using namespace std;
#define maxn 200050
struct qul
{
    int l;int r;int cost;
}a[maxn];

struct point
{
    int m;
    int v;int w;//左端点为0,右端点为1
}b[maxn<<1];

bool cmp1(point a,point b)
{
    if(a.v==b.v)return a.w<b.w;
    return a.v<b.v;
}
int now[maxn]={0};//num[i]表示长度为i的区间的最小花费。
int main()
{
    for(int i=0;i<maxn;i++)
    {
        now[i]=-1;
    }
    int n,x;
    scanf("%d%d",&n,&x);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].cost);
        b[2*i].v=a[i].l;b[2*i].w=0;b[2*i].m=i;
        b[2*i+1].v=a[i].r;b[2*i+1].w=1;b[2*i+1].m=i;
    }
    sort(b,b+n*2,cmp1);
    int ans=-1;
    for(int i=0;i<2*n;i++)
    {
        int t=b[i].m;
        int dis=a[t].r-a[t].l+1;
        if(b[i].w==0)//如果是左端点,就找有没有能匹配的。
        {
            if(x-dis<=0)continue;
            if(now[x-dis]!=-1)
            {
                if(now[x-dis]+a[t].cost<ans||ans==-1)
                {
                    ans=now[x-dis]+a[t].cost;
                }
            }
        }
        if(b[i].w==1)//如果是右端点,就加进去
        {
            if(now[dis]>a[t].cost||now[dis]==-1)now[dis]=a[t].cost;
        }
    }
    printf("%d",ans);
}