经典匹配问题0.0

题目链接
题意：找两个不重叠的区间段，每个区间段都有一个价值，两区间长度加起来刚好等于x，并且使得价值最小。区间段个数2e5以内。
类似这种题，就是找两个东西的问题，但是一般的两个for就是超时，一般情况总结下其中一个遍历，另外一个进行二分处理。当样的方法不行，要找他们之间的关系，先进行按一定规律的排序，去寻找可行解。
然后一般时间都是能够降到(nlogn)的。
题解：
参考博客
按端点排序，给左端点标记成比右端点小的类型，可以设置个结构体。
代码体现具体情况

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 2e9+10;
const int N =2e5+7;
struct P{
	ll p,len,cost,type;//p 指的是l或者r len表示长度，type用来表示左端点还是右端点 
	P(){}
	P(ll a,ll b,ll c,ll d){p=a;len=b;cost=c;type=d;
	}
}pa[N*2];
bool cmp(P x,P y)//按端点排序，数值相同则左端点在前 
{
	if(x.p==y.p) return x.type<y.type;
	return x.p<y.p;
}
ll best[N];//长度数值 best[x-pa[i].len] 以及 best[pa[i].len] 
int main()
{
	int n,x,cnt=0;
	ll l,r,w;
	//if(0x3f3f3f>inf) cout<<"YES";//0x3f3f3f3f 比 2e9 小 
	scanf("%d%d",&n,&x);
	for(int i=0;i<n;i++)
	{
		scanf("%lld%lld%lld",&l,&r,&w);
		pa[cnt++]=P(l,r-l+1,w,-1);
		pa[cnt++]=P(r,r-l+1,w,1); 
	}
	sort(pa,pa+cnt,cmp);
	fill(best,best+x+1,inf);
	ll ans=inf;//初始化成最大值 
	for(int i=0;i<cnt;i++)
	{
		if(pa[i].type==-1)//当是左端点时，判断是否在之前有长度x-len的best去更新ans值 
		{
			if(pa[i].len<x)
			{
				ans=min(ans,pa[i].cost+best[x-pa[i].len]);
			}
		}
		else best[pa[i].len]=min(best[pa[i].len],pa[i].cost);//如果不是左端点，是右端点可以更新之前使用过的右端的cost 
	}
	//以上保证了区间不会重叠的问题 
	if(ans>=inf) ans=-1;
	cout<<ans<<endl;
	return 0;
}

/*
利用best数组边添加边判断，
巧妙的将维度降低，
时间的复杂度也巧妙降低
*/