当前位置: 首页 > news >正文

Corral the Cows

点评:我认为是一道很不错的题,将很多基础的算法融汇到一起。

题目链接:https://vjudge.net/problem/POJ-3179#author=GPT_zh

题目描述:农夫约翰希望为他的奶牛建造一个围栏。由于奶牛是挑剔的动物,它们要求围栏是正方形的,并且围栏内至少要有 C (1 <= C <= 500) 块三叶草田作为下午的美味佳肴。围栏的边缘必须与 X,Y 轴平行。

FJ 的土地上总共有 N (C <= N <= 500) 块三叶草田,每块的大小为 1 x 1,且其左下角的坐标为整数 X 和 Y,范围在 1..10,000。有时,多个三叶草田会生长在同一位置;这样的田地在输入中会出现两次(或更多次)。如果一块三叶草田完全位于围栏的边界内,则该围栏将围绕该三叶草田。
请帮助 FJ 告诉他包含 C 块三叶草田的最小正方形的边长。

因为这道题涉及的问题很多,所以接下来我们逐步进行分析

离散化引入:
很多人拿到这道题的时候肯定第一想法是二维前缀和。然后再枚举正方形。我当时也是这么想的,因为我刚拿到这道题的时候错把N当作图的大小。每次只需要选定一个起始点然后遍历这个点所在斜线利用双指针求解。
代码如下

点击查看代码
for (int i = 1; i <= 500; i++){lowx = 1;lowy = i;highx = 1;highy = i;while (highx <= 500 && highy <= 500){if (map1[highx][highy] - map1[highx][lowy - 1] - map1[lowx - 1][highy] + map1[lowx - 1][lowy - 1] < n){highx++;highy++;continue;}ans = min(ans, highx - lowx + 1);if (map1[highx][highy] - map1[highx][lowy - 1] - map1[lowx - 1][highy] + map1[lowx - 1][lowy - 1] >= n){lowx++;lowy++;}}}for (int i = 1; i <= 500; i++){lowx = i;lowy = 1;highx = i;highy = 1;while (highx <= 500 && highy <= 500){if (map1[highx][highy] - map1[highx][lowy - 1] - map1[lowx - 1][highy] + map1[lowx - 1][lowy - 1] < n){highx++;highy++;continue;}ans = min(ans, highx - lowx + 1);if (map1[highx][highy] - map1[highx][lowy - 1] - map1[lowx - 1][highy] + map1[lowx - 1][lowy - 1] >= n){lowx++;lowy++;}}}
以上代码时间复杂度为O(max(x,y)^2)只适用于规模x和y的最大值较小的题。

对于这道题来说我们发现给出的点的数量很少但是点之间的跨度又很大,所以我们可以将点给离散化。
代码如下

点击查看代码
cin >> n >> m;vector<int> judgex(10050);vector<int> judgey(10050);vector<int> nx;vector<int> ny;nx.push_back(0);ny.push_back(0);vector<pll> arr(m + 5);for (int i = 1; i <= m; i++){cin >> arr[i].first >> arr[i].second;if (!judgex[arr[i].first]){judgex[arr[i].first] = 1;nx.push_back(arr[i].first);}if (!judgey[arr[i].second]){judgey[arr[i].second] = 1;ny.push_back(arr[i].second);}}vector<vector<int> > arr1(nx.size() + 5, vector<int>(ny.size() + 5));vector<vector<int> > map1(nx.size() + 5, vector<int>(ny.size() + 5));sort(nx.begin() + 1, nx.end());sort(ny.begin() + 1, ny.end());int maxx = max(nx[nx.size() - 1] - nx[1], ny[ny.size() - 1] - ny[1]) + 5;for (int i = 1; i <= m; i++){int x = lower_bound(nx.begin() + 1, nx.end(), arr[i].first) - nx.begin();int y = lower_bound(ny.begin() + 1, ny.end(), arr[i].second) - ny.begin();arr1[x][y]++;}

使用二维前缀和处理二维数组

点击查看代码
for (int i = 1; i < nx.size(); i++){for (int j = 1; j <= ny.size(); j++){map1[i][j] = map1[i - 1][j] + map1[i][j - 1] + arr1[i][j] - map1[i - 1][j - 1];}}

二分答案
因为我们对点进行了离散,对于数组位置(i,j)来说(i+k,j+k)之间可能已经不能组成正方形,所以我们可以选定正方形的起始点和二分答案得到正方形的边长来进行判断该组合是否满足要求。

这里附上完整代码。

点击查看代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>using namespace std;
typedef pair<int, int> pll;int n, m;
bool check(int s, vector<vector<int> > &map, vector<int> &nx, vector<int> &ny)
{for (int i = 1; i < nx.size(); i++){for (int j = 1; j < ny.size(); j++){int x1 = upper_bound(nx.begin() + 1, nx.end(), nx[i] + s - 1) - nx.begin();int y1 = upper_bound(ny.begin() + 1, ny.end(), ny[j] + s - 1) - ny.begin();if (nx[x1] != nx[i] + s - 1)x1--;if (ny[x1] != ny[i] + s - 1)y1--;if (map[x1][y1] - map[x1][j - 1] - map[i - 1][y1] + map[i - 1][j - 1] >= n)return true;}}return false;
}
int binary(int high, vector<vector<int> > &map, vector<int> &nx, vector<int> &ny)
{int low = 0;while (low + 1 != high){int mid = (low + high) / 2;bool ret = check(mid, map, nx, ny);if (ret == true)high = mid;elselow = mid;}return high;
}
void solve()
{cin >> n >> m;vector<int> judgex(10050);vector<int> judgey(10050);vector<int> nx;vector<int> ny;nx.push_back(0);ny.push_back(0);vector<pll> arr(m + 5);for (int i = 1; i <= m; i++){cin >> arr[i].first >> arr[i].second;if (!judgex[arr[i].first]){judgex[arr[i].first] = 1;nx.push_back(arr[i].first);}if (!judgey[arr[i].second]){judgey[arr[i].second] = 1;ny.push_back(arr[i].second);}}vector<vector<int> > arr1(nx.size() + 5, vector<int>(ny.size() + 5));vector<vector<int> > map1(nx.size() + 5, vector<int>(ny.size() + 5));sort(nx.begin() + 1, nx.end());sort(ny.begin() + 1, ny.end());int maxx = max(nx[nx.size() - 1] - nx[1], ny[ny.size() - 1] - ny[1]) + 5;for (int i = 1; i <= m; i++){int x = lower_bound(nx.begin() + 1, nx.end(), arr[i].first) - nx.begin();int y = lower_bound(ny.begin() + 1, ny.end(), arr[i].second) - ny.begin();arr1[x][y]++;}for (int i = 1; i < nx.size(); i++){for (int j = 1; j <= ny.size(); j++){map1[i][j] = map1[i - 1][j] + map1[i][j - 1] + arr1[i][j] - map1[i - 1][j - 1];}}cout << binary(maxx, map1, nx, ny) << endl;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);int t = 1;// cin >> t;while (t--){solve();}return 0;
}

对二分答案进行说明,当我们分到变成K时我们只需要遍历整个二维数组选择起始点,根据K我们可以得到在这个正方形内满足条件的位置在如果该正方形内的草田的数量>=我们想要的数量时,说明K有可能可以缩小,如果对于二维数组的任何位置都不满足条件的话,就是K的值太小

http://www.hskmm.com/?act=detail&tid=15962

相关文章:

  • HarmonyOS 5 通知与语音能力开发实战:从消息推送到智能语音交互
  • HarmonyOS 5 Native与ArkTS混合开发实战:跨语言高性能组件开发
  • 实战:基于HarmonyOS 5构建分布式聊天通讯应用
  • Java-Eclipse使用-多维数组的使用
  • HarmonyOS 5 动画开发实战:从基础动效到高级交互动画
  • HarmonyOS 5 高级动效实战:粒子系统、路径动画与物理动效开发
  • 从范德蒙德矩阵聊开去.
  • HarmonyOS 5 动画性能优化深度解析:从原理到实践
  • HarmonyOS 5 性能优化全攻略:从启动加速到内存管理
  • #字符串执行函数——eval()、exec()和compile()详解
  • HarmonyOS 5 网络编程与数据存储实战:从RESTful API到本地持久化
  • 【光照】[环境光ambient]以UnityURP为例
  • 浅谈当前时代下大学生的就业择业及人生规划
  • 实用指南:玳瑁的嵌入式日记---0923(ARM)
  • 个人博客搭建记录【hexo】
  • 喵喵喵
  • flink不同环境切换 - --
  • ps-填充色
  • HarmonyOS 5分布式数据同步实战:跨设备待办事项应用
  • 深入理解HarmonyOS 5的AVSession:构建跨设备媒体播放器
  • Extjs小例子
  • 匿名函数
  • HarmonyOS资源管理与访问:多分辨率与多语言适配
  • 面试官:为什么没有虚拟线程池?
  • 润生软件简介:以“重构与共生”引领商业未来
  • Python 并发编程
  • 安装pyautogui时与setuptool时冲突报错-module setuptools.dist has no attribute check_test_suite
  • 统计机器学习经典分类算法MATLAB实现
  • 从安装到中文界面,一文带你玩转 DaVinci Resolve 20(零基础也能搞定)
  • 靶场1