BZOJ1217:[HNOI2003]消防局的设立
2024-09-01 14:22:06
我对贪心的理解:https://www.cnblogs.com/AKMer/p/9776293.html
题目传送门:https://www.lydsy.com/JudgeOnline/problem.php?id=1217
显然对于树最下面那一层点,肯定都会被父亲上或者祖父上的消防局管理。我们就可以从深度最深的点开始贪心。我们把点按深度从大到小排序,对于当前点如果没有被父亲、祖父、儿子、孙子、兄弟上的消防局管理就应该在这个点的祖父处新建一个消防局,这样显然可以管理更多点。父亲和祖父上有没有消防局很容易判断,儿子和孙子上有没有消防局我们可以在儿子或孙子上建消防局的时候更新父亲或祖父的信息来判断。那么兄弟咋整呢?暴力去枚举的话显然不行。
所以我们开一个数组\(dis\)记录某些神奇的信息。\(dis[i]\)表示到\(i\)号点最近的消防局距离是多少。初始都为\(n\)。每次新建一个消防局都去更新这个点的父亲和祖父的\(dis\),因为比这个点深度更深的显然已经不需要更新了。每次判断兄弟上有没有消防局只需要判断父亲的\(dis\)是不是等于\(1\)就行了。
时间复杂度:\(O(nlogn)\)
空间复杂度:\(O(n)\)
代码如下:
#include <cstdio>
#include <algorithm>
using namespace std;
int n,ans;
int fa[1005],dep[1005],dis[1005],id[1005];
int read() {
int x=0,f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
return x*f;
}
bool cmp(int a,int b) {
return dep[a]>dep[b];
}
int main() {
n=read();
for(int i=2;i<=n;i++) {
id[i]=i,fa[i]=read();
dep[i]=dep[fa[i]]+1,dis[i]=n;
}id[1]=1;dis[1]=dis[0]=n;
sort(id+1,id+n+1,cmp);//按深度排序
for(int i=1;i<=n;i++) {
int u=id[i],f=fa[u],ff=fa[f];
dis[u]=min(dis[u],min(dis[f]+1,dis[ff]+2));//用兄弟或者祖父来跟新自己的dis
if(dis[u]>2) {//如果当前点无人管理,那就在祖父处新建消防局
dis[ff]=0;ans++;int fff=fa[ff],ffff=fa[fff];
dis[fff]=min(dis[fff],1);
dis[ffff]=min(dis[ffff],2);//在祖父的父亲和祖父处更新dis信息
}
}
printf("%d\n",ans);
return 0;
}
最新文章
- The .NET of Tomorrow
- Linux下查看版本号,查看存在的普通用户
- Django框架初入
- Coding源码学习第一部分(AppDelegate.m)
- varchar2_to_blob,应用向数据库更新LOB字段时的超时问题
- Windows7睡眠后自动唤醒
- shell学习记录002-知识点储备
- CSS实现图片变灰色及透明度
- AngularJS学习笔记1——什么是AngularJS?
- FZYZOJ-1578 [NOIP福建夏令营]数列分段
- C# - 数据库存取图片
- Net 项目代码风格
- Java NIO的探究
- Python实现栈
- sql 用临时表时报错 ";Chinese_PRC_90_CI_AI"; 和 ";Chinese_PRC_CI_AS"; 之间的排序规则冲突
- 传入list或map进行首字母大小写转换
- 北京大学Cousera学习笔记--4-计算导论与C语言基础--计算机的基本原理-程序运行的基本原理
- Nodejs使用robot操作鼠标键盘
- Golang Kernel For Jupyter-NoteBook
- Web上传文件的原理及实现
热门文章
- Sumdiv(较难数学题)
- Throwing Dice(概率dp)
- What is MEAN?
- python 数据结构中被忽视的小技巧
- afinal 文件上传、下载、图片加载实例
- 【leetcode刷题笔记】Combination Sum
- 【leetcode刷题笔记】Spiral Matrix II
- POJ 之 Hardwood Species
- Hadoop-HA配置详细步骤
- STL中流相关的输入输出符和get函数彻底总结:cin、cin.get()、cin.getline()、getline()、gets()等函数的用法