2021qdu省賽選拔 J(貪心都不會QAQ)

題目

題意: 給定n張代金券，每張代金券為一個區間[l,r]，duration即區間大小,r - l + 1，花費為w。找到兩張區間不相交的代金券，滿足duration之和恰好為m，花費之和最小。輸出最小花費或判定無解。

思路: 将每個區間的兩個端點都進數組按照大小排序。而且這裡有個小trick，大小相等優先排左端點。這樣右端點制造的滿足條件的最小值會在左端點計算之前，事實也是如此，因為他倆是相交的。

用數組f維護目前已經周遊完的區間的最小值，f[2] = 1說明前邊有區間長度為2，最小花費為1。

當周遊到左端點: ans = min(f[m-d] + w,ans)

當周遊到右端點: f[d] = min(f[d],w)

時間複雜度: O(nlogn)

代碼:

// Problem: C. Hacker, pack your bags!
// Contest: Codeforces - Codeforces Round #422 (Div. 2)
// URL: https://codeforces.com/problemset/problem/822/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
typedef long long ll;
typedef pair<int,int> PII;
#define mem(a,x) memset(a,x,sizeof(a))
#define fir(i,a,b) for(int i=a;i<=b;++i)
#define int long long
int n,m,k,T;
struct node{
	int x;
	int d;
	int w;
	int type;
	bool operator<(const node&rhs)
	{
		if(x != rhs.x) return x < rhs.x;
		return type < rhs.type;
	}
}a[N];
vector<node> va;
int ans = 2e9+10;
ll f[N]; //區間長度為i的最小
void solve()
{
	for(int i=1;i<=(int)2e5;++i) f[i] = 2e9+1;
	cin>>n>>m;
	for(int i=0;i<n;++i)
	{
	    int x,y,z; cin>>x>>y>>z;
	    int d = y-x+1;
	    if(d >= m) continue;
	    va.push_back({x,d,z,-1});
	    va.push_back({y,d,z,1});
	}
	sort(va.begin(),va.end());
	for(int i=0;i<va.size();++i)
	{
		int type = va[i].type;
		int x = va[i].x;
		int d = va[i].d;
		int w = va[i].w;
		if(type == -1)
		{
		    int t = m - d;
		    if(f[t]==0 || f[t] + w >= ans) continue;
		    ans = min(ans,f[t] + w);
		}
		else
		{
			f[d] = min(f[d],w);
		}
	}
	if(ans > (int)2e9) ans = -1;
	cout<<ans;
}
signed main(void)
{
	int T = 1;
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	// cin>>T;
	while(T--)
	solve();
	return 0;
}