59  懒惰的奶牛
贝西所在的牧场,散落着 N 堆牧草,其中第 i 堆牧草在 ( Xi,Yi ) 的位置,数量有 Ai 个单位。
贝西从家移动到某一堆牧草的时候,只能沿坐标轴朝正北、正东、正西、正南这四个方向移
动,所以计算贝西和牧草间的距离时,应采用“曼哈顿距离”—— (x,y ) 和 (x ,y ) 之间的距离为
|x x | + |y y |。例如贝西的家在 (0.5, 0.3),有一堆牧草在 (3, 2),那么它们之间的距离就是 4.2。
贝西懒得走动,她想请你为它寻找一个最好的位置作为家,这个家附近距离不超过 K 的牧草数
量之和是最大的。注意家的坐标可以不是整数,也可以和某堆牧草的坐标完全重合。
输入格式
• 第一行:两个整数 N K, 1 N 100000, 1 K 2000000
• 第二行到第 N + 1 行:第 i + 1 行有三个整数: Ai, Xi Yi, 1 Ai 10000, 0 Xi,Yi
1000000
输出格式
• 单个整数:表示距离和最佳位置不超过 K 的牧草数量之和
样例输入
4 3
7 8 6
3 0 0
4 6 0
1 4 2
样例输出
8
解释
选择 (3, 0) 为家,位置在 (0, 0), (6, 0) 和
(4, 2) 的牧草距离家都不超过 K
来源
The Lazy Cow, 2014 Mar

【分析】

  曼哈顿距离的话,那个范围,应该是一个边长和坐标轴呈45度角的正方形。

  这样就有点难搞,难统计。

  我们需要把图形“旋转一下”

  旋转的目标是让正方形的边长平行于坐标轴。、

  那么,观察一下可以得到,可以把nx=x-y ny=x+y 这样就旋转过来了(其实改变了正方形的大小的,但没有关系,只要能判断出曼哈顿距离是不是<=k就好)

 然后就很简单了,用线段树维护y纵坐标,然后x横坐标线性扫描。

代码如下:

 #include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
#define Maxn 2000010 struct hp
{
int a,ax,ay;
}tt[Maxn]; struct node
{
int l,r,lc,rc,ans;
int lazy;
}t[*Maxn];int len; int mymin(int x,int y) {return x<y?x:y;}
int mymax(int x,int y) {return x>y?x:y;} bool cmp(hp x,hp y) {return x.ax<y.ax;}
int n,k; int build(int l,int r)
{
int x=++len;
t[x].l=l;t[x].r=r;
t[x].ans=;t[x].lazy=;
if(l!=r)
{
int mid=(l+r)>>;
t[x].lc=build(l,mid);
t[x].rc=build(mid+,r);
}
else t[x].lc=t[x].rc=;
return x;
} void init()
{
scanf("%d%d",&n,&k);
int mx=;
for(int i=;i<=n;i++)
{
scanf("%d%d%d",&tt[i].a,&tt[i].ax,&tt[i].ay);
int xx=tt[i].ax;
tt[i].ax=tt[i].ax-tt[i].ay;tt[i].ay=xx+tt[i].ay+;
mx=mymax(mx,tt[i].ay);
}
sort(tt+,tt++n,cmp);
k=k*;
build(,mx);
} void upd(int x)
{
if(t[x].lazy==) return;
t[x].ans+=t[x].lazy;
int lc=t[x].lc,rc=t[x].rc;
if(t[x].l!=t[x].r)
{
t[lc].lazy+=t[x].lazy;
t[rc].lazy+=t[x].lazy;
}
t[x].lazy=;
} void change(int x,int l,int r,int y)
{
if(t[x].l==l&&t[x].r==r)
{
t[x].lazy+=y;
return;
}
upd(x);
int mid=(t[x].l+t[x].r)>>;
if(r<=mid) change(t[x].lc,l,r,y);
else if(l>mid) change(t[x].rc,l,r,y);
else
{
change(t[x].lc,l,mid,y);
change(t[x].rc,mid+,r,y);
}
upd(t[x].lc);upd(t[x].rc);
t[x].ans=mymax(t[t[x].lc].ans,t[t[x].rc].ans);
} void ffind()
{
int j=,ans=;
for(int i=;i<=n;i++)
{
while(j<n&&tt[j+].ax-tt[i].ax<=k)
{
int nx=mymax(,tt[j+].ay-k);
change(,nx,tt[j+].ay,tt[j+].a);
j++;
}
upd();
ans=mymax(ans,t[].ans);
change(,mymax(,tt[i].ay-k),tt[i].ay,-tt[i].a);
}
printf("%d\n",ans);
} int main()
{
init();
ffind();
return ;
}

bzoj 3476

2016-10-31 11:25:57

最新文章

  1. JAVA 分页工具类及其使用
  2. TLV(类型—长度—值)格式及编码
  3. Oracle 客户端免安装数据库连接
  4. C++标准转换运算符reinterpret_cast
  5. 解决ntfs格式的移动硬盘mount到Linux下时变成只读文件系统的问题
  6. PostgreSQL的 create index concurrently
  7. mysql学习笔记6——用phpmyadmin和在腾讯微云中创建数据库
  8. ubuntu 查本机 ip地址的命令是什么, 详细信息的?
  9. IntelliJ Idea常用的快捷键
  10. Rime 小狼毫 注意事项
  11. mysql 乐观锁实现
  12. B - Red and Black 问题思考
  13. python第六十八天--第十二周作业
  14. ElasticSearch入门 第七篇:分词
  15. 执行nova-manage db sync时出错,提示’Specified key was too long; max key length is 1000 bytes’
  16. 50.EasyGank妹纸App
  17. WinForm界面开发之 启动界面
  18. [转载] MFC绘制动态曲线,用双缓冲绘图技术防闪烁
  19. SpringDaoSupport
  20. (Lua) C++ 寫函式,Lua 呼叫使用

热门文章

  1. Python数据分析笔记目录
  2. (转)Redis使用场景及使用经验
  3. Shell脚本一枚
  4. 全文检索引擎 Solr 部署与基本原理
  5. hibernate(六)一对一映射
  6. UML - 类图
  7. Code First :使用Entity. Framework编程(3) ----转发 收藏
  8. 学习记录 java随机数的产生机制
  9. latex公式中的空格如何表示
  10. JavaScript学习代码整理(二)--函数
  11. PHP文件的上传下载
  12. GridView导出Excel的超好样例
  13. 两款商业拓扑发现软件siteview和ElementSentry的比较
  14. (转)xml节点和元素的关系 .
  15. Oracle的汉字转拼音首字母的函数
  16. JAVA学习第六十二课 — TCP协议练习
  17. 【XSY2771】城市 分治
  18. SWUST OJ(961)
  19. 理解Vuex的辅助函数mapState, mapActions, mapMutations用法
  20. hdu2174 kiki&#39;s game 博弈