[P1003]对于萌新最佳的暴力优化例子

kingstarjun · 2022-01-27 13:47:15 · 个人记录

这一题有一种很简单的暴力思路，那就是建立一个XY坐标轴，每输入一行数据就将地毯所覆盖的XY范围全部赋值为当前地毯编号。

既然有了这个思路，为什么不尝试着去优化一下？

啊对，很简单，就是先输入a,b,g,k存起来，等到输完要获取的XY坐标的最上面的地毯的时候，创建一个变量存储地毯编号，再遍历一遍所有的a,b,g,k，判断该XY坐标是否在该地毯范围内，是的话直接替换变量为当前地毯编号。

因为地毯上下顺序就是我们输入a,b,g,k的顺序，所以可以直接大胆替换变量。

也就是这种思路。先读。

for(long long i = 0;i <= n;i++){
    cin>>a[i]>>b[i]>>g[i]>>k[i];
}

然后读完XY坐标后遍历一遍。

for(long long i = 0;i <= n;i++){
    if(
    (a[i] <= x && x <= a[i] + g[i] - 1)
    && (b[i] <= y && y <= b[i] + k[i] - 1)
    ) ans = i + 1;
}

甚至还可以DEBUG一下。

cout<<"("<<a[i]<<","<<b[i]<<"),("<<a[i] + g[i] - 1<<","<<b[i] + k[i] - 1<<") WITH ("<<x<<","<<y<<") LOG INX="<<((a[i] <= x && x <= a[i] + g[i] - 1) ? "YES" : "NO")<<" INY="<<((b[i] <= y && y <= b[i] + k[i] - 1) ? "YES" : "NO")<<endl;