POJ 3179 Corral the Cows(离散化+二分)

文章目录[x]
  1. 1:题目链接:
  2. 2:题意:
  3. 3:思路:
  4. 4:参考代码:


  • 题目链接:

    http://poj.org/problem?id=3179

    题意:

    有一个最大为10000的图,里面有一些特定的点叫三叶草,每个这样的点可包括往上、右、右上(也就是这是单位矩形的左下角)的一个单位,然后问你如何修护最小边长的正方形栅栏才能完全包括至少单位的三叶草。

    思路:

    • 首先,点的坐标很大,考虑离散化,将坐标离散化后求二维前缀和,由于,所以离散化后最多也只有个点显然可行。这样离散化之后二维前缀和可以记录这个二维区间的三叶草单位数。
    • 其次,考虑到答案具有单调性,也就是如果边长为的正方形可以包括至少单位三叶草,那么比他的的肯定可以,因此可以二分答案求解。
    • 如何?:的时候,我们枚举正方形的左上角,用二分求出它的右下角,然后,判断正方形内是否有大于C的草量。

    参考代码:

    //#include <bits/stdc++.h>
    #include <algorithm>
    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <iostream>
    #include <map>
    #include <queue>
    #include <set>
    #include <stack>
    #include <vector>
    
    using namespace std;
    #define IOS ios::sync_with_stdio(false), cin.tie(0)
    #define endl '\n'
    #define PB push_back
    #define FI first
    #define SE second
    #define m_p(a, b) make_pair(a, b)
    const double pi = acos(-1.0);
    const double eps = 1e-9;
    typedef long long LL;
    const int M = 1e6 + 10;
    const int N = 500 + 10;
    const int mod = 998244353;
    int len, c, n;
    int sum[N << 1][N << 1], temp[N << 1], X[N << 1], Y[N << 1];
    bool check(int x) {
      if (x > temp[len]) {
        return sum[len][len] >= c;
      }
      int pos = upper_bound(temp + 1, temp + len + 1, temp[len] - x + 1) - temp - 1;
      for (int i = 1; i <= pos; i++) {
        for (int j = 1; j <= pos; j++) {
          int nx =
              lower_bound(temp + 1, temp + len + 1, temp[i] + x - 1) - temp - 1;
          int ny =
              lower_bound(temp + 1, temp + len + 1, temp[j] + x - 1) - temp - 1;
          if (sum[nx][ny] - sum[i - 1][ny] - sum[nx][j - 1] + sum[i - 1][j - 1] >=
              c) {
            return true;
          }
        }
      }
      return false;
    }
    void solve() {
      IOS;
      cin >> c >> n;
      for (int i = 1; i <= n; i++) {
        cin >> X[i] >> Y[i];
        temp[++len] = X[i];
        temp[++len] = Y[i];
      }
      sort(temp + 1, temp + len + 1);
      len = unique(temp + 1, temp + len + 1) - temp - 1;
      for (int i = 1; i <= n; i++) {
        int nx = lower_bound(temp + 1, temp + len + 1, X[i]) - temp;
        int ny = lower_bound(temp + 1, temp + len + 1, Y[i]) - temp;
        sum[nx][ny]++;
      }
      temp[++len] = 10005;
      for (int i = 1; i <= len; i++) {
        for (int j = 1; j <= len; j++) {
          sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }
      }
      int l = 1, r = 10000, ans = 0;
      while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
          r = mid - 1;
        } else {
          l = mid + 1;
        }
      }
      cout << r << endl;
    }
    signed main() {
      solve();
      return 0;
    }
    


点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像