題目鏈接：點擊查看

題目大意：在數軸上有 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,結束點:1Node(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]升序排序，滿足情況1LL 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; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 1267A Apprentice Learning Trajectory(贪心)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。