题目链接 题意: 现给你n个时间段，在每个时间段内可以花费t时间，获得一把剑。但是一个时间段只能造一把剑。最大化剑总和。 题解： 我们离散化后，遍历一遍区间，维护一个该区间段可以造的剑的集合。其中我们贪心选t最小的剑进行制作，这里可以用multiset。 例如样例1：
2 5 7 1 1 9 2
将区间离散化后，得到数组（这里值得注意的是，我们针对每个区间并不是离散[l, r],而是[l+t-1, r]，因为直到l+t，该区间才真正的可以造剑，这里压入l+t-1，是因为我们要在上一个区间进行处理。）：
2 , 5, 7, 9
这时，我们每个元素开一个vector，记录在遍历到该点时，应该从multiset删去和 添加的t值。在遍历完后，执行操作序列。维护multiset。另外multiset应该记录该能取该最小值的最左的左端点。期间，我们还要维护一个last指针，指向数组最后被覆盖的地方，我们下一次覆盖，就只能从这个点开始了。 下面是ac代码：
#include<cstdio> #include<iostream> #include<cstring> #include <map> #include <queue> #include <set> #include <cstdlib> #include <cmath> #include <algorithm> #include <vector> #include <string> #include <list> #include <bitset> #include <array> #include <cctype> #include <time.h> #pragma GCC optimize(2) void read_f() { freopen("1.in", "r", stdin); freopen("1.out", "w", stdout); } void fast_cin() { std::ios::sync_with_stdio(false); std::cin.tie(); } void run_time() { std::cout << "ESC in : " << clock() * 1000.0 / CLOCKS_PER_SEC << "ms" << std::endl; } template <typename T> bool bacmp(const T & a, const T & b) { return a > b; } template <typename T> bool pecmp(const T & a, const T & b) { return a < b; } #define ll long long #define ull unsigned ll #define _min(x, y) ((x)>(y)?(y):(x)) #define _max(x, y) ((x)>(y)?(x):(y)) #define max3(x, y, z) ( max( (x), max( (y), (z) ) ) ) #define min3(x, y, z) ( min( (x), min( (y), (z) ) ) ) #define pr(x, y) (make_pair((x), (y))) #define pb(x) push_back(x); #define int ll using namespace std; const int N = 1e6 + 5; const int inf = 0x3f3f3f3f; struct Node { ll l, r; ll sum; } su[N]; ll lisan[N], cnt; int getn(int x) { return lower_bound(lisan + 1, lisan + cnt, x) - lisan; } multiset<pair<ll, ll> > q; vector<pair<ll, ll> > v[N]; void add(int x) { for (auto s : v[x]) { if (s.first < 0) q.erase(q.lower_bound(make_pair(-s.first, s.second))); else q.insert(s); } } signed main() { int n; scanf("%lld", &n); for (int i = 1; i <= n; i++) { scanf("%lld%lld%lld", &su[i].l, &su[i].r, &su[i].sum); lisan[++cnt] = su[i].l + su[i].sum-1; lisan[++cnt] = su[i].r; } sort(lisan + 1, lisan + cnt + 1); cnt = unique(lisan + 1, lisan + cnt + 1) - lisan; for (int i = 1; i <= n; i++) { v[getn(su[i].r)].push_back(make_pair(-su[i].sum, su[i].l)); v[getn(su[i].l+su[i].sum-1)].push_back(make_pair(su[i].sum, su[i].l)); } ll la = 0; add(1); ll ans = 0; for (int i = 2; i < cnt; i++) { if (q.size() == 0) { add(i); continue; } ll mil = (*q.begin()).second; ll c = lisan[i]; ll s = max(mil, la); ll len = c - s; ll num; ans += (num = len / (*q.begin()).first); if (num != 0) la = s + num * (*q.begin()).first; add(i); } printf("%lld\n", ans); //run_time(); return 0; }