a299 - NOIP2011 Day1.1.铺地毯
題目描述
題目描述了在一個矩形區域內鋪設多張矩形地毯，地毯按照編號從小到大順序鋪設，後鋪的地毯會覆蓋先鋪的地毯。題目要求給定一個點的座標，找出覆蓋該點的最上面的地毯的編號。如果該點沒有被任何地毯覆蓋，則輸出 -1。
解題思路
此題的解題思路是從地毯列表中，按照編號倒序遍歷每一張地毯。對於每一張地毯，判斷給定的點是否在其覆蓋範圍內。如果點在該地毯的覆蓋範圍內，則該地毯的編號就是答案，直接輸出並結束循環。如果遍歷完所有地毯後仍然沒有找到覆蓋該點的地毯，則輸出 -1。
複雜度分析
- 時間複雜度: O(n)，其中 n 是地毯的數量。最壞情況下，需要遍歷所有地毯才能找到答案或確定該點沒有被覆蓋。
- 空間複雜度: O(n)，用於儲存地毯的資訊。
程式碼
#include <stdio.h>
int main(){
int a,x,y;
while(scanf("%d",&a)>0){
int n[a][4],ans=-1;
for(int i=0;i<a;i++)
scanf("%d%d%d%d",&n[i][0],&n[i][1],&n[i][2],&n[i][3]);
scanf("%d%d",&x,&y);
for(int i=a-1;i>=0;i--){
if(x>=n[i][0]&&x<=n[i][2]+n[i][0]&&y>=n[i][1]&&y<=n[i][3]+n[i][1]){
ans=i+1;
break;
}
}
printf("%d\n",ans);
}
return 0;
}