洛谷 P1902 刺杀大使（二分）

//这可能是期末考试前的最后一篇题解了趴

传送门

解题思路

让伤害最大值最小，很显然用二分，然后O(nm)跑一遍图，看看能不能到终点即可。

总复杂度：O(nm*log(p_max))。

AC代码

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cmath>
 4 #include<cstdio>
 5 #include<cstring>
 6 using namespace std;
 7 const int maxn=1005;
 8 int n,m,p[maxn][maxn],maxp,vis[maxn][maxn];
 9 int ch[4][2]={{0,-1},{-1,0},{0,1},{1,0}};
10 bool dfs(int x,int y,int t){
11     if(x==n) return 1;
12     if(vis[x][y]) return 0;
13     vis[x][y]=1;
14     for(int i=0;i<4;i++){
15         if((x+ch[i][0]>0&&y+ch[i][1]>0&&y+ch[i][1]<=m)&&p[x+ch[i][0]][y+ch[i][1]]<=t){
16             if(dfs(x+ch[i][0],y+ch[i][1],t)) return 1;
17         }
18     }
19     return 0;
20 }
21 bool check(int x){
22     memset(vis,0,sizeof(vis));
23     for(int i=1;i<=m;i++){
24         if(dfs(1,i,x)) return 1;
25     }
26     return 0;
27 }
28 int main()
29 {
30     cin>>n>>m;
31     for(int i=1;i<=n;i++){
32         for(int j=1;j<=m;j++){
33             scanf("%d",&p[i][j]);
34             maxp=max(maxp,p[i][j]);
35         }
36     }
37     int l=0,r=maxp;
38     while(l<r){
39         int mid=(l+r)/2;
40         if(!check(mid)){
41             l=mid+1;
42         }else{
43             r=mid;
44         }
45     }
46     cout<<l;
47     return 0;
48 }