Hacker, pack your bags!

​​C - Hacker, pack your bags!​​

謹記​

​sort()​

​函數是\(O(nlog(n))\)的複雜度。

我們對每一個旅途進行周遊，分别找到開始符合條件的那一個旅途，這裡的複雜度可以用二分來降低，但是我們還需要找到一個滿足條件而且權值最大的旅途，如果我們此時進行周遊的話，就是\(O(n^2)\)的複雜度了，那麼怎麼降低其複雜度呢， 這個時候就需要對其進行預處理，在每一個位置找到它滿足條件所需要的最少花費。這裡需要注意一個性質，在旅途的長度相等的情況下，起始日期更晚的旅途也是符合條件的，那麼我們就可以用一個單調棧對其進行維護，然後再在後面周遊的時候\(O(1)\)查詢即可。

代碼：

// Created by CAD on 2020/1/20.
#include <iostream>
#include <vector>
#include <algorithm>
#define inf 0x3f3f3f3f
#define INF 0x7fffffffffffffff
#define ll long long
using namespace std;

const int maxn=2e5+5;
struct node{
    int l,r;
    ll w;
    bool operator <(node &b)
    {
        return l<b.l;
    }
}nod[maxn];
vector<node> v[maxn];
vector<ll> w[maxn];
inline bool judge(node &a,node &b)
{
    return a.l>b.r;
}
int main()
{
    int n,x;    cin>>n>>x;
    ll ans=INF;
    for(int i=1;i<=n;++i)
    {
        int l,r;
        ll c;
        scanf("%d%d%lld",&l,&r,&c);
        nod[i]={l,r,c};
        v[r-l+1].push_back({l,r,c});
    }
    for(int i=1;i<=x;i++)
        sort(v[i].begin(),v[i].end());
    for(int i=1;i<=x;++i)
    {
        if(v[i].empty()) continue;
        w[i].push_back(v[i].back().w);
        for(int j=v[i].size()-2;j>=0;--j)
            w[i].push_back(min(w[i].back(),v[i][j].w));
    }
    for(int i=1;i<=n;++i)
    {
        int k=x-(nod[i].r-nod[i].l+1);
        if(k<1) continue;
        if(v[k].empty()) continue;
        else{
            int l=0,r=int(v[k].size())-1;
            int pos=inf;
            while(l<=r)
            {
                int mid=(l+r)>>1;
                if(judge(v[k][mid],nod[i])) pos=min(pos,mid),r=mid-1;
                else l=mid+1;
            }
            if(pos==inf) continue;
            ll minn=w[k][w[k].size()-pos-1];
            ans=min(ans,nod[i].w+minn);
        }
    }
    if(ans==INF) cout<<-1<<endl;
    else    cout<<ans<<endl;
    return 0;
}