1、照明灯安装
你负责在一条笔直的道路上安装一些照明灯。但是道路上并不是任意位置都适合安装照明灯，具体地，假设将道路看作一条起点坐标为\(0\)，终点坐标为\(M\)的线段，那么只有在\(x_1,x_2,..,x_n\)这\(n\)个坐标可以安装照明灯，且每个坐标上最多只能安装一个照明灯。现在你要在道路上安装\(k\)个照明灯，为了使照明灯能够尽量覆盖道路，你需要使距离最近的两个照明灯尽量远。请问这个最近距离最大可以是多少？
输入
第一行是两个整数\(n,k\)，分别表示可以安装照明灯的位置数和需要安装的照明灯数量。
接下来一行\(n\)个整数\(x_1,x_2,\dots,x_n\)表示可以安装照明灯的坐标。保证
\(x_1<x_2<\dots<x_n\)。
- \(1<k\le n\le 100000, 1\le x_i\le
1000000\)
输出
一行，一个整数，表示最近距离的最大值。
样例
1
2
3
4
5
6
7
8
9
10
11
| 输入：
5 3
1 3 4 7 9
输出：
3
提示：
分别放在1、4、7的位置(放在1、4、9也可以)
能够证明3是最小的最大距离。
|
解答
本题是经典二分。二分判断最大距离是\(x\)，如果一个路灯距离上一个路灯的距离超过\(x\)，那么当前路灯可以进行安装。为了方便，在安装第一盏路灯前，可以假设上一路灯的距离为\(-\infty\)。
最终只需要判断能安装路灯的数量是否超过\(k\)即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| # include <bits/stdc++.h>
using namespace std;
const int N=100004;
int a[N],n,k;
bool ok(int x){
int pre=-1e9,cnt=0;
for(int i=1;i<=n;i++){
if(a[i]-pre>=x){
++cnt;pre=a[i];
}
}
return cnt>=k;
}
int main(){
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int l=0,r=1e6+4;
while(l<r){
int mid=(l+r+1)>>1;
if(ok(mid)) l=mid;
else r=mid-1;
}
printf("%d\n",l);
}
|
2、黑白块
有一个\(n*m\)的网格图，起初你在\((1,1)\)处，现在想走到\((n,m)\)处，且经过的黑色网格尽可能少。请输出最少需要经过多少个黑色网格。网格图是四联通的，也就是每次只能向上下左右四个相邻的格子移动，且不能走出边界。
输入
第一行两个正整数\(n\)和\(m\)，含义如上文所述。
接下来\(n\)行，每行\(m\)个数，此数为\(1\)时表示为黑色格子，为\(0\)时表示为白色格子
- \(1\le n\times m\le 100000\)
输出
输出仅包含一个非负整数，表示答案。
样例
1
2
3
4
5
6
7
8
9
10
| 输入：
5 3
0 1 0
0 1 1
0 1 0
1 0 0
1 0 0
输出：
1
|
解答
这道题是一道经典的0-1BFS题目。对于每个格子，我们可以从其到相邻的格子连一条边。如果最终到达的格子是黑格子，那么边权为\(1\)，否则边权为\(0\)。
我们使用双端队列来实现这个0-1BFS问题。假设当前走到了一个白格子，那么花费数不变，并将状态从左端插入队列；否则花费数增加\(1\)，从有端插入队列。
最终搜索完成后，得到的就是从格子\((1,1)\)到达棋盘上所有其它格子的最少经过的黑色格子数量，我们只需要返回位于\((n,m)\)的那个即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| # include <bits/stdc++.h>
using namespace std;
struct P{
int x,y,l;
};
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
int main(){
int n,m;
scanf("%d %d",&n,&m);
vector<vector<int>>a(n,vector<int>(m));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
scanf("%d",&a[i][j]);
vector<vector<int>>f(n,vector<int>(m,-1));
deque<P>q;
q.push_back(P{0,0,a[0][0]});
while(!q.empty()){
P u=q.front();q.pop_front();
if(f[u.x][u.y]!=-1) continue;
f[u.x][u.y]=u.l;
for(int i=0;i<4;i++){
int x=u.x+dx[i],y=u.y+dy[i];
if(x<0||y<0||x>=n||y>=m||f[x][y]!=-1) continue;
if(a[x][y]==0) q.push_front(P{x,y,u.l});
else q.push_back(P{x,y,u.l+1});
}
}
printf("%d\n",f[n-1][m-1]);
}
|