模板题目
- www.acwing.com/problem/con…
- 题意是给一些区间，问至少取多少个点，让所有区间里至少有一个点
- 上面这个是区间选点的模板贪心
- 按照右端点排序，可以发现相邻的区间只有三种情况
- L2≤L1≤R1≤R2L_2 \leq L_1 \leq R_1 \leq R_2L2≤L1≤R1≤R2
- L1≤L2≤R1≤R2L_1 \leq L_2 \leq R_1 \leq R_2L1≤L2≤R1≤R2
- L1≤R1≤L2≤R2L_1 \leq R_1 \leq L_2 \leq R_2L1≤R1≤L2≤R2
- 所以得出结论，贪心的想，选点在每个区间最后面开始，能满足最优的情况
题目
思路1————贪心
- 这个就是上面题目的升级版，区间选点不再是一个，而是每个区间需要至少选一定数量的点
- 同理，我们只需要用一个run数组来记录那些时间是被使用过的，然后从后往前补上确实的运行时间即可
代码
cpp
复制代码
class Solution { public: int findMinimumTime(vector<vector<int>>& tasks) { sort(tasks.begin(),tasks.end(),[&](vector<int> &a,vector<int> &b) { return a[1] < b[1]; }); int run[2023] = {0}; int ans = 0; for(auto task:tasks) { int l = task[0],r = task[1],ti = task[2]; int has_run = 0; for(int i = l;i <= r;i ++) { has_run += run[i]; } if(has_run >= ti)continue; for(int i = r;i >= l;i --)if(ti > has_run) { if(!run[i]) { has_run ++; run[i] = 1; ans ++; } } } return ans; } };
思路2————贪心+线段树
- 贪心思路和上面一样
- 只不过用上了线段树的区间修改
- 优先修改右子树
- 找到从未更新过的子线段，然后判断是否数量足够、是否已满、是否被用过，然后再更新答案
- 带入的更新value可以用引用
- 然后返回，判断value > 0
代码
scss
复制代码
class Solution { typedef long long LL; const static int N = 2100; // int n, m; // int w[N]; struct Node { int l, r; LL sum, add;//现实点数，子树有的lazy }tr[N * 4]; void pushup(int u) { tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum; } void pushdown(int u) { auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1]; if (root.add) { //传递懒标记，更新子树 left.add = root.add, left.sum = (LL) (left.r - left.l + 1) * root.add; right.add = root.add, right.sum = (LL) (right.r - right.l + 1) * root.add; //删除父结点懒标记 root.add = 0; } } void build(int u, int l, int r) { if (l == r) tr[u] = {l, r, 0, 0}; else { tr[u] = {l, r}; int mid = l + r >> 1; build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); pushup(u); } } void modify(int u, int l, int r, int &v)//修改的modify { if(tr[u].sum == tr[u].r - tr[u].l + 1)return ; if (l <= tr[u].l && tr[u].r <= r && tr[u].sum == 0 && tr[u].r - tr[u].l + 1 <= v) { v -= tr[u].r - tr[u].l + 1; tr[u].sum = (tr[u].r - tr[u].l + 1); tr[u].add = 1; } else { pushdown(u); int mid = tr[u].l + tr[u].r >> 1; if (r > mid && v > 0) modify(u << 1 | 1, l, r, v); if (l <= mid && v > 0) modify(u << 1, l, r, v); pushup(u); } } LL query(int u, int l, int r) { if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum; pushdown(u); int mid = tr[u].l + tr[u].r >> 1; LL v = 0; if (l <= mid) v = query(u << 1, l, r); if (r > mid) v += query(u << 1 | 1, l, r); return v; } public: int findMinimumTime(vector<vector<int>>& tasks) { sort(tasks.begin(),tasks.end(),[&](vector<int> &a,vector<int> &b) { return a[1] < b[1]; }); build(1,1,tasks.back()[1]); for(auto task:tasks) { int l = task[0],r = task[1],ti = task[2]; ti -= query(1,l,r); if(ti > 0)modify(1,l,r,ti); } return query(1,1,tasks.back()[1]); } };
最后
- 又学到了新的线段树
