[USACO09OPEN] Work Scheduling G
依旧糖的要死
题目大意
总共 \(N\) 项工作，每个工作两个参数 \(D_i\)（截至日期） 和 \(P_i\)（所获利润），时间 \(0\) 开始，总共有 \(10^9\) 个时间单位。他目前可以从 \(N\) 项工作中选择要做的工作，任何一个时间单位内只能完成一项工作，每项工作只需要一个时间单位。在截止时间前才能完成第 \(i\) 项工作，问获得的最大总利润是多少？
分析
首先一个相当显然的贪心：直接对着利润排序，优先选择利润较高的工作，赶在截至日期去前做（一个小小的转化，既然时间从 \(0\) 开始，我们不妨将时间整体向后位移一位），因为一件工作显然是越晚做越好，因此从截至日期向前找第一个空闲的日子来做当前工作即可。
然后我们来考虑一下，“向前找第一个空闲的日子”这个操作显然是优化的关键，我们考虑从 \(O(n)\) 优化到 \(O(\log n)\)。
这就是这是一个比较典的线段树上二分问题了，通过记录最小值对线段树递归剪枝，向右封闭区间。
最后可以得到一个总体 \(O(n\log n)\) 的算法（好像贪心部分是可以用并查集做到线性的，但是我不会捏）。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,rt,cnt(0),ans(0);
int num[N];
struct pii{int val,dea;
}a[N];
namespace TREE{struct Node{#define lson t[pos].ls#define rson t[pos].rsint ls,rs,minn;}t[N<<2];void push_up(int pos){t[pos].minn=min(t[lson].minn,t[rson].minn);}void insert(int &pos,int l,int r,int x){if(!pos) pos=++cnt;t[pos].minn=0;if(l==r) return t[pos].minn=1,void();int mid((l+r)>>1);if(x<=mid) insert(lson,l,mid,x);else insert(rson,mid+1,r,x);push_up(pos);}int query(int pos,int l,int r,int ql,int qr){if(t[pos].minn) return 0;if(l==r) return l;int mid((l+r)>>1),x(0);if(mid<qr) x=query(rson,mid+1,r,ql,qr);if(ql<=mid&&(!x)) x=query(lson,l,mid,ql,qr);return x;}
}
signed main(){// freopen("2.in","r",stdin);// freopen("2.in","r",std);ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;++i) cin>>a[i].dea>>a[i].val;sort(a+1,a+n+1,[](const pii A,const pii B){return A.val>B.val;});for(int i=1;i<=n;++i){int y=TREE::query(rt,1,n,1,a[i].dea);if(!y) continue;ans+=a[i].val;TREE::insert(rt,1,n,y);}cout<<ans<<endl;
}
/*
3
2 10
1 5
1 7
*/
后记：记得不管什么情况下都要把 warning 削干净了，本地测评环境往往和测评机不一样，小心 \(Linux\) 出锅。