题目:
思想:
1. 贪心
变量:
1. 记Vis[i]=1为第i个房间被网络覆盖
2. 记Vis[i]=0为第i个房间没有被网络覆盖
3. R:半径 N:节点个数
思路:
1. 使用最基础最基础的贪心算法
2. 遍历整个数组Vis
2.1 如图1,该点已经被覆盖,则略过
2.2 如图2,如果该点没有被覆盖,则进行贪心(看下文)
2.2.1 从i+R-1开始从后往前枚举到i-R+1,查看是否有发射器(看问题1[下文])
2.2.2 如果找到发射器j,则将Vis[j-R+1~j+R-1]全部标记为1
2.2.3 如果i+R-1到i-R+1区间,没有找到发射器,则无法覆盖该点,则输出-1,程序结束
疑问:
1.为什么从后往前找发射器?
因为越靠后的发射器,在保证当前节点可以覆盖的时候,尽量覆盖更多后面的点.
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MaxN=2050;
bool Vis[MaxN]; //记录是否被覆盖
int WIFI[MaxN]; //记录发射器位置
int N,R; //N 个数 R 半径
int Count; //记录结果
int main()
{
cin>>N>>R;
for(int i=1;i<=N;i++)cin>>WIFI[i]; //输入
for(int i=1;i<=N;i++)
{
if(!Vis[i]) //该点没有被发射器覆盖
{
bool Flag=false;
for(int j=min(N,i+R-1);j>=max(1,i-R+1);j--)//查找
{
if(WIFI[j])
{
for(int k=max(1,j-R+1);k<=min(N,j+R-1);k++)//标记
{
Vis[k]=true;
}
Count++;
Flag=true; //成功覆盖
break;
}
}
if(!Flag) //失败
{
cout<<-1<<endl;
return 0;
}
}
}
cout<<Count<<endl; //输出
return 0;
}
逻辑大师
感谢
作者好棒!
感谢
补充一下
时间复杂度为O(NR)
N为点数 R为半径
但实际上只有O(N)
很难达到O(NR)
因为你标记过的点直接略过了
%%%%%%
啥意思???
膜膜