题目链接：点击查看
题目大意：在数轴上有 n 个房子，每个房子开放的时间为 [ l[ i ] , r[ i ] ] ，在这个房子里铸一把剑需要 t[ i ] 个连续的时间单位，同一个时间只能在一间房子里铸剑，问最多能铸多少剑
题目分析：对于一个时间戳 t 而言，只有两种情况，我们可以讨论一下：
如果 t 时刻没有房子开放，那么我们选择接下来首先可以铸完剑的房子显然是最优的，注意是首个可以铸完剑的房子，而不是首个可以铸剑的房子，换句话说也就是 l[ i ] + t[ i ] 最小的区间肯定是最优的，而不是 l[ i ] 最小的区间如果 t 时刻有房子开放，那么我们显然在 t[ i ] 最小的房子里铸剑是最优的基于此，这个题目就变成了一个贪心的问题，考虑如何贪心
因为数轴给的区间非常大，但是却非常的稀疏，所以我们并不需要枚举时间戳 t ，而是枚举每个区间的开始点和结束点就可以计算出相应的贡献
具体如何计算呢，因为上面的讨论中也提到了，按照 l[ i ] + t[ i ] 升序排序对于情况 1 来说一定是最优的，对于情况 2 最优的话，我们需要维护一个数据结构，满足在一堆数字中快速查找到其最小值，还必须要快速的插入和删除，因为对于每个端点来说都是需要更新的，所以不难想到用 set 来维护，这样每次插入删除都是 log 级别的，查询更是 O( 1 ) 级别的，又因为时间 t[ i ] 是可以重复出现的，所以我们选择用 multiset 进行维护铸剑时间 t[ i ] 的最小值
剩下的实现就好了， 维护一个 pre 指针代表上一次的结束位置，每次让 pre 贪心在数轴上跳，顺便维护一下贡献就好了，有点小细节可以看代码
代码：
#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<unordered_map> using namespace std; typedef long long LL; typedef unsigned long long ull; const int inf=0x3f3f3f3f; const int N=1e5+100; struct Node { LL pos,t; bool flag;//开始点:0,结束点:1 Node(LL pos,LL t,bool flag):pos(pos),t(t),flag(flag){} bool operator<(const Node& t)const { if(pos!=t.pos) return pos<t.pos; return flag<t.flag; } }; vector<Node>node; multiset<LL>st; int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false); int n; scanf("%d",&n); for(int i=1;i<=n;i++) { LL l,r,t; scanf("%lld%lld%lld",&l,&r,&t); node.push_back(Node(l+t,t,0)); node.push_back(Node(r,t,1)); } sort(node.begin(),node.end());//按照l[i]+t[i]升序排序，满足情况1 LL ans=0,pre=0; for(Node t:node) { if(!st.empty())//如果当前有房子开放 { LL num=(t.pos-pre)/(*st.begin());//贪心计算贡献 ans+=num; pre+=num*(*st.begin()); } if(t.flag)//结束点 st.erase(st.find(t.t)); else//开始点 { if(pre+t.t<=t.pos)//到达开始点l[i]+t[i]时就可以铸一把剑了 { ans++; pre=t.pos; } st.insert(t.t); } } printf("%lld\n",ans); return 0; }
