BZOJ_3476_[Usaco2014 Mar]The Lazy Cow_扫描线+切比雪夫距离
BZOJ_3476_[Usaco2014 Mar]The Lazy Cow_扫描线+切比雪夫距离
Description
It's a hot summer day, and Bessie the cow is feeling quite lazy. She wants to locate herself at a position in her field so that she can reach as much delicious grass as possible within only a short distance. There are N patches of grass (1 <= N <= 100,000) in Bessie's field. The ith such patch contains g_i units of grass (1 <= g_i <= 10,000) and is located at a distinct point (x_i, y_i) in the field (0 <= x_i, y_i <= 1,000,000). Bessie would like to choose a point in the field as her initial location (possibly the same point as a patch of grass, and possibly even a point with non-integer coordinates) so that a maximum amount of grass is within a distance of K steps from this location (1 <= K <= 2,000,000). When Bessie takes a step, she moves 1 unit north, south, east, or west of her current position. For example, to move from (0,0) to (3,2), this requires 5 total steps. Bessie does not need to take integer-sized steps -- for example, 1 total step could be divided up as half a unit north and half a unit east. Please help Bessie determine the maximum amount of grass she can reach, if she chooses the best possible initial location.
在二维平面有N个点。每个点都有个权值。
现在希望你选择某个点,如果其它点到这个点的距离不超过K。
则牛就可以吃到这个点的东西。
现在希望吃到的东西的权值越大越好。请求出这个值来。
Input
* Line 1: The integers N and K.
* Lines 2..1+N: Line i+1 describes the ith patch of grass using 3 integers: g_i, x_i, y_i.
Output
* Line 1: The maximum amount of grass Bessie can reach within K steps, if she locates herself at the best possible initial position.
Sample Input
7 8 6
3 0 0
4 6 0
1 4 2
INPUT DETAILS: Bessie is willing to take at most 3 steps from her
initial position. There are 4 patches of grass. The first contains 7
units of grass and is located at position (8,6), and so on.
Sample Output
8
曼哈炖距离在处理‘距离不超过K’这种问题时比较麻烦,因为要维护一个斜45度的正方形。
于是逆时针旋转45度,使得x->x-y,y->x+y,转化为切比雪夫距离就只需要维护一个正方形。
然后就是扫描线的套路,设f[i]表示左下的纵坐标为i时的答案,用线段树维护y轴的f值。
每次相当于区间加和全局最大值。
注意这里y的范围是[0,2000000],空间要开够。
代码:
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 2000050
#define inf 2000000
#define ls p<<1
#define rs p<<1|1
struct Point {
int x,y,v;
bool operator < (const Point &p) const {
return x<p.x;
}
}a[100050];
int n,t[N<<2],add[N<<2],K;
void pushdown(int p) {
if(add[p]) {
int d=add[p]; add[ls]+=d; add[rs]+=d;
t[ls]+=d; t[rs]+=d; add[p]=0;
}
}
void update(int l,int r,int x,int y,int v,int p) {
if(x<=l&&y>=r) {
t[p]+=v; add[p]+=v; return ;
}
pushdown(p);
int mid=(l+r)>>1;
if(x<=mid) update(l,mid,x,y,v,ls);
if(y>mid) update(mid+1,r,x,y,v,rs);
t[p]=max(t[ls],t[rs]);
}
int main() {
scanf("%d%d",&n,&K); K<<=1;
int i,x,y;
for(i=1;i<=n;i++) {
scanf("%d%d%d",&a[i].v,&x,&y); a[i].x=x-y; a[i].y=x+y;
}
sort(a+1,a+n+1);
int ans=0;
int j=1;
for(i=1;i<=n;i++) {
while(a[i].x-a[j].x>K) update(0,inf,max(0,a[j].y-K),a[j].y,-a[j].v,1),j++;
update(0,inf,max(0,a[i].y-K),a[i].y,a[i].v,1);
if(ans<t[1]) ans=t[1];
}
printf("%d\n",ans);
}
最新文章
- JAVA语言搭建白盒静态代码、黑盒网站插件式自动化安全审计平台
- Sublime Text 2 增加python版本
- 数据库中Schema和Database有什么区别
- PHP的PSR系列规范都有啥内容
- 【bzoj1828】[Usaco2010 Mar]
- 【python】and和or的用法
- NGUI无限滑动
- mysql 关联条件与查询(过滤)条件
- jQuery选择器之可见性过滤选择器Demo
- Linux 的启动流程-阮一峰
- [转]Android 使用Scroller实现绚丽的ListView左右滑动删除Item效果
- 201521123028 《java程序设计》 第7周学习总结
- 4.熟悉App Inventor 2编程界面
- Word操作——通配符
- 在IDEA中配置Spring的XML装配
- Beaglebone板子修改usb连接时的默认IP192.168.0.2
- Chrome V8引擎的一点认识
- easyui学习笔记10—手风琴格子始终展开和多个格子展开
- 【Python3的命名空间与作用域,闭包函数,装饰器】
- Symmetrical Network Acceleration with EBS 12
热门文章
- BestCoder Round #90 A+B题解!
- java邮件工具类【最终版】
- linux rdesktop远程Win7老是提示密码错误问题解决
- centos 6.5 yum安装lnmp
- BZOJ1592: [Usaco2008 Feb]Making the Grade 路面修整
- 七天从零基础学习android(2)--第一个安卓程序
- 重装JDK后Tomcat和Eclipse的配置
- eclipse中安装maven插件
- Linux源代码分析工具-Source Insight
- 矩阵奇异值分解(SVD)