合肥网站建设设计公司,wordpress 远程图片,网站建设课程设计百度文库,如何让自己的网站被百度收录正题
题目链接:https://www.luogu.com.cn/problem/P7990 题目大意
数轴上有kkk个点是草地#xff0c;每个草地有不同收益#xff0c;mmm个点是地方的点#xff0c;现在你要放置nnn个我方的点#xff0c;不能和敌方的点重合。
如果一个草地离最近的我方的点距离严格小于最…正题
题目链接:https://www.luogu.com.cn/problem/P7990 题目大意
数轴上有kkk个点是草地每个草地有不同收益mmm个点是地方的点现在你要放置nnn个我方的点不能和敌方的点重合。
如果一个草地离最近的我方的点距离严格小于最近的敌方点距离那么这个草地被占领。
给出敌方点和草地坐标保证两两不同求占领草地的最大收益和 。
1≤n,m,k≤2×105,1≤x≤1091\leq n,m,k\leq 2\times10^5,1\leq x\leq 10^91≤n,m,k≤2×105,1≤x≤109 解题思路
考虑在两个敌方点之间我们最多放两个己方点又因为敌方点肯定和草地不重合所以放两个肯定能占领这之间的所有草地。
而且不能放敌方点的限制可以无视因为放敌方点没有任何收益。
然后我们再考虑如何算出两个敌方点之间放一个我方点的最大收益。
显然之间考虑位置很麻烦我们可以考虑对于一个草地作为最右边的草地那么一头牛能占领的最左边的草地这个可以直接用一个双指针维护。
这样我们就得出了每一段放一头/两头牛的收益记为ci,1/2c_{i,1/2}ci,1/2。
此时我们考虑暴力贪心开始把所有的ci,1c_{i,1}ci,1放进堆里每次取出的如果是一个ci,1c_{i,1}ci,1那么把ci,2−ci,1c_{i,2}-c_{i,1}ci,2−ci,1再放进堆里做nnn次就可以了。
看起来这个贪心好像是错的因为如果ci,2c_{i,2}ci,2远大于ci,1c_{i,1}ci,1时我们就可能牺牲第一次取小的来取第二次的。
但是实际上我们用在上面那个过程中不难发现肯定是有ci,1≥ci,2−ci,1c_{i,1}\geq c_{i,2}-c_{i,1}ci,1≥ci,2−ci,1的因为直接放在左右地方牛的旁边贡献大的那个位置就至少有一半的收益。
时间复杂度O(nlogn)O(n\log n)O(nlogn)
当然我推荐的做法是无脑wqs二分dp code
#includecstdio
#includecstring
#includealgorithm
#includequeue
#define ll long long
#define mp(x,y) make_pair(x,y)
using namespace std;
const ll N2e510;
struct node{ll p,t;
}a[N];
ll n,m,k,ans,s[N],f[N],w[N],v[N];
priority_queuepairll,ll q;
bool cmp(node x,node y)
{return x.py.p;}
signed main()
{scanf(%lld%lld%lld,k,m,n);for(ll i1;ik;i)scanf(%lld%lld,a[i].p,a[i].t);for(ll i1;im;i)scanf(%lld,f[i]);sort(a1,a1k,cmp);sort(f1,f1m);f[0]-1e9;f[m1]2e9;ll now1,l1,las0,maxs0;for(ll i1;ik;i){s[i]s[i-1]a[i].t;while(lmf[l]a[i].p){w[l]maxs;v[l]s[i-1]-s[las];lasi-1;nowi;maxs0;l;}ll Lf[l-1],Rf[l];while((a[i].p-a[now].p)*2R-L)now;maxsmax(maxs,s[i]-s[now-1]);}w[l]maxs;v[l]s[n]-s[las];for(ll i0;ik1;i)q.push(mp(w[i],i));for(ll i1;in;i){pairll,ll wq.top();answ.first;q.pop();if(w.second)q.push(mp(v[w.second]-w.first,0));}printf(%lld\n,ans);return 0;
}
