首页 > 代码库 > 喵哈哈村的魔法考试 Round #10 (Div.2) B
喵哈哈村的魔法考试 Round #10 (Div.2) B
喵哈哈村与哗啦啦村的大战（二）
发布时间: 2017年3月27日 09:25 时间限制: 1000ms 内存限制: 128M
喵哈哈村因为和哗啦啦村争夺稀有的水晶资源，展开了激烈的战斗。
喵哈哈村与哗啦啦村战斗的地图可以视为一个二维平面。
喵哈哈村准备修建n个防御工事，唯一的要求就是任意两个防御工事之间的距离不得大于R。
在喵哈哈村修建完防御工事之后，哗啦啦村准备选择一个防御工事进行攻击，这个防御工事包括离被攻击防御工事距离小于等于r的防御工事都将被摧毁。其中：R*R=2*r*r。
现在问题来了，请问喵哈哈村怎么修建，才能使得最后被摧毁的建筑最少。
本题包含若干组测试数据。
第一行一个n，表示喵哈哈村要修建的建筑数量。
满足 1<=n<=1e18
输出最少被摧毁的数量。
复制
3
1
题解：我感觉这个题目还是稍微有点难想啊。。。但是想出来了的话就很简单了（废话）。
步骤：先手动模拟一下，第一个点，以半径为R作圆；第二个点一定在圆内，最好的情况就是在圆弧上，再以R为半径作第二个点的圆；然后第三个点在前两个圆的相交的部分内，同样的方法再作第三个圆。
然后我们可以发现这是一个等边三角形啊！找三角形的重心（为什么会想重心？因为我想最优情况应该是重心到三个点的距离都大于安全距离）发现，这个点到三个顶点的距离安全距离，所以不能建立在
重心上，然后我们就会想去尽可能减少被摧毁的建筑物，至少是一个，既然重心的不满足我想要的条件，那么我就想最坏情况就摧毁两个吧，所以把第四个点放在其中一个顶点的尽可能近的位置；接下来的
点都是这样分析，然后就大胆猜想一下这个解应该是(n+2)/3 ... 提交上去，A了， 果然是啊，hhh。 说明做题的时候还是应该相信自己的判断和直觉（当然是在有理论依据的情况下）
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 5 int main(){ 6 ll n; 7 while(cin>>n){ 8 if(n%3==0) cout<<n/3<<endl; 9 else{10 cout<<n/3+1<<endl; 11 }12 } 13 return 0;14 }
喵哈哈村的魔法考试 Round #10 (Div.2) B
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。