题解 P3117 【[USACO15JAN]牛的矩形Cow Rectangles】

暴力什么的就算了，~~贪心他不香吗~~

这题其实如果分开想，就三种情况需要讨论：（~~由于不会发图，只能手打~~）

1）

5 . . . . .

4 . . . . .

3 . . . H .

2 . . G . .

1 . H . . .

0 1 2 3 4 5

在这种情况下，下面两个H绝对不在一组（因为他们中有G）

5 . . G . .

4 . . H . .

3 . . . H .

2 . H . . .

1 . G . . .

0 1 2 3 4 5

在这种情况下所有H都能拿，因为G在所有H之上/之下

5 . . H . .

4 . . G . .

3 . . . H .

2 . . . . H

1 . H . . .

0 1 2 3 4 5 在这种情况下下面所有H都能拿，但是上面那个连不了（被G挡住了）

因此，我们只需要对这三种情况进行判断就行了（判断方法见注释）

pp find_pair(int aa, int bb){

  int mini = 1e8,maxi = 0;

  int low = aa, high = bb;

  while(cow[low-1].x==cow[aa].x) {low--;if (low==0)break;}

  while(cow[high-1].x==cow[bb].x) {high++; if (high == 0) break;}

  //这是一个很重要的判断：

  //因为我们在排序的时候有可能遇到x相等的点，这个点并不会被搜索，但是这个点仍然需要判断。在这个时候就需要往前和后搜索x相等的点

  for (int i=low;i<=high;i++){

    if (cow[i].id=='G'){

      if (cow[i].y>max(cow[aa].y,cow[bb].y)) mini = min(mini,cow[i].y);

      else if (cow[i].y<min(cow[aa].y,cow[bb].y)) maxi = max(maxi,cow[i].y);

      else posible = false;

    }

  }//如果这两个点中间有G就进行以下判断：

  //1.如果这个G的y坐标在这两个点的y之上，那么我们将最高值更新

  //2.如果这个G的坐标在y之下，我们将最小值之下，我们更新最小值

  //3.如果这个G在两个坐标中间，那么这两个点必然不可能选（因为无论怎么样连最后G都会在这个范围里）

  return make_pair(mini,maxi);

}

那么问题来了，怎么保证找的G在两个H的中间呢？

~~还用问吗，加个sort就好了~~

*注意事项：在找G的时候，我们要记住如果这个G和H的x坐标相等，在sort的时候未必会在他的范围内。那怎么办？

~~还用问吗，如果x坐标相等就减/加到他不相等为止~~

while(cow[low-1].x==cow[aa].x) {low--;if (low==0)break;}

  while(cow[high-1].x==cow[bb].x) {high++; if (high == 0) break;}

找完G之后，我们对两点之间的所有H进行判断：

如果这个H在上下G的y的范围以内，那么我们更新最大/最小值。（相当于更新高）

pp in_range(int aa, int bb, pp bo){

  int maxi = 0,mini = 1e8;

  for (int i=aa;i<=bb;i++){

    if (cow[i].id!='G'){

      if (between(bo,cow[i].y)){

        maxi = max(maxi,cow[i].y);

        mini = min(mini,cow[i].y);

        temp++;

      }

    }

  }//现在已经找出了在这个点上面最低的G点和下面最高的G点

  //我们在这个范围里面搜索所以的H，更新最高点和最低点（前提是要在G点的范围内）

  return make_pair(maxi,mini);

}

找完之后怎么办？

~~还用问吗，当然找面积啊~~

面积 = 底*高 = (x2-x1)*abs(y2-y1) [因为sort了，所以x2一定>=x1]

if (temp){

        if(temp>breed){

          //如果H的数量大于之前的，直接更新

          breed = temp;

          ans = abs(res.first-res.second)*abs(cow[j].x-cow[i].x);

        }else if (temp==breed) ans = min(ans,abs(res.first-res.second)*abs(cow[j].x-cow[i].x));//否则更新面积（底『x的差』乘高『最高y值和最低y值的差』

      }

由于判断不需要储存，这个程序用500的空间其实就够了（800-KB应该够小了吧）

完整代码如下：

#include <iostream>

#include <algorithm>

#include <math.h>

#include <stdio.h>

using namespace std;

#define pp pair<int,int>

struct node{

  int x,y;

  char id;

}cow[505];

int tot = 0, temp = 0;

int a,b,c; char d;

void add(int aa, int bb, char cc){

  cow[++tot].x = aa;

  cow[tot].y = bb;

  cow[tot].id = cc;

}

bool sorted(node aa, node bb){

  return aa.x<bb.x;

}

bool between(pp aa,int b){

  return aa.first>b && aa.second<b;

}//这个是表示一个数是否在两个数直接

bool posible = true;

pp find_pair(int aa, int bb){

  int mini = 1e8,maxi = 0;

  int low = aa, high = bb;

  while(cow[low-1].x==cow[aa].x) {low--;if (low==0)break;}

  while(cow[high-1].x==cow[bb].x) {high++; if (high == 0) break;}

  //这是一个很重要的判断：

  //因为我们在排序的时候有可能遇到x相等的点，这个点并不会被搜索，但是这个点仍然需要判断。在这个时候就需要往前和后搜索x相等的点

  for (int i=low;i<=high;i++){

    if (cow[i].id=='G'){

      if (cow[i].y>max(cow[aa].y,cow[bb].y)) mini = min(mini,cow[i].y);

      else if (cow[i].y<min(cow[aa].y,cow[bb].y)) maxi = max(maxi,cow[i].y);

      else posible = false;

    }

  }//如果这两个点中间有G就进行以下判断：

  //1.如果这个G的y坐标在这两个点的y之上，那么我们将最高值更新

  //2.如果这个G的坐标在y之下，我们将最小值之下，我们更新最小值

  //3.如果这个G在两个坐标中间，那么这两个点必然不可能选（因为无论怎么样连最后G都会在这个范围里）

  return make_pair(mini,maxi);

}

pp in_range(int aa, int bb, pp bo){

  int maxi = 0,mini = 1e8;

  for (int i=aa;i<=bb;i++){

    bool update = true;

    while(update){

      if (cow[i].id!='G'){

        if (between(bo,cow[i].y)){

          maxi = max(maxi,cow[i].y);

          mini = min(mini,cow[i].y);

          temp++;

        }

      }

    }

  }//现在已经找出了在这个点上面最低的G点和下面最高的G点

  //我们在这个范围里面搜索所以的H，更新最高点和最低点（前提是要在G点的范围内）

  return make_pair(maxi,mini);

}

int main(){

  ios::sync_with_stdio(0);

  cin >> a;

  for (int i=0;i<a;i++){

    cin >> b >> c >> d;

    add(b,c,d);

  }

  int ans = 0, breed = 1;

  sort(cow+1,cow+tot+1,sorted);

  //以上不解释

  for (int i=1;i<=a;i++){

    for (int j=i+breed;j<=a;j++){

      if (cow[i].id=='G'||cow[j].id == 'G') continue;//如果两个点中有G就不需要判断

      posible = true;

      temp = 0;

      pp bounds = find_pair(i,j);//先找G的范围

      if (!posible) continue;

      pp res = in_range(i,j,bounds);//再找H的范围

      if (temp){

        if(temp>breed){

          //如果H的数量大于之前的，直接更新

          breed = temp;

          ans = abs(res.first-res.second)*abs(cow[j].x-cow[i].x);

        }else if (temp==breed) ans = min(ans,abs(res.first-res.second)*abs(cow[j].x-cow[i].x));//否则更新面积（底『x的差』乘高『最高y值和最低y值的差』

      }

    }

  }

  cout << breed << endl << ans;

}

~~你抄任你抄，过得了算我输~~

巴特西

题解 P3117 【[USACO15JAN]牛的矩形Cow Rectangles】

最新文章

热门文章