为什么大家都是从左到右和从右到左扫两边,我只扫了一遍还是ac了
  • 板块P1578 奶牛浴场
  • 楼主Hpnes
  • 当前回复1
  • 已保存回复1
  • 发布时间2020/7/8 00:41
  • 上次更新2023/11/6 23:28:53
查看原帖
为什么大家都是从左到右和从右到左扫两边,我只扫了一遍还是ac了
214197
Hpnes楼主2020/7/8 00:41

我代码把从右向左扫描的部分注释掉了,但是还是ac了,为啥呀。

我又把了别人的代码删掉从右向左,结果wa了。 现在我不太懂为什么要两个方向都扫一遍了。。

#include<bits/stdc++.h>
using namespace std;
//#define int long long
const int N=3e4+5;
struct Node{
    int x,y;
}a[N];
bool cmp(Node a,Node b){//按横坐标从小到大排序
    if(a.x!=b.x)return a.x<b.x;
    return a.y<b.y;
}
bool cmp2(Node a,Node b){//按纵坐标从小到大排序
    return a.y<b.y;
}
signed main(){
    int R,C;
    scanf("%d%d",&R,&C);
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].x,&a[i].y);
    }
    //将整个大矩形的四个端点加入,视为障碍点
    a[++n]={0,0};//
    a[++n]={0,C};
    a[++n]={R,0};
    a[++n]={R,C};
    //
    sort(a+1,a+1+n,cmp);
    //左上角为(0,0),右下角为(R,C)
    int ans=0;
    for(int i=1;i<=n;i++){//枚举一个边界
        int up=C,down=0;
        for(int j=i+1;j<=n;j++){//从左往右枚举右边界
            ans=max(ans,(a[j].x-a[i].x)*(up-down));
            if(a[j].y>a[i].y)up=min(up,a[j].y);
            else down=max(down,a[j].y);
        }
    }
//    for(int i=1;i<=n;i++){
//        int up=C,down=0;
//        for(int j=i-1;j>=1;j--){//从右往左枚举左边界
//            ans=max(ans,(a[i].x-a[j].x)*(up-down));
//            if(a[j].y>a[i].y)up=min(up,a[j].y);
//            else down=max(down,a[j].y);
//        }
//    }
    sort(a+1,a+1+n,cmp2);
    for(int i=2;i<=n;i++){
        ans=max(ans,(a[i].y-a[i-1].y)*C);
    }
    printf("%d\n",ans);
    return 0;
}
/*


*/

2020/7/8 00:41
加载中...