PowerOj 2392(树状数组 or CDQ分治)
大家都知道,如果晚上睡不着觉的话,数星星是一种很好的可以帮助入眠的方式。 那现在我们就来数星星吧。 但是对于大家来说,单纯的数星星肯定是太简单了,所以,我们改变一下数星星的方式。 首先,所有的星星都是位于二维坐标平面上的。 其次,我们约定:每一个星星有一个 value 值,这个 value 值等于 x 值不超过其 x 值并且 y 值不超过其 y 值(也即是在坐标平面上位于其左下方(包含边界))的星星的个数。 比如,在上面这个图片中,5号星星的 value ==3(因为1,2,4号星星位于5号星星的左下方)。 2号和4号星星的 value==1。 1号星星的 value==0。 3号星星的 value==2。 所以,在这幅图中,只有一颗星星的 value==0,两颗星星的 value==1,一颗星星的 value==2,一颗星星的 value==3。 现在的任务是:输出每一个 value 所对应的星星的数量。。 Input 多组数据 第一行输入一个数 N(表示所有的星星的数量) (1 <= N <= 10000) 接下来的 N 行,每行一对x,y,表示一个星星的坐标 (1<= X,Y <= 10000 ) 星星的坐标不重复。 Output 每组数据输出 N 行 第一行输出value==0 的星星的数量 第二行输出value==1 的星星的数量 .......... 第N行输出value==N-1 的星星的数量 Sample Input 5 1 1 5 1 7 1 3 3 5 5 Sample Output 1 2 1 1
发布日期:2021-06-29 21:40:22
浏览次数:3
分类:技术文章
本文共 1974 字,大约阅读时间需要 6 分钟。
0
数据范围不大情况下用树状数组快一点,查询log(n)。
代码:
CDQ:先按照x排序,分治,递归处理左右区间,然后对y进行排序,记录左边区间内比y小的数的个数,边找边统计答案。
#include树状数组:树状数组里面处理的是区间内出现次数总和。using namespace std;const int maxn=1e4+5;int ans[maxn],cnt[maxn];struct node{ int x; int y; int id; node(){} node(int x,int y,int id):x(x),y(y),id(id){}}a[maxn];bool cmp(node m,node n){ if(m.x==n.x) return m.y >1; CDQ(l,mid); CDQ(mid+1,r); sort(l+a,a+mid+1,cmp1); sort(a+mid+1,a+r+1,cmp1); int left=l; for(int right =mid+1;right<=r;right++) { while(left<=mid&&a[left].y<=a[right].y) left++; cnt[a[right].id]+=left-l; }}int main(){ int n; while(scanf("%d",&n)!=EOF) { memset(a,0,sizeof(a)); memset(cnt,0,sizeof(cnt)); memset(ans,0,sizeof(ans)); for(int i=1;i<=n;i++) { scanf("%d%d",&a[i].x,&a[i].y); a[i].id=i; } sort(a+1,a+1+n,cmp); CDQ(1,n); for(int i=1;i<=n;i++) { ans[cnt[i]]++; } for(int i=0;i<=n-1;i++) { printf("%d\n",ans[i]); } } return 0;}
#includeusing namespace std;const int maxn=1e4+5;int ans[maxn],num[maxn];struct node{ int x; int y;}a[maxn];bool cmp(node a,node b){ if(a.x==b.x) return a.y
转载地址:https://dh-butterfly.blog.csdn.net/article/details/77162323 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年04月15日 21时03分15秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
MATLAB指定路径保存图片方法
2019-04-30
Python一键获取微信推送封面图
2019-04-30
油猴脚本:微信推送浏览功能拓展
2019-04-30
JavaScript DOM对象操作详解
2019-04-30
JavaScript 表单操作与MD5加密
2019-04-30
jQuery 选择器与鼠标事件详解(附实例)
2019-04-30
Mcmod模组下载脚本
2019-04-30
intelliJ IDEA配置html文件在浏览器打开的快捷键
2019-04-30
(Ver 0.5)油猴脚本:微信推送浏览功能拓展
2019-04-30
JavaScript 点击文字复制到剪切板
2021-07-03
(Ver 1.0)油猴脚本:微信推送浏览功能拓展
2021-07-03
大数据技术之Hadoop(入门)概述、运行环境搭建、运行模式
2021-07-03
大数据技术之Hadoop(HDFS)概述、Shell操作、API操作、读写流程、工作机制
2021-07-03
大数据技术之Hadoop(MapReduce)概述、序列化
2021-07-03
ubuntu 18.04 编译octomap
2021-07-03
C++ Core Guidelines 笔记01
2021-07-03
C++ Core Guideline 笔记02
2021-07-03
C++ Core Guideline 笔记03
2021-07-03
C++11 C++14 C++17 move semantics
2021-07-03
octomap 简单自定义 OcTree
2021-07-03