CF527D
2024-09-01 09:41:50
这题还挺水的,把那个式子稍微变形一下就可以的到xi-wi>=xj+wj,易知:若把每个点看做一条线段,左端点是xi-wi,右端点是xi+wi,就只要求最多的不重叠的线段数就可以了,然后就是乱搞了
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=;
int n;
struct point{int x,w;}a[N];
inline bool cmp(point a,point b){return a.x<b.x;}
struct node{int l,r;}line[N];
inline bool cmp1(node a,node b){return (a.r!=b.r)?(a.r<b.r):(a.l<b.l);}
int main()
{
int i,re=,tmp=-2e9; scanf("%d",&n); for(i=;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].w); sort(a+,a+n+,cmp);
for(i=;i<=n;i++)line[i].l=a[i].x-a[i].w,line[i].r=a[i].x+a[i].w; sort(line+,line+n+,cmp1);
for(i=;i<=n;i++)
{
if(tmp<=line[i].l){tmp=line[i].r; re++;}
}printf("%d\n",re);
}
最新文章
- GitHub实战系列~2.把本地项目提交到github中 2015-12-10
- 【BZOJ 3445】【Usaco2014 Feb】Roadblock
- 构造自己的动画函数:animation,stop功能的实现
- cain使用教程
- 通过viewmodel找到view
- 【CronExpression表达式详解和案例】
- PHP的数据类型总结
- mysql 将时间戳直接转换成日期时间
- 教你如何删除WIN7系统文件以及无法删除的文件
- Spring2.5与JDK8的集成问题
- 将caffe训练时loss的变化曲线用matlab绘制出来
- iOS UITableView UIScrollView 的支持触摸事件
- django 创建一个通用视图
- [置顶] 阅读Oracle官方文档指南
- Exiting the Matrix: Introducing Metasploit&#39;s Hardware Bridge
- Freemarker中如何遍历List
- windows平台上用python 远程线程注入,执行shellcode
- Zookeeper之入门(原理、基础知识)
- 阿里巴巴Java开发规约插件安装使用指南
- (转)MySql 获取所有级联父级或所有级联子级