P7990-[USACO21DEC]Closest Cow Wins S【堆,贪心】
2024-09-08 10:00:53
正题
题目链接:https://www.luogu.com.cn/problem/P7990
题目大意
数轴上有\(k\)个点是草地,每个草地有不同收益,\(m\)个点是地方的点,现在你要放置\(n\)个我方的点,不能和敌方的点重合。
如果一个草地离最近的我方的点距离严格小于最近的敌方点距离,那么这个草地被占领。
给出敌方点和草地坐标(保证两两不同),求占领草地的最大收益和 。
\(1\leq n,m,k\leq 2\times10^5,1\leq x\leq 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}\geq 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;
}
最新文章
- Centos6.5 设置nfs
- CSS超出部分显示省略号…代码
- Objective C静态代码扫描和代码质量管理 OClint + SonarQube
- glibc strlen delphi pascal
- 使用截图方式将Excel导出为PNG图片的不可行性
- LINUX 添加定时任务
- MyEclipse数据库反向生成实体类
- MongoDB入门学习(一)—— 安装和启动
- Java String 类的 equals 和 ==
- mysql 不能插入中文
- 如何在Eclipse中添加Servlet-api.jar的方法
- 锁对象Lock
- 浏览器将URL变成一个屏幕上显示的网页的过程?
- Unity编辑器扩展-Custom List, displaying data your way
- django rest framework批量上传图片及导入字段
- sqlyog创建数据库表关系图
- python timeit
- Ubuntu 12.04 安装Redis并设置主从复制
- day 26
- django的权限认证:登录和退出。auth模块和@login_required装饰器
热门文章
- 如何在 ShardingSphere 中开发自己的 DistSQL
- Python 3 快速入门 2 —— 流程控制与函数
- Codeforces 997E - Good Subsegments(线段树维护最小值个数+历史最小值个数之和)
- 洛谷 P3266 - [JLOI2015]骗我呢(容斥原理+组合数学)
- UOJ #228 - 基础数据结构练习题(势能线段树+复杂度分析)
- Codeforces 516D - Drazil and Morning Exercise(树的直径+并查集)
- P6973 [NEERC2016]List of Primes
- Python中关于join函数的陷阱?
- Oracle-怎么在表的特定位置增加列
- day12 函数嵌套