用c++ M 国要在 A 城市与 B 城市之间建设 5G 基站,已知 A 城市与 B 城市的距离为 nn 千米,工程师们已经考察在从 A 城市往 B 城市方向上 1,2,...,n 千米处建设 5G 基站的成本,分别是 w1w1,w2w2,...,wnwn。 为了保证通信质量,5G 基站的选址还需要满足 mm 条需求,其中第 ii 条需求可以用 lili 和 riri 表示 (1≤li≤ri≤n1≤li≤ri≤n),代表从 A 城市往 B 城市方向上 lili 千米到 riri 千米的位置之间(含两端)至少需要建设 1 座 5G 基站。 作为总工程师,您需要决定 5G 基站的数量与位置,并计算满足所有需求的最小总成本。 输入格式 第一行输入两个整数 nn 和 mm 分别表示距离和需求数量。 接下来一行输入 nn 个整数 w1w1,w2w2,...,wnwn 分别表示从 A 城市往 B 城市方向上 1,2,...,nn 千米处建设 5G 基站的成本。 接下来 mm 行,第 i 行输入两个整数 lili 和 riri(1≤li≤ri≤n1≤li≤ri≤n) 表示从 A 城市往 B 城市方向上 lili 千米到 riri 千米的位置之间(含两端)至少需要建设 1 座 5G 基站。 输出格式 输出一行一个整数,表示满足所有需求的最小总成本。
时间: 2024-03-20 11:45:26 浏览: 27
这是一个经典的区间覆盖问题,可以使用贪心算法来解决。具体来说,我们可以按照右端点从小到大的顺序排序,然后依次选择右端点最小、且与前面已选择的区间不重叠的区间。
以下是C++代码实现:
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
struct Range
{
int l, r;
bool operator< (const Range& W) const
{
return r < W.r; // 按右端点从小到大排序
}
}range[N];
int n, m;
int w[N];
bool st[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++)
cin >> w[i];
for (int i = 0; i < m; i ++)
cin >> range[i].l >> range[i].r;
sort(range, range + m);
int res = 0;
for (int i = 0; i < m; i ++)
{
int j = range[i].l;
while (j <= range[i].r && st[j]) j ++; // 找到第一个未被覆盖的位置
if (j <= range[i].r) // 如果存在未被覆盖的位置
{
int k = j;
for (; k <= range[i].r; k ++) // 找到从 j 到 r 中成本最小的位置
if (!st[k] && w[k] < w[j])
j = k;
st[j] = true; // 标记该位置已被覆盖
res += w[j];
}
}
cout << res << endl;
return 0;
}
```
时间复杂度分析:排序的时间复杂度为 $O(m\log m)$,依次遍历每个区间的时间复杂度为 $O(nm)$,因此总时间复杂度为 $O(nm + m\log m)$,可以通过本题。