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
using namespace std;
const int N = 2e5+10;
typedef long long ll;
typedef pair PII;
#define mem(a,x) memset(a,x,sizeof(a))
#define fir(i,a,b) for(int i=a;ix>>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= ans) continue;
		    ans = min(ans,f[t] + w);
		}
		else
		{
			f[d] = min(f[d],w);
		}
	}
	if(ans > (int)2e9) ans = -1;
	coutT;
	while(T--)
	solve();
	return 0;
}