第10章 二分法
2020-03-31 本文已影响0人
得力小泡泡
1、开花
算法分析
由于开花的同学的编号按文学优秀奖的同学a[]优先，把体育优先奖的同学b[]全部扔去set集合中，再枚举所有的a[]，若set中有这个同学则输出
时间复杂度 )
Java 代码
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Main{
static int N = 100010;
static int n,m;
static int[] a = new int[N];
static int[] b = new int[N];
static Set<Integer> set = new HashSet<Integer>();
static int[] ans = new int[N];
static int k = 0;
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
for(int i = 0;i < n;i ++) a[i] = scan.nextInt();
for(int i = 0;i < m;i ++) b[i] = scan.nextInt();
for(int i = 0;i < m;i ++) set.add(b[i]);
for(int i = 0;i < n;i ++)
{
if(set.contains(a[i]))
ans[k ++] = a[i];
}
for(int i = 0;i < k;i ++)
{
if(i != k - 1) System.out.print(ans[i] + " ");
else System.out.println(ans[i] + " ");
}
}
}
二分法
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
public class Main {
static int N = 100010;
static int[] a = new int[N];
static int[] b = new int[N];
static int[] ans = new int[N];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
String[] s1 = br.readLine().split(" ");
int n = Integer.parseInt(s1[0]);
int m = Integer.parseInt(s1[1]);
String[] s2 = br.readLine().split(" ");
for(int i = 0;i < n;i ++) a[i] = Integer.parseInt(s2[i]);
String[] s3 = br.readLine().split(" ");
for(int i = 0;i < m;i ++) b[i] = Integer.parseInt(s3[i]);
Arrays.sort(b, 0, m);
int k = 0;
for(int i = 0;i < n;i ++)
{
int l = 0, r = m - 1;
while(l < r)
{
int mid = l + r >> 1;
if(b[mid] >= a[i]) r = mid;
else l = mid + 1;
}
if(b[l] == a[i]) ans[k ++] = a[i];
}
for(int i = 0;i < k;i ++)
{
if(i != k - 1) System.out.print(ans[i] + " ");
else System.out.println(ans[i]);
}
log.flush();
}
}
2、切割钢管
算法分析
求的是能满足题意的柱子能建多高，l = 1,r = 100000000，这个区域二分，求左边区域的最大值
check(x)：表示至少有k个长度大于等于x的棍子，满足返回true，否则返回false
时间复杂度 )
Java 代码
import java.util.Scanner;
public class Main{
static int N = 10010 ;
static int n,k;
static int[] h = new int[N];
static boolean check(int x)
{
int res = 0;
for(int i = 0;i < n; i ++)
{
res += h[i] / x;
}
return res >= k;
}
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
k = scan.nextInt();
for(int i = 0;i < n;i ++) h[i] = scan.nextInt();
int l = 1,r = 100000000;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
System.out.println(l);
}
}
3、跳石子
算法分析
本题求的是两点之间最小距离的最大值，因此用二分求解
求的是左区域的最大值
-
check(x):表示搬走m个石子能使得所有点两点之间的距离的最小距离大于等于x -
check函数的做法，now表示固定的当前石子，从1枚举到n + 1，如果s[i] - s[now] < x,则搬走这个i石子，否则更新now = i - 注意：由于最后一个石子需要特判的，但是枚举到第
n + 1个石子，若不符合条件，由于最后一个石子是一定固定的，cnt++表示把前面那颗now扔掉即可
时间复杂度 )
Java 代码
import java.util.Scanner;
public class Main {
static int N = 50010;
static int[] s = new int[N];
static int m;
static int n;
static int L;
static boolean check(int x)
{
int cnt = 0,now = 0;
for(int i = 1;i <= n + 1;i ++)
{
if(s[i] - s[now] < x) cnt ++;
else now = i;
}
return cnt <= m;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
L = scan.nextInt();
n = scan.nextInt();
m = scan.nextInt();
for(int i = 1;i <= n;i++) s[i] = scan.nextInt();
s[n + 1] = L;
int l = 0,r = L;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
System.out.println(l);
}
}
4、转圈游戏
算法分析
快速幂，x位置，转了很多次，一次走m个位置
时间复杂度 )
Java 代码
import java.util.Scanner;
public class Main {
static long qmi(int a,int k,int p)
{
long res = 1;
long t = a;
while(k > 0)
{
if((k & 1) == 1) res = res * t % p;
k >>= 1;
t = t * t % p;
}
return res;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
int k = scan.nextInt();
int x = scan.nextInt();
System.out.println((x + qmi(10,k,n) * m % n) % n) ;
}
}
5、架设电线
算法分析
单源最短路 + 二分
题目描述到有k条边可以免费升级，因此只需要求1~N的所有路径中第k + 1大的值的最小值，是最大最小值模型，因此可以使用二分求解
对于区间[0,1000001]中的某一个点x：
- 1、
check(x)函数表示:从1走到N，最少经过的长度大于x的边数的数量是否小于等于k，若是则返回true，否则返回false
- 2、求出从
1到N最少经过几条长度大于x的边
可以分类成：
* 如果边大于`x`，则边权看成`1`
* 如果边长小于等于`x`，则边权看成`0`
注意：
- 1、初始
l = 0，r = 1000001的原因是：如果1号点到n号点是不连通的，最后二分出来的值一定是1000001，表示无解
- 2、对于只有两种边权是
0,1可以使用双端队列求解，下面使用的是spfa
时间复杂度 )
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int N = 1010,M = 10010 * 2;
static int n,m,k;
static int INF = 0x3f3f3f3f;
static int[] h = new int[N];
static int[] e = new int[M];
static int[] w = new int[M];
static int[] ne = new int[M];
static int idx = 0;
static int[] dist = new int[N];
static boolean[] st = new boolean[N];
static void add(int a,int b,int c)
{
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx ++;
}
static boolean check(int x)
{
Arrays.fill(dist, INF);
Queue<Integer> q = new LinkedList<Integer>();
q.add(1);
st[1] = true;
dist[1] = 0;
while(!q.isEmpty())
{
int t = q.poll();
st[t] = false;
for(int i = h[t];i != -1;i = ne[i])
{
int j = e[i];
if(w[i] > x)
{
if(dist[j] > dist[t] + 1)
{
dist[j] = dist[t] + 1;
if(!st[j])
{
q.add(j);
st[j] = true;
}
}
}
else
{
if(dist[j] > dist[t])
{
dist[j] = dist[t];
if(!st[j])
{
q.add(j);
st[j] = true;
}
}
}
}
}
if(dist[n] <= k) return true;
return false;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = br.readLine().split(" ");
n = Integer.parseInt(s1[0]);
m = Integer.parseInt(s1[1]);
k = Integer.parseInt(s1[2]);
Arrays.fill(h, -1);
while(m -- > 0)
{
String[] s2 = br.readLine().split(" ");
int a = Integer.parseInt(s2[0]);
int b = Integer.parseInt(s2[1]);
int c = Integer.parseInt(s2[2]);
add(a,b,c);
add(b,a,c);
}
//求最大边的最小值
int l = 0,r = 1000001;
while(l < r)
{
int mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
if(l == 1000001) System.out.println("-1");
else System.out.println(l);
}
}
