题解
查看原帖
题解
1459554
ZAYYY楼主2025/7/1 20:46

这道题的标签是枚举暴力,但是正常暴力会发现测试点超出存储限制了,所用我们不妨换个思路,既然会覆盖,那我们不妨试试贪心的做法

#include<bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	int a[n][4];
	for (int i=0;i<n;i++){
		cin>>a[i][0]>>a[i][1]>>a[i][2]>>a[i][3];
	} 
	int x,y;
	cin>>x>>y;
	int ans=-1;
	for (int i=0;i<n;i++){
		if (x>=a[i][0]&&x<=a[i][0]+a[i][2]&&y>=a[i][1]&&y<=a[i][1]+a[i][3]){
			ans=i+1;
		}
	}
	cout<<ans;
	
}

如上代码,因为是按顺序覆盖,所以我们只要去看每次我们所要找的点有没有被覆盖住就行了,默认答案ans=-1,如果被覆盖了我们就去将ans的值改为i+1,依次类推直至最后一个,其实这也有枚举的思想,只不过把枚举的每个格子改成了我们需要的格子经过第n次覆盖后是什么值,但也可以理解为是一种贪心的思想

2025/7/1 20:46
加载中...