给你一张地图和一个范围，地图上有某种元素若干。目标是找到地图中范围内包含这一元素最多的点。
举例子就是给你一个256*256格子的地图，然后范围是5*5，元素是人，想要找到在这个范围内，人数最多的点。
如果地图的规模是O(n*m)， 人的数量是O(k)， 范围的规模是O(L)， 首先用O(k)的时间复杂度读人的位置是必须的。 正常的思路是用二维数组前缀和求解， 时间复杂度是O(nm)级别。 还有一种思路是读入每个人的位置时按照圈人范围更新这个点周围的点的值， 顺便记录最优答案， （也就是开个数组， 按圈人范围将这个点周围的下标自增1， 同时记录最大的值）， 这样时间复杂度是O(kL)级别的。 可以根据数据特点权衡这两个方法， 大致比较一下nm 与 kL 就可以。
格子的长宽都是1，范围不一定是正方形，也可能是圆形，圆形的距离为5
那就得从0-251 开始在5*5得格子里循环找 就完事了。
圆形状范围怎么圈
圆形的直径为5，说的不好不要介意啊
但是你这个用⚪圈出来的。一个单位要怎么算
说是格子其实是一个点，一个点于它上下左右的相邻的点的距离是1，跟左上，右上，左下，右下的距离是1.414，这下你明白了吧
问题就在数学建模上面...编程倒是不是很难...我还是没明白...你要怎么建平面直角坐标系
以左下角为0,0点
问题是,圆 圈出来的这块面积.是算圈里整的，还是只要圈到格子的边边就算圈到了。
这样的情况下，中间只有两格。但是圆描边了。算不算在这个范围内
圆心是不是任意的
你还是没有弄清楚我的问题，我的问题是点跟点之间的，不是格子之间的，举例子就是半径为1的圆的圆心在1,1这个点，那么2,1的人就包含在这个范围内，相对的2,2的就不在这个范围内。
圆心可不可以是0.5,0.5这样子
不能必须是int类型
那这就非常简单了啊...建一个二维数组... 然后用一个动圆(圆心必须在点上,且直径为5)去扫一下不就好了。
那复杂度就太高了，是n^2的复杂度了
兄弟,复杂度那里高 就一个for循环
兄弟，二维数组，怎么弄都不可能只扫一次啊256*256啊
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication5
{
class Program
{
public static Boolean[][] arrs = new Boolean[256][];
static void Main(string[] args)
{
// 数组初始化
for (int i = 0; i < 256; i++)
{
arrs[i] = new Boolean[256];
}
/// 定义一个圆
///
// 定义一个圆心
int x1 = 0; int y1 = 0;
/// 设定半径
///
double r = 2.5;
// 圆左下角的定点
int x0 = 0;
int y0 = 0;
// 负责检查的动点
int x = x0;
int y = y0;
int count = 0;
// x,y 从左下角 一直移动到右上角
while (!(x == x0 + 5) && !(y == y0 + 5))
{
if (((x - x1) * (x - x1) + (y - y1) * (y - y1) < 2.5 * 2.5))
{
if (arrs[x][y])
{
count++;
}
x++;
if (x == x0 + 5)
{
x = x0;
y++;
}
}
else
{
x++;
if (x == x0 + 5)
{
x = x0;
y++;
}
continue;
}
}
}
}
}
然后变一下圆心的位置,和圆心左下角的位置,for循环,把count比较一下 不就完事了。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication5
{
class Program
{
public static Boolean[][] arrs = new Boolean[256][];
static void Main(string[] args)
{
// 数组初始化
for (int i = 0; i < 256; i++)
{
arrs[i] = new Boolean[256];
}
int cx = 3;
int cy = 3;
// 圆心从(3,3)滚动到(253,253)
while (cx != 253 && cy != 253)
{
/// 定义一个圆
///
// 定义一个圆心
int x1 = cx; int y1 = cy;
/// 设定半径
///
double r = 2.5;
// 圆左下角的定点
// 圆半径是2.5 所以要减3吧
int x0 = cx - 3;
int y0 = cy - 3;
// 负责检查的动点
int x = x0;
int y = y0;
int count = 0;
// x,y 从左下角 一直移动到右上角
while (!(x == x0 + 5) && !(y == y0 + 5))
{
if (((x - x1) * (x - x1) + (y - y1) * (y - y1) < 2.5 * 2.5))
{
if (x <= 256 && y <= 256 && x>=0 && y>=0)
{
if (arrs[x][y])
{
count++;
}
}
x++;
if (x == x0 + 5)
{
x = x0;
y++;
}
}
else
{
x++;
if (x == x0 + 5)
{
x = x0;
y++;
}
continue;
}
}
cx++;
if (cx == 253)
{
cx = 0;
cy++;
}
}
}
}
}
形状也很好处理的， 第一种方法推个用二维前缀和求和的式子， 第二种方法直接按形状枚举就完了。