- 浏览: 198261 次
- 性别:
- 来自: 武汉
-
文章分类
- 全部博客 (137)
- c++ (74)
- c++,算法,回溯 (2)
- DP问题。 (9)
- DP问题,0/1背包问题 (3)
- 数学问题 (6)
- 贪心算法 (10)
- 排序 (16)
- 数据结构 (7)
- 容器 (2)
- 模拟问题 (2)
- 水题 (8)
- 并查集 (3)
- 非技术 (2)
- 素数问题 (1)
- DFS (3)
- 二叉树 (1)
- 递归 (1)
- 图论 (5)
- 最小生成树 (5)
- 最短路径 (6)
- bell_flaod算法 (2)
- hash (3)
- 二分查找 (1)
- 搜索 (5)
- BFS (5)
- STL (3)
- 字符串hash (1)
- 拓扑排序 (1)
- 字典树 (4)
- 哈弗曼树 (1)
- KMP (7)
- 线段树 (9)
- 树状数组 (6)
- 全排列 (2)
- DP问题 (2)
- LCS (1)
- 最长不下降子序列 (2)
- 面试经验 (3)
题意:有一只猴子喜欢吃香蕉,但他只能在相邻的两棵香蕉树之间行动,如果两棵树是在横方向或竖方向相邻的,那么这就组成一个区域,这个区域内猴子可以随意走动,有人可以把k个区域连接起来,从而使猴子在这k个区域内随意行动,问猴子最多可以在多少棵树内走动?给定n个树的坐标,和k。
思路:由于是区域相连接,所以可以想到用并查集这个数据结构进行操作。使用并查集来对这n个点进行操作,最后选出前k个最大的根节点相加即可。里面主要涉及到排序的问题,我这里采取的一致是STL算法模板中提供的qsort算法,下面关于qsort算法有一点小小的感受。int cmp(const void *a,const void *b);(红色字体是其固定模式,必须这样写,黑色的则是自己随便起的名字)(其函数体详见后面),并且规定这个函数只能返回int型值。以前没有注意到这个问题,就随便操作,导致很多问题出现。
下面提供代码:
#include <iostream> using namespace std; struct point { int x,y; int index; }data[16020]; int father[16020]; int rank[16020]; int sum[16020]; int mem[16020]; int cmp(const void *a,const void *b) { return *(int *)b-*(int *)a; } int cmp1(const void *p1,const void *p2)//对point 先x后y排序 { if((*((point*)p1)).x==(*((point*)p2)).x) { return (*((point*)p1)).y-(*((point*)p2)).y; } return (*((point*)p1)).x-(*((point*)p2)).x; } int cmp2(const void *a,const void *b)//先对y再对x排序 { if(((point *)a)->y!=((point *)b)->y) return ((point *)a)->y-((point *)b)->y; return ((point *)a)->x-((point *)b)->x; } void make_set(int x) { father[x]=x; rank[x]=0; sum[x]=1; } int find_set(int x) { if (father[x]!=x) father[x]=find_set(father[x]); return father[x]; } void Union_set(int x,int y) { int rootx=find_set(x); int rooty=find_set(y); if(rootx==rooty)//在一棵树上 return; if(rank[rootx]<rank[rooty])//y所在树高,所以挂到x的根上 { father[rootx]=rooty; sum[rooty]+=sum[rootx];//!!!!!!!!!之前有错误原因在于写作了sum[x]+=sum[y];!!!!!!!! } else if(rank[rootx]>rank[rooty]) //根据rank是为了得到更低的树 !!!!!!!!之前有错误写作if(rank[y]>rank[x])反了两次!!!!! { father[rooty]=rootx; sum[rootx]+=sum[rooty];//!!!!!之前一直WA原因是写成sum[y]+=sum[x]!!!!!!所以注意这里所有的都是用的rootx,rooty } else { rank[y]++; father[rootx]=rooty; sum[rooty]+=sum[rootx]; } } int main() { int n,k; cin>>n>>k; int i; for (i=0;i<n;i++) { cin>>data[i].x>>data[i].y; data[i].index=i; make_set(data[i].index); } qsort(data,n,sizeof(point),cmp1); for (i=0;i<n-1;i++) { if ((data[i].x==data[i+1].x)&&(data[i+1].y-data[i].y==1)) Union_set(data[i].index,data[i+1].index); } qsort(data,n,sizeof(point),cmp2); for (i=0;i<n-1;i++) { if ((data[i].y==data[i+1].y)&&(data[i+1].x-data[i].x==1)) Union_set(data[i].index,data[i+1].index); } int begin=0; for (i=0;i<n;i++) { if(father[i]==i) mem[begin++]=sum[i]; } int ans=0; qsort(mem,begin,sizeof(int),cmp); for (i=0;i<k;i++) ans+=mem[i]; cout<<ans<<endl; return 0; }
<!--EndFragment-->
发表评论
-
虚函数、纯虚函数、虚基类、抽象类、虚函数继承、虚继承
2013-08-29 14:34 796虚函数:虚函数是C++中用于实现多态(polymorphis ... -
排序算法总结
2013-05-17 11:00 800选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法, ... -
poj 3122
2012-12-11 19:51 829题意:作者要开一个生日party,他现在拥有n块高度都为1 ... -
poj 3273
2012-12-11 16:49 958题意:给你天数n,和每天需要花的钱,让你把这些天分成m份(每份 ... -
字典树学习材料
2012-05-30 14:29 943字典树,又称单词查找树,Trie树,是一种树形结构,典型应 ... -
poj 1159
2012-05-28 19:08 1413题目大意:给你一段字符串,让你求出在中间最少加入几个字符 ... -
poj 3176
2012-05-28 14:47 992大致题意: 输入一个n层的三角形,第i层有i个数,求从第 ... -
poj 1260
2012-05-28 09:54 1583题意解释: 有n个等级的珠宝,等级依次升高,等级越高价钱越高 ... -
poj 1836
2012-05-28 09:22 2686是POJ2533的扩展题。题意不难,令到原队列 ... -
poj 2533
2012-05-26 15:36 1223在做这道题目之前,首先让我们了解一下什么是LIS算法,LIS俗 ... -
poj 3267
2012-05-26 09:43 784从程序可以看出,第i个位置到L所删除的字符数,总是先取最坏情况 ... -
poj 1276
2012-05-25 16:20 2369题意: 这道题的意思是给你一堆钱,各种面值的都有,比 ... -
poj 1094
2012-05-25 13:54 1074题意:给出字母个数,和有限个有序对(a<b)求出能确定字 ... -
poj 3393
2012-05-23 17:00 1236大致题意: 科普文一篇,文章80%都是无用信息,因为 ... -
poj 3007
2012-05-14 10:21 965大致题意: 给定一个字符串,从任意位置把它切为两半, ... -
poj 3096
2012-05-10 21:09 979题意: 定义D-pairs表示取字符串s中相距为D的两个字母 ... -
poj 1426
2012-04-26 20:11 2133大致题意: 给出一个整数n,(1 <= n <= ... -
poj 1797
2012-04-24 15:05 1606题目大意是就是何处一个图,n个顶点和m条边,每个边都有最大承载 ... -
poj 1338
2012-04-23 10:20 1235题意:题目意思是求由2,3,5的乘积组成的数从大到小排列,从1 ... -
poj 2021
2012-04-19 15:00 912题意:Ted今年100岁,给出n对他家族的关系:“父 ...
相关推荐
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
* 图的深度优先遍历和广度优先遍历:图的深度优先遍历和广度优先遍历是指遍历图的两种方式,如 poj1860、poj3259、poj1062、poj2253、poj1125、poj2240。 * 最短路径算法:最短路径算法是指计算图中两点之间的最短...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
* 较为复杂的动态规划:例如 poj1191、poj1054、poj3280、poj2029、poj2948、poj1925、poj3034。 数学 1. 组合数学: * 加法原理和乘法原理。 * 排列组合。 * 递推关系:例如 poj3252、poj1850、poj1019、poj...
北大POJ1159-Palindrome 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj分类poj分类poj分类poj分类
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
北大POJ2002-Squares 解题报告+AC代码
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类是指在 POJ(Peking University Online Judge)平台上面的编程题目的分类,这些题目涵盖了多种编程领域,包括枚举、递归、模拟、数制转换、高精度计算、简单计算、字符串处理和...
poj 1001答案
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
POJ2968代码有用,欢迎下载,POJ代码