洛谷二分题
P1024 [NOIP2001 提高组] 一元三次方程求解
题目描述
有形如：𝑎𝑥3+𝑏𝑥2+𝑐𝑥+𝑑=0ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数（𝑎,𝑏,𝑐,𝑑a,b,c,d 均为实数），并约定该方程存在三个不同实根（根的范围在 −100−100 至 100100 之间），且根与根之差的绝对值 ≥1≥1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后 22 位。
提示：记方程 𝑓(𝑥)=0f(x)=0，若存在 22 个数 𝑥1x1 和 𝑥2x2，且 𝑥1<𝑥2x1<x2，𝑓(𝑥1)×𝑓(𝑥2)<0f(x1)×f(x2)<0，则在 (𝑥1,𝑥2)(x1,x2) 之间一定有一个根。
输入格式
一行，44 个实数 𝑎,𝑏,𝑐,𝑑a,b,c,d。
输出格式
一行，33 个实根，从小到大输出，并精确到小数点后 22 位。
输入输出样例
输入 #1复制
1 -5 -4 20输出 #1复制
-2.00 2.00 5.00说明/提示
【题目来源】
NOIP 2001 提高组第一题
import java.util.*;
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);double a = scanner.nextDouble();double b = scanner.nextDouble();double c = scanner.nextDouble();double d = scanner.nextDouble();for (double i = -100; i <= 100; i += 0.001) {double j = i + 0.001;double y1 = a * Math.pow(i, 3) + b * Math.pow(i, 2) + c * i + d;double y2 = a * Math.pow(j, 3) + b * Math.pow(j, 2) + c * j + d;if ((y1 >= 0 && y2 <= 0) || (y1 <= 0 && y2 >= 0)) {double x = (i + j) / 2;System.out.printf("%.2f ", x);}}}
}P2678 [NOIP2015 提高组] 跳石头
题目背景
NOIP2015 Day2T1
题目描述
一年一度的“跳石头”比赛又要开始了！
这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 𝑁N 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。
为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 𝑀M 块岩石（不能移走起点和终点的岩石）。
输入格式
第一行包含三个整数 𝐿,𝑁,𝑀L,N,M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 𝐿≥1L≥1 且 𝑁≥𝑀≥0N≥M≥0。
接下来 𝑁N 行，每行一个整数，第 𝑖i 行的整数 𝐷𝑖 (0<𝐷𝑖<𝐿)Di(0<Di<L)， 表示第 𝑖i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。
输出格式
一个整数，即最短跳跃距离的最大值。
输入输出样例
输入 #1复制
25 5 2 2 11 14 17 21输出 #1复制
4说明/提示
输入输出样例 1 说明
将与起点距离为 22 和 1414 的两个岩石移走后，最短的跳跃距离为 44（从与起点距离 1717 的岩石跳到距离 2121 的岩石，或者从距离 2121 的岩石跳到终点）。
数据规模与约定
对于 20%20%的数据，0≤𝑀≤𝑁≤100≤M≤N≤10。
对于 50%50% 的数据，0≤𝑀≤𝑁≤1000≤M≤N≤100。
对于 100%100% 的数据，0≤𝑀≤𝑁≤50000,1≤𝐿≤1090≤M≤N≤50000,1≤L≤109。
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 读取起点到终点的距离Lint L = in.nextInt();// 读取起点和终点之间的岩石数Nint N = in.nextInt();// 读取组委会至多移走的岩石数Mint M = in.nextInt();// 用于存储每块岩石与起点的距离，数组大小为N + 2，// 其中第0个位置不用，方便后续计算，所以长度为N + 2int[] bones = new int[N + 2];// 循环读取每块岩石与起点的距离，并存储到bones数组中for (int i = 1; i <= N; i++) {bones[i] = in.nextInt();}// 将终点与起点的距离存入bones数组的最后一个位置（N + 1）bones[N + 1] = L;// 调用solve方法计算最短跳跃距离的最大值，并输出结果System.out.println(solve(bones, M, L));}public static int solve(int[] dis, int quantity, int n) {// 初始化左端点l为1，表示最短跳跃距离的可能最小值int l = 1;// 初始化右端点r为n，表示起点到终点的距离，即最短跳跃距离的可能最大值int r = n;int ans = 0;// 使用二分查找来确定最短跳跃距离的最大值while (l <= r) {// 计算中间值mid，这里使用位运算 >> 1 相当于除以2int mid = l + r >> 1;// tot用于记录在当前假设的最短跳跃距离mid下，需要移走的岩石数量int tot = 0;// now用于记录当前所在的岩石位置索引，初始化为0int now = 0;// 遍历所有岩石（除了第0个位置，因为第0个位置未使用）for (int i = 1; i < dis.length; i++) {// 如果当前岩石与上一块岩石的距离小于假设的最短跳跃距离midif (dis[i] - dis[now] < mid) {// 则需要移走这块岩石，移走岩石数量加1tot++;} else {// 否则，更新当前所在的岩石位置索引为当前岩石的索引inow = i;}}// 如果需要移走的岩石数量tot不超过允许移走的数量quantityif (tot <= quantity) {// 说明当前假设的最短跳跃距离mid是可行的，更新答案ans为midans = mid;// 并且尝试增大最短跳跃距离，将左端点l更新为mid + 1l = mid + 1;} else {// 如果需要移走的岩石数量超过了允许移走的数量，说明当前假设的最短跳跃距离mid过大// 则需要减小最短跳跃距离，将右端点r更新为mid - 1r = mid - 1;}}// 返回最短跳跃距离的最大值return ans;}
}P1902 刺杀大使
题目描述
某组织正在策划一起对某大使的刺杀行动。他们来到了使馆，准备完成此次刺杀，要进入使馆首先必须通过使馆前的防御迷阵。
迷阵由 𝑛×𝑚n×m 个相同的小房间组成，每个房间与相邻四个房间之间有门可通行。在第 𝑛n 行的 𝑚m 个房间里有 𝑚m 个机关，这些机关必须全部打开才可以进入大使馆。而第 11 行的 𝑚m 个房间有 𝑚m 扇向外打开的门，是迷阵的入口。除了第 11 行和第 𝑛n 行的房间外，每个房间都被使馆的安保人员安装了激光杀伤装置，将会对进入房间的人造成一定的伤害。第 𝑖i 行第 𝑗j 列 造成的伤害值为 𝑝𝑖,𝑗pi,j（第 11 行和第 𝑛n 行的 𝑝p 值全部为 00）。
现在某组织打算以最小伤害代价进入迷阵，打开全部机关，显然，他们可以选 择任意多的人从任意的门进入，但必须到达第 𝑛n 行的每个房间。一个士兵受到的伤害值为他到达某个机关的路径上所有房间的伤害值中的最大值，整个部队受到的伤害值为所有士兵的伤害值中的最大值。现在，这个恐怖组织掌握了迷阵的情况，他们需要提前知道怎么安排士兵的行进路线可以使得整个部队的伤害值最小。
输入格式
第一行有两个整数 𝑛,𝑚n,m，表示迷阵的大小。
接下来 𝑛n 行，每行 𝑚m 个数，第 𝑖i 行第 𝑗j 列的数表示 𝑝𝑖,𝑗pi,j。
输出格式
输出一个数，表示最小伤害代价。
输入输出样例
输入 #1复制
4 2 0 0 3 5 2 4 0 0输出 #1复制
3说明/提示
- 50%50% 的数据，𝑛,𝑚≤100n,m≤100；
- 100%100% 的数据，𝑛,𝑚≤1000n,m≤1000，𝑝𝑖,𝑗≤1000pi,j≤1000。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;public class Main {// 使用StreamTokenizer来处理输入，从标准输入读取数据private static final StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));// 定义四个方向的偏移量，用于在迷阵中进行上下左右四个方向的移动private static final int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};// 迷阵的行数private static int n;// 迷阵的列数private static int m;// 存储迷阵中每个房间造成的伤害值的二维数组private static int[][] p;// 用于标记每个房间是否已经被访问过的二维数组private static boolean[][] visited;// 从输入流中获取下一个整数的方法private static int nextInt() throws IOException {in.nextToken();return (int) in.nval;}// 深度优先搜索方法，用于校验是否存在一条从当前位置 (i, j) 到最后一行的路径，// 且路径上房间的伤害值最大值不超过resprivate static boolean dfs(int i, int j, int res) {// 如果已经到达最后一行，说明找到了一条可行路径if (i == n - 1) {return true;}visited[i][j] = true;// 对四个方向进行搜索for (int[] direction : directions) {int x = i + direction[0];int y = j + direction[1];// 检查新位置 (x, y) 是否在迷阵范围内boolean checkPos = x >= 0 && x < n&& y >= 0 && y < m;// 如果新位置在迷阵内，未被访问过，且该位置的伤害值不超过resif (checkPos &&!visited[x][y] && p[x][y] <= res) {// 继续递归搜索从新位置出发是否能到达最后一行if (dfs(x, y, res)) {return true;}// 如果从新位置出发无法到达最后一行，回溯（将当前位置标记为未访问）}}return false;}public static void main(String[] args) throws IOException {// 读取迷阵的行数和列数n = nextInt();m = nextInt();// 初始化存储伤害值的二维数组和标记访问情况的二维数组p = new int[n][m];visited = new boolean[n][m];// 初始化用于二分查找的左右边界，left初始化为一个较大值，right初始化为0int left = 1001, right = 0;// 读取迷阵中每个房间的伤害值，并同时更新left和right的值for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {p[i][j] = nextInt();left = Math.min(left, p[i][j]);right = Math.max(right, p[i][j]);}}// 初始化结果为right，即初始假设最大伤害值为所有房间伤害值中的最大值int res = right;// 二分查找最小伤害代价while (left <= right) {// 每次循环开始时，将所有房间的访问标记重置为未访问for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {visited[i][j] = false;}}// 计算中间值int mid = left + right >> 1;// 从迷阵的第一行的每个房间开始进行深度优先搜索，// 检查是否存在一条路径使得最大伤害值不超过midif (dfs(0, 0, mid)) {// 如果存在这样的路径，更新结果res为mid，并缩小右边界res = mid;right = mid - 1;} else {// 如果不存在这样的路径，增大左边界left = mid + 1;}}// 输出最小伤害代价System.out.println(res);}
}https://www.luogu.com.cn/problem/P1314
P1314 [NOIP2011 提高组] 聪明的质监员
题目描述
小T是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有 𝑛n 个矿石，从 11 到 𝑛n 逐一编号，每个矿石都有自己的重量 𝑤𝑖wi 以及价值 𝑣𝑖vi 。检验矿产的流程是：
- 给定𝑚m 个区间 [𝑙𝑖,𝑟𝑖][li,ri]；
- 选出一个参数 𝑊W；
- 对于一个区间 [𝑙𝑖,𝑟𝑖][li,ri]，计算矿石在这个区间上的检验值 𝑦𝑖yi：
𝑦𝑖=∑𝑗=𝑙𝑖𝑟𝑖[𝑤𝑗≥𝑊]×∑𝑗=𝑙𝑖𝑟𝑖[𝑤𝑗≥𝑊]𝑣𝑗yi=j=li∑ri[wj≥W]×j=li∑ri[wj≥W]vj
其中 𝑗j 为矿石编号。
这批矿产的检验结果 𝑦y 为各个区间的检验值之和。即：∑𝑖=1𝑚𝑦𝑖i=1∑myi
若这批矿产的检验结果与所给标准值 𝑠s 相差太多，就需要再去检验另一批矿产。
小T不想费时间去检验另一批矿产，所以他想通过调整参数 𝑊W 的值，让检验结果尽可能的靠近标准值 𝑠s，即使得 ∣𝑠−𝑦∣∣s−y∣ 最小。请你帮忙求出这个最小值。输入格式
第一行包含三个整数 𝑛,𝑚,𝑠n,m,s，分别表示矿石的个数、区间的个数和标准值。
接下来的 𝑛n 行，每行两个整数，中间用空格隔开，第 𝑖+1i+1 行表示 𝑖i 号矿石的重量 𝑤𝑖wi 和价值 𝑣𝑖vi。
接下来的 𝑚m 行，表示区间，每行两个整数，中间用空格隔开，第 𝑖+𝑛+1i+n+1 行表示区间 [𝑙𝑖,𝑟𝑖][li,ri] 的两个端点 𝑙𝑖li 和 𝑟𝑖ri。注意：不同区间可能重合或相互重叠。
输出格式
一个整数，表示所求的最小值。
输入输出样例
输入 #1复制
5 3 15 1 5 2 5 3 5 4 5 5 5 1 5 2 4 3 3输出 #1复制
10说明/提示
【输入输出样例说明】
当 𝑊W 选 44 的时候，三个区间上检验值分别为 20,5,020,5,0 ，这批矿产的检验结果为 2525，此时与标准值 𝑆S 相差最小为 1010。
【数据范围】
对于 10%10% 的数据，有 1≤𝑛,𝑚≤101≤n,m≤10；
对于 30%30%的数据，有 1≤𝑛,𝑚≤5001≤n,m≤500 ；
对于 50%50% 的数据，有 1≤𝑛,𝑚≤5,0001≤n,m≤5,000；
对于 70%70% 的数据，有 1≤𝑛,𝑚≤10,0001≤n,m≤10,000 ；
对于 100%100% 的数据，有 1≤𝑛,𝑚≤200,0001≤n,m≤200,000，0<𝑤𝑖,𝑣𝑖≤1060<wi,vi≤106，0<𝑠≤10120<s≤1012，1≤𝑙𝑖≤𝑟𝑖≤𝑛1≤li≤ri≤n
import java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.io.BufferedReader;
import java.io.BufferedOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;public class Main {// 创建一个BufferedReader对象，用于从标准输入读取字符流数据static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));// 创建一个StreamTokenizer对象，用于将读取到的字符流解析为标记（token），以便于获取不同类型的数据static StreamTokenizer st = new StreamTokenizer(br);// 创建一个PrintWriter对象，用于将数据输出到标准输出，通过BufferedOutputStream进行缓冲，提高输出效率static PrintWriter OUT = new PrintWriter(new BufferedOutputStream(System.out));// 定义一个方法，用于从输入流中获取下一个整数类型的数据public static int nextInt() throws Exception {st.nextToken();return (int) st.nval;}// 定义一个方法，用于从输入流中获取下一个长整数类型的数据public static long nextLong() throws Exception {st.nextToken();return (long) st.nval;}// 存储矿石的个数static int n;// 存储区间的个数static int m;// 存储标准值，即期望的矿产检验结果值static long s;// 以下几个变量用于在程序执行过程中的一些临时计算和存储，初始值在这里只是占位，后续会重新赋值static int l, r, w;// 用于存储最终找到的与标准值相差最小的检验结果差值的绝对值，初始化为Long.MAX_VALUEstatic long ans = Long.MAX_VALUE;// 用于累加各个区间的检验值，在每次计算区间检验值时会更新static long sum;// 用于存储最终计算得到的当前参数W下的检验结果与标准值的差值的绝对值static long res;// 二维数组，用于存储每个矿石的重量和价值信息，第一维长度为n + 1，方便从1开始索引每个矿石static int[][] arr = new int[n + 1][2];// 二维数组，用于存储每个区间的左右端点信息，第一维长度为m + 1，方便从1开始索引每个区间static int[][] range = new int[m + 1][2];// 一维数组，用于存储与矿石重量和价值相关的一种前缀和信息，长度为n + 1，方便从1开始索引static long[] pre = new long[n + 1];// 一维数组，用于存储与矿石重量相关的另一种前缀和信息，长度为n + 1，方便从1开始索引static long[] preW = new long[n + 1];public static void main(String[] args) throws Exception {// 从标准输入读取矿石的个数、区间的个数和标准值n = nextInt();m = nextInt();s = nextLong();// 初始化存储每个矿石重量和价值信息的二维数组arr = new int[n + 1][2];// 初始化存储每个区间左右端点信息的二维数组range = new int[m + 1][2];// 初始化用于存储一种前缀和信息的一维数组pre = new long[n + 1];// 初始化用于存储另一种前缀和信息的一维数组preW = new long[n + 1];// 循环读取每个矿石的重量和价值信息，并同时更新l和r的值，// l用于记录目前遇到的最小的矿石价值，r用于记录目前遇到的最大的矿石价值（初始值不准确，后续会修正）for (int i = 1; i <= n; i++) {arr[i][0] = nextInt();arr[i][1] = nextInt();l = Math.min(arr[i][1], l);r = Math.max(arr[i][1], r);}// 循环读取每个区间的左右端点信息for (int i = 1; i <= m; i++) {range[i][0] = nextInt();range[i][1] = nextInt();}// 对l和r进行调整，l减去1，r加上2，这样做是为了确保在后续的二分查找过程中，// 能够覆盖所有可能的重量值范围，避免遗漏边界情况l -= 1;r += 2;// 开始二分查找合适的参数W的值，使得检验结果与标准值的差值绝对值最小while (l <= r) {// 计算当前二分查找的中间值midint mid = l + (r - l) / 2;// 调用ok方法检查以mid作为参数W时的检验结果情况if (ok(mid)) {// 如果ok方法返回true，说明当前的mid使得检验结果大于标准值s，// 则将左边界l更新为mid + 1，继续在右半部分查找更小的W值l = mid + 1;} else {// 如果ok方法返回false，说明当前的mid使得检验结果小于等于标准值s，// 则将右边界r更新为mid - 1，继续在左半部分查找更合适的W值r = mid - 1;}// 如果当前找到的结果res比之前记录的ans更小，更新ans的值if (ans > res) {ans = res;}}// 输出最终找到的与标准值相差最小的检验结果差值的绝对值System.out.println(ans);}// 定义一个方法，用于检查以给定的w作为参数W时，计算得到的检验结果与标准值s的差距情况public static boolean ok(int w) {// 初始化sum为0，用于累加各个区间的检验值sum = 0;// 遍历每个矿石，根据矿石的重量与w的关系更新相关的前缀和信息for (int i = 1; i <= n; i++) {if (arr[i][0] >= w) {// 如果矿石的重量大于等于w，更新与矿石价值相关的前缀和pre// 以及与矿石重量大于等于w的数量相关的前缀和preWpre[i] = pre[i - 1] + arr[i][1];preW[i] = preW[i - 1] + 1;} else {// 如果矿石的重量小于w，保持这两种前缀和不变preW[i] = preW[i - 1];pre[i] = pre[i - 1];}}// 遍历每个区间，根据之前更新的前缀和信息计算该区间的检验值，并累加到sum中for (int i = 1; i <= m; i++) {sum += (pre[range[i][1]] - pre[range[i][0] - 1]) * (preW[range[i][1]] - preW[range[i][0] - 1]);}// 计算当前检验结果sum与标准值s的差值的绝对值res = Math.abs(sum - s);// 如果当前检验结果sum大于标准值s，返回true，否则返回falseif (sum > s) {return true;}return false;}
}