P1578 奶牛浴场

· · 题解

本题解特点

本题解的特点是不需要扫两遍，也不需要考虑浴场左右边界顶着牛场左右边界的情况，极大简化了代码

思路

将左右边界上的每个位置都作为障碍点加进去，共有(W+1)*2个新的点，这样就不需要考虑：

  1. 浴场左右边界正好是牛场左右边界的一部分的情况，因为牛场左右边界上的每个位置都有障碍点，一定会有某次枚举是从边界上的某个点开始的
  2. 没有障碍点的情况

代码量极短，时间复杂度为O((N+2W)^2)，实测最慢的点为400多ms.

如果加上if(a[i].y==a[j].y)break;则可以跳过很多没用的枚举，最慢的点是200多ms

#include <bits/stdc++.h>
using namespace std;
int L,W,ans,n;
struct milk{
    int x,y;
}a[70000+5];
bool cmp(milk A, milk B){
    return A.x < B.x;
}
int main(){
    cin>>L>>W>>n;
    for(int i=0;i< n;++i)cin>>a[i].x>>a[i].y;
    for(int i=0;i<=W;++i)a[n++]={0,i},a[n++]={L,i};//把牛场围栏左右边界上的每个点都加进去 
    sort(a, a+n, cmp);//只需要遍历一次 
    for(int i =0; i < n; ++i)
        for(int j =i+1,up=0,dw=W; j < n; ++j){
            if(a[j].x == a[i].x)continue;
            ans =max(ans,(dw-up)*abs(a[j].x-a[i].x));
            //if(a[j].y==a[i].y)break;//这一行加上可以减少很多没用的枚举
            if(a[j].y>a[i].y)dw = min(dw, a[j].y);
            else             up = max(up, a[j].y);
        }
    printf("%d", ans);
}

以上代码为了保持简洁做了轻微的压行