Hacker, pack your bags

&题意：

有n条线段(n<=2e5) 每条线段有左端点li，右端点ri，价值cost（1 <= li <= ri <= 2e5, cost <= 1e9)

对于一个给定的x(x <= 2e5)，寻找两个不相交的线段，使它们的长度和恰好为x，并且价值和最小

&题解：

只有2个线段,并且他们的和是定值x.但是还有另外一个条件,他们的区间不相交,这个我们可以通过排序左端点l来实现,当我们排序完l,那么任意一个r在这个l之前的都可以与这条线段相组合,那么可以设一个mi[i]:表示线段长度为i时的最小花费,mi[i]可以通过r是否在这个l之前来更新.

&代码：

#include <cstdio>

#include <bitset>

#include <iostream>

#include <set>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <map>

#include <queue>

#include <vector>

using namespace std;

#define ll long long

#define fo(i,a,b) for(int i=(a);i<=(b);i++)

#define fd(i,a,b) for(int i=(a);i>=(b);i--)

#define cle(a,v) memset(a,(v),sizeof(a))

const int maxn = 2e5 + 7, inf = 2e9 + 9;

int n, x, cnt, mi[maxn];

struct Gro {

	int a, b, co, dur, sta;

} a[maxn << 1];

bool cmp (Gro a, Gro b) {

	return a.a < b.a || a.a == b.a && a.sta > b.sta;

}

int main() {

	freopen("E:1.in", "r", stdin);

	cle(mi, -1);

	scanf("%d%d", &n, &x);

	fo(i, 0, n - 1) {

		int x, y, z;

		scanf("%d%d%d", &x, &y, &z);

		a[cnt++] = Gro{x, y, z, y - x + 1, 1};

		a[cnt++] = Gro{y, x, z, y - x + 1, -1};

	}

	sort(a, a + cnt, cmp);

	int ans = inf;

	fo(i, 0, cnt - 1) {

		// printf("%d %d %d \n", a[i].a, a[i].b, a[i].dur);

		if(a[i].sta == 1) {

			if(a[i].dur < x && mi[x - a[i].dur] != -1) {

				ans = min(ans, mi[x - a[i].dur] + a[i].co);

			}

		}

		else {

			if(a[i].dur < x && (mi[a[i].dur] == -1 || mi[a[i].dur] > a[i].co)) {

				mi[a[i].dur] = a[i].co;

			}

		}

	}

	printf("%d\n", ans == inf ? -1 : ans);

	return 0;

}

2e5

CF822C Hacker, pack your bags!(思维)

Hacker, pack your bags