正題

題目鏈接:https://www.luogu.com.cn/problem/P7990

---

題目大意

數軸上有$k$個點是草地，每個草地有不同收益，$m$個點是地方的點，現在你要放置$n$個我方的點，不能和敵方的點重合。

如果一個草地離最近的我方的點距離嚴格小于最近的敵方點距離，那么這個草地被占領。

給出敵方點和草地坐標（保證兩兩不同），求占領草地的最大收益和 。

$1\le n,m,k\le 2\times 10^5,1\le x\le 10^9$

---

解題思路

考慮在兩個敵方點之間我們最多放兩個己方點，又因為敵方點肯定和草地不重合所以放兩個肯定能占領這之間的所有草地。

而且不能放敵方點的限制可以無視因為放敵方點沒有任何收益。

然后我們再考慮如何算出兩個敵方點之間放一個我方點的最大收益。

顯然之間考慮位置很麻煩，我們可以考慮對于一個草地作為最右邊的草地，那么一頭牛能占領的最左邊的草地，這個可以直接用一個雙指針維護。

這樣我們就得出了每一段放一頭/兩頭牛的收益，記為$c_{i,1/2}$。

此時我們考慮暴力貪心開始把所有的$c_{i,1}$放進堆里，每次取出的如果是一個$c_{i,1}$那么把$c_{i,2}?c_{i,1}$再放進堆里做$n$次就可以了。

看起來這個貪心好像是錯的，因為如果$c_{i,2}$遠大于$c_{i,1}$時我們就可能犧牲第一次取小的來取第二次的。

但是實際上我們用在上面那個過程中不難發現，肯定是有$c_{i,1}\ge c_{i,2}?c_{i,1}$的（因為直接放在左右地方牛的旁邊貢獻大的那個位置就至少有一半的收益）。

時間復雜度：$O(n\log n)$

當然我推薦的做法是無腦wqs二分+dp

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define ll long long #define mp(x,y) make_pair(x,y) using namespace std; const ll N=2e5+10; struct node{ll p,t; }a[N]; ll n,m,k,ans,s[N],f[N],w[N],v[N]; priority_queue<pair<ll,ll> > q; bool cmp(node x,node y) {return x.p<y.p;} signed main() {scanf("%lld%lld%lld",&k,&m,&n);for(ll i=1;i<=k;i++)scanf("%lld%lld",&a[i].p,&a[i].t);for(ll i=1;i<=m;i++)scanf("%lld",&f[i]);sort(a+1,a+1+k,cmp);sort(f+1,f+1+m);f[0]=-1e9;f[m+1]=2e9;ll now=1,l=1,las=0,maxs=0;for(ll i=1;i<=k;i++){s[i]=s[i-1]+a[i].t;while(l<=m&&f[l]<a[i].p){w[l]=maxs;v[l]=s[i-1]-s[las];las=i-1;now=i;maxs=0;l++;}ll L=f[l-1],R=f[l];while((a[i].p-a[now].p)*2>=R-L)now++;maxs=max(maxs,s[i]-s[now-1]);}w[l]=maxs;v[l]=s[n]-s[las];for(ll i=0;i<=k+1;i++)q.push(mp(w[i],i));for(ll i=1;i<=n;i++){pair<ll,ll> w=q.top();ans+=w.first;q.pop();if(w.second)q.push(mp(v[w.second]-w.first,0));}printf("%lld\n",ans);return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的P7990-[USACO21DEC]Closest Cow Wins S【堆,贪心】的全部內容，希望文章能夠幫你解決所遇到的問題。

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