首页 > 代码库 > 喵哈哈村的魔法考试 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