优化: Hackerearth Postman软件工程师实习生问题
你想买台笔记本电脑。每台笔记本电脑都有两个参数:额定值和价格。你的任务是在给定的价格范围内购买一台评级最高的笔记本电脑。给定Q任务，每个查询包含所需的价格范围，您必须打印在该价格范围内可以购买的最高级别笔记本电脑。 输入格式： 第一行包含N个，表示输入的数目。 以下N行包含表示笔记本电脑价格和范围的P&R。 下一行包含表示查询数量的Q。 以下Q行包含两个整数X&Y，表示价格范围(包括)。 输出格式： 对于每个任务Q，打印可以在范围内购买的最高评级。 如果你不能得到任何笔记本电脑的范围内，打印-1。 约束： 1 <= N，Q <= 10^6 0 <= R，P <= 10^9 1 <= X <= Y <= 10^9 时间限制:每次输入6秒 示例输入： 5 1000 300 1100 400 1300 200 1700 2000 600 3 1000 1400 1700 1900 0 2000 示例输出： 400 500 600
My Approach
- 生成(键、值)映射
- 而Y->X做， 迭代器= map.find(Y) 如果迭代器，那么，max_rating = max(max_rating，iterator.value)
- 返回max_rating
这里是我的解决方案
int solve(vector<int> P, vector<int> R, int X, int Y)
{
int max_value=-1;
map<int,int> price_rating;
for(int i=0;i<N;i++)
{
price_rating.insert(pair<int, int>(P[i],R[i]));
}
while(y>x)
{
auto iterator = price_rating.find(y);
if(iterator!=price_rating.end())
{
max_rating = max(max_rating,iterator->second);
}
y-=1;
}
return max_rating;
}只有少数测试用例使用上述解决方案通过，而其他测试用例由于TLE (超过时间限制)而失败。如果能找到更好的解决办法就太好了。
回答 2
Stack Overflow用户
发布于 2019-09-29 19:54:41
调查段树。
其思想是首先构建一个段树，其中每个节点代表一个价格范围，并存储该范围的最高评级。
例如，如果您的数据有7种价格，{10、20、30、40、50、60、70}，您将创建一个具有以下节点的树：
[10-70]
/ \
[10-30] [40-70]
/ \ / \
[10-20] [30] [40-50] [60-70]
/ \ / \ / \
[10] [20] [40] [50] [60] [70]叶子是“范围”，只有一个价格。您可以在此树上设置最高评等，以便每个节点都具有该特定范围的最高评等。
然后，对于实际的查询，您可以遍历树(深度优先搜索)，并且：
- 排除通过其范围不与所查询范围重叠的节点的路径。
- 当有部分重叠时继续往下钻(延伸路径)。
- 在完全处于查询范围内的节点上停止并回溯。
最终，您将在节点上结束，这些节点加在一起将达到所查询的范围。从这些节点获取最大等级，而从递归中进行回溯。
这将使查询在O(logn)中运行。
Stack Overflow用户
发布于 2021-11-02 15:19:11
有关上述问题，请参阅下面的代码。我在考试中努力解决这个问题。
该方案的任务：
- 根据价格对价格和评级向量进行排序。
- 根据“sl，sr指数之间的最大等级”建立分段树
- 在queryLowPrice和queryHighPrice之间获取queryHighPrice时，只需检查当前节点是否包含该价格，并根据该价格返回答案。
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
struct mydtype
{
int price;
int rating;
};
bool comp( mydtype a, mydtype b ){
if( a.price != b.price ) return a.price<b.price;
else return a.rating<b.rating;
}
int getMid( int a , int b ){
return a+(b-a)/2;
}
void build( int st[], vector<mydtype> v, int si, int sl, int sr ){
if(sl==sr) st[si]=v[sl].rating;
else{
int mid=getMid(sl,sr);
build(st,v,2*si+1,sl,mid);
build(st,v,2*si+2,mid+1,sr);
st[si]=max( st[2*si+1], st[2*si+2] );
}
}
int getMaxRating(int st[], vector<mydtype> v , int si, int sl, int sr, int queryLowPrice, int queryHighPrice ){
if( queryLowPrice > queryHighPrice ) return -1;
int stLowPrice = v[sl].price;
int stHighPrice = v[sr].price;
if( queryLowPrice > stHighPrice || queryHighPrice < stLowPrice ) return INT_MIN;
if( stLowPrice>= queryLowPrice && stHighPrice <= queryHighPrice ) return st[si];
else{
int mid = getMid(sl,sr);
return max( getMaxRating( st, v, 2*si+1, sl, mid, queryLowPrice, queryHighPrice ),
getMaxRating( st, v, 2*si+2, mid+1, sr, queryLowPrice, queryHighPrice ) );
}
}
int main ()
{
int n = 5;
vector < mydtype > v(n);
v={{10,2}, {20,3}, {20,4}, {30,4}, {40,2}};
sort(v.begin(),v.end(), comp);
int max_size = 15;
int st[max_size];
build (st, v, 0, 0, n-1 );
cout<< getMaxRating(st, v, 0, 0, n-1, 19, 21);
return 0;
}https://stackoverflow.com/questions/58157471
复制相似问题
腾讯云开发者
