数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++程序：统计给定操作下，从每个城市可以访问的城市数量
假设我们有一列N个坐标点P，形式为(xi, yi)。x和y值是前N个自然数的排列。对于1到N范围内的每个k，我们位于城市k。我们可以任意多次应用以下操作：我们移动到另一个城市，该城市具有比我们当前所在城市更小的x坐标和更小的y坐标，或者更大的x坐标或更大的y坐标。我们必须找到可以从城市k到达的城市数量。
因此，如果输入类似于P = [[1, 4], [2, 3], [3, 1], [4, 2]]，则输出将为[1, 1, 2, 2]
步骤
为了解决这个问题，我们将遵循以下步骤：
n := size of P
Define one 2D array lst
for initialize i := 0, when i < n, update (increase i by 1), do:
v := { P[i, 0], P[i, 1], i }
insert v at the end of lst
sort the array lst
y_min := 1e9
Define one set se
Define an array ans of size n and fill with 0
for initialize i := 0, when i < n, update (increase i by 1), do:
y_min := minimum of y_min and lst[i, 1]
insert lst[i, 2] into se
if y_min + i is same as n, then:
for each element j in se
ans[j] := size of se
clear the set se
if i is same as n - 1, then:
for each element j in se
ans[j] := size of se
for initialize i := 0, when i < n, update (increase i by 1), do:
display ans[i]示例
让我们看看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
void solve(vector<vector<int>> P){
int n = P.size();
vector<vector<int>> lst;
for (int i = 0; i < n; i++){
vector<int> v = { P[i][0], P[i][1], i };
lst.push_back(v);
}
sort(lst.begin(), lst.end());
int y_min = 1e9;
set<int> se;
vector<int> ans(n, 0);
for (int i = 0; i < n; i++){
y_min = min(y_min, lst[i][1]);
se.insert(lst[i][2]);
if (y_min + i == n){
for (auto j : se)
ans[j] = se.size();
se.clear();
}
if (i == n - 1){
for (auto j : se)
ans[j] = se.size();
}
}
for (int i = 0; i < n; i++){
cout << ans[i] << ", ";
}
}
int main(){
vector<vector<int>> P = { { 1, 4 }, { 2, 3 }, { 3, 1 }, { 4, 2 } };
solve(P);
}输入
{ { 1, 4 }, { 2, 3 }, { 3, 1 }, { 4, 2 } }输出
1, 1, 2, 2,
更新于：2022年3月3日
624 次浏览
广告