• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

洛谷P1003

开发技术 开发技术 5小时前 1次浏览

title: “洛谷P1003”
author: Sun-Wind
date: September 13, 2021

洛谷P1003

题目大意

简而言之就是在坐标轴上铺地毯,根据输入的坐标将地毯放在坐标轴上,然后最后给出一个坐标,找到铺在这个坐标上最上面的地毯编号

Train of thought

首先我们应该找到每个矩阵对应包含的范围,这样我们才能去寻找目标点最上方的矩阵
这里我们采用枚举的方式,创建一个结构体,其包含的是对应矩阵的范围

struct Matrix{
    int x1,x2;
    int y1,y2;
};

遍历整个数组,如果发现目标点在矩阵范围内,就把对应得编号记下来

Time complexity

输入最多需要104,每次输入处理两次,然后遍历整个数组一次,每次遍历比较一次,总的时间复杂度大概为2*104 + 10 ^4,就是0(n)

综上所述,代码如下:

#include<iostream>
#include<utility>
#include<vector>
using namespace std;
typedef long long ll;
#define fi(a,b) for(int i = a; i <= b; ++i)
#define fr(a,b) for(int i = a; i >= b; --i)
using pii = pair<int,int>;
struct Matrix{
    int x1,x2;
    int y1,y2;
};
vector<Matrix> vec;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
while(n--)
{
    Matrix temp;
    cin >> temp.x1 >> temp.y1;
    int q,w;
    cin >> q >> w;
    temp.x2 = temp.x1 + q;
    temp.y2 = temp.y1 + w;
    vec.push_back(temp);
}//处理范围
int r,w;
cin >> r >> w;
int result = -1;
fi(0,vec.size()-1)
{
    if(vec[i].x1 <= r && r <= vec[i].x2 && w >= vec[i].y1 && w <= vec[i].y2)
        result = i;//如果满足条件,就记下对应得编号
}
result++;//因为编号是从0开始,所以最后要加一
if(result == 0)
cout << "-1" << endl;
else
cout << result << endl;
return 0;
}

优化

考虑从后往前遍历,遇到满足条件的就直接跳出,这样可以有效地降低时间复杂度


感谢大家的阅读,如果觉得还不错就点个赞吧ヾ(≧▽≦*)o


程序员灯塔
转载请注明原文链接:洛谷P1003
喜欢 (0)