BZOJ1720: [Usaco2006 Jan]Corral the Cows 奶牛围栏

此题非常一眼

就是直接分别将 x,y 坐标离散化

并在离散化之后做二维前缀和

二分一下答案，O(n^2) 的 check 即可

注意在 check 当中的二分 x - mid 的过程中，需要去二分 x - mid + 1
因为 STL lower_bound 是找大于等于参数的第一个数
如果直接二分 x - mid ，可能会找到想要的行的下一行

而二分 x - mid + 1 就不会出现这种问题
只需要在二分之后将得到的下标 -1 就行了

复杂度 O(n^2*log1e4)

网上好像有别的做法，懒得写了 = = ...

---

代码：

#include<algorithm> #include<iostream> #include<cstring> #include<cstdlib> #include<cctype> #include<cstdio> using namespace std;const int MAXN = 505;struct POS{int x, y, ux, uy;POS(int X = 0, int Y = 0) {x = X; y = Y;} }pos[MAXN]; int n, c, sizx, sizy, maxp; int unx[MAXN], uny[MAXN], sum[MAXN][MAXN];inline bool chk(int mid) {for(int i = 1; i <= sizx; ++i) {register int dstx = lower_bound(unx + 1, unx + sizx + 1, unx[i] - mid + 1) - unx;for(int j = 1; j <= sizy; ++j) {register int dsty = lower_bound(uny + 1, uny + sizy + 1, uny[j] - mid + 1) - uny;if(sum[i][j] - sum[i][dsty - 1] - sum[dstx - 1][j] + sum[dstx - 1][dsty - 1] >= c) return true;}}return false; } inline void hfs(int l, int r) {int mid = 0, ans = 0;while(l <= r) {mid = ((l + r) >> 1);if(chk(mid)) {ans = mid;r = mid - 1;} else l = mid + 1;}printf("%d\n", ans);return; }int main() {scanf("%d%d", &c, &n);register int xx, yy;for(int i = 1; i <= n; ++i) {scanf("%d%d", &xx, &yy);pos[i] = POS(xx, yy);unx[i] = xx; uny[i] = yy;maxp = max(maxp, max(xx, yy));}sort(unx + 1, unx + n + 2); sort(uny + 1, uny + n + 2);sizx = unique(unx + 1, unx + n + 2) - unx - 1;sizy = unique(uny + 1, uny + n + 2) - uny - 1;for(int i = 1; i <= n; ++i) {pos[i].ux = lower_bound(unx + 1, unx + sizx + 1, pos[i].x) - unx;pos[i].uy = lower_bound(uny + 1, uny + sizy + 1, pos[i].y) - uny;++sum[pos[i].ux][pos[i].uy];}for(int i = 1; i <= sizx; ++i) {for(int j = 1; j <= sizy; ++j) {sum[i][j] = sum[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];}}hfs(1, maxp);return 0; }

转载于:https://www.cnblogs.com/xcysblog/p/9737782.html

总结

以上是生活随笔为你收集整理的BZOJ1720: [Usaco2006 Jan]Corral the Cows 奶牛围栏的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。