T1 ZYB建围墙
题意
给你一个数 \(n\)，求把这 \(n\) 个格子围起来所需的格子数的最小值。
思路
首先，我们尝试把图画出来枚举前面来找出规律。下面这张图里是 1~10 的距离。
好的，我们可以发现。在这个图中 7 这个图内部是六边形。外面一圈绿色的也是六边形。这个时候我们发现数据中有一部分是这么写的：
\[N = 6 \times \frac{k \times (k + 1)}{2} +1 \]于是，我们考虑从这里入手。首先我们再次进行枚举可知，当 \(n = 7\) 时需要 \(12\) 个。当 \(n = 19\) 时需要 \(18\) 个。好的规律已经出来了。当 \(k\) 为整数的时候，我们可以得到当前的答案为 \(6 \times (k + 1)\)。
在这个基础上，我们考虑进行扩展。当现在是一个六边形的时候。设现在的边长为 \(edge\) 那么每扩展 6 层就有能多围出来的量就为：\(e - 1,e，e，e，e，e + 1\)。那么我们就直接枚举接近 \(n\) 的一个满足内外都为六边形的状态。暴力一层层加到 \(n\) 就可以了。这里需要枚举的量很小。所以时间复杂度大致就为：\(O(\sqrt{n})\)。
AC code
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace WYL{
const int INF=1e9;
const int N=1e3+10;
int n,opt=0;
int now=1,y=1,sy,x=6;
int f[N]={0,6,8,9,10,11,12,12,13,14,14,15,15,16,16,17,17,18,18,18,19};
bool check(int k){
for(int i=1;i*i<=INF;i++){
if(n==6*(i*(i+1)/2)+1){
opt=i;
return true;
}
}
return false;
}
signed main(){
cin>>n;
if(check(n)){
cout<<6*(opt+1)<<endl;
return 0;
}else{
while(now+x<=n){
now+=x;
y++;
x+=6;
}
sy=n-now;
// cout<<sy<<" "<<y<<endl;
if(sy==0){
// cout<<"***"<<endl;
cout<<x<<endl;
}else{
// cout<<x<<endl;
cout<<x+(sy/y)+1<<endl;
}
}
return 0;
}
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// freopen("wall.in","r",stdin);
// freopen("wall.out","w",stdout);
WYL::main();
return 0;
}