请帮助加快此任务的代码:
同步(20 分)
一组 n 颗卫星位于坐标线上的坐标为 1、2、...n 的点处。每颗卫星的特征在于它产生的信号的功率 pi。如果 xi 点处的卫星具有信号强度 pi,则位于不大于 pi 距离处的所有卫星都可以接收到来自该卫星的信号。卫星本身不接收它的信号。
为了同步工作,所有卫星同时将它们的信号发送到它们的信号到达的所有其他卫星。每颗卫星都需要确定它从多少其他卫星接收到信号。
输入格式
第一行包含数字 n - 卫星数量,2 ≤ n ≤ 105。第二行包含 n 个空格分隔的整数 - 相应卫星的功率。第二条线的第 i 个位置包含位于坐标线上 i 点的卫星的功率。所有幂都是 1 到 109 之间的整数。
输出格式
输出 n 个空格分隔的数字,表征卫星在同步期间接收到的信号数量。第 i 个位置应指示位于坐标线上第 i 点的卫星接收到的信号数量。
#include <iostream>
#include <vector>
using namespace std;
int main(){
int n;
cin >> n;
vector <int> a(n, -1);
for (int i = 0; i < n; i++){
int p;
cin >> p;
for (int j = max(0, i - p); j < min(n, i + p + 1); j++){
a[j] += 1;
}
}
for (int i = 0; i < n; i++){
cout << a[i] << " ";
}
}
对于每颗卫星,创建三个结构,其中包含:
并将所有内容合并到一个向量或数组中
按第一个字段对向量进行排序。如果第一个字段相等,则带有 +1 的条目首先出现。
初始化
active_count = 0
,遍历向量。如果第二个字段不为空,则将其添加到
active_count
如果为零,则相应的卫星从
active_count - 1
其他卫星接收数据。复杂性
O(nlogn)
是由于排序,通过列表的通道是线性的。