5月22总结
P1024 [NOIP 2001 提高组] 一元三次方程求解
题目描述
有形如：$ a x^3 + b x^2 + c x + d = 0 $ 这样的一个一元三次方程。给出该方程中各项的系数（$ a,b,c,d $ 均为实数），并约定该方程存在三个不同实根（根的范围在 $ -100 $ 至 $ 100 $ 之间），且根与根之差的绝对值 $ \ge 1 $。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后 $ 2 $ 位。
提示：记方程 $ f(x) = 0 $，若存在 $ 2 $ 个数 $ x_1 $ 和 $ x_2 $，且 $ x_1 < x_2 ， ， ， f(x_1) \times f(x_2) < 0 $，则在 $ (x_1, x_2) $ 之间一定有一个根。
输入格式
一行，$ 4 $ 个实数 $ a, b, c, d $。
输出格式
一行，$ 3 $ 个实根，从小到大输出，并精确到小数点后 $ 2 $ 位。
输入输出样例 #1
输入 #1
1 -5 -4 20
输出 #1
-2.00 2.00 5.00
说明/提示
【题目来源】
NOIP 2001 提高组第一题
题解:
就是特别要注意输入不是整数实数,所以用double,然后就是数学的零点存在定理,再运用二分法求出零点所在
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
double a, b, c, d;
double f(double x) {return a * x * x * x + b * x * x + c * x + d;
}
int main() {cin >> a >> b >> c >> d;for (double x = -100; x <= 100; x++) {double left = x, right = x + 1;if (f(left) * f(right) == 0) {if (f(left) == 0) {printf("%.2f ", left);}}else if (f(left) * f(right) < 0) {while (right - left >=0.001) {double mid = right + (left - right) / 2;if (f(left) * f(mid) < 0) {right = mid;}else {left = mid;}}printf("%.2f ", left);}else continue;}return 0;
}
P1182 数列分段 Section II
题目描述
对于给定的一个长度为 $ N $ 的正整数数列 $ A_{1\sim N} $，现要将其分成 $ M （ （ （ M\leq N $）段，并要求每段连续，且每段和的最大值最小。
关于最大值最小：
例如一数列 $ 4\ 2\ 4\ 5\ 1 $ 要分成 $ 3 $ 段。
将其如下分段：
$ [4\ 2][4\ 5][1] $
第一段和为 $ 6 $，第 $ 2 $ 段和为 $ 9 $，第 $ 3 $ 段和为 $ 1 $，和最大值为 $ 9 $。
将其如下分段：
$ [4][2\ 4][5\ 1] $
第一段和为 $ 4 $，第 $ 2 $ 段和为 $ 6 $，第 $ 3 $ 段和为 $ 6 $，和最大值为 $ 6 $。
并且无论如何分段，最大值不会小于 $ 6 $。
所以可以得到要将数列 $ 4\ 2\ 4\ 5\ 1 $ 要分成 $ 3 $ 段，每段和的最大值最小为 $ 6 $。
输入格式
第 $ 1 $ 行包含两个正整数 $ N,M $。
第 $ 2 $ 行包含 $ N $ 个空格隔开的非负整数 $ A_i $，含义如题目所述。
输出格式
一个正整数，即每段和最大值最小为多少。
输入输出样例 #1
输入 #1
5 3
4 2 4 5 1
输出 #1
6
说明/提示
对于 $ 20% $ 的数据，$ N\leq 10 $。
对于 $ 40% $ 的数据，$ N\leq 1000 $。
对于 $ 100% $ 的数据，$ 1\leq N\leq 10^5 ， ， ， M\leq N ， ， ， A_i < 10^8 $， 答案不超过 $ 10^9 $。
解题思路:就是输入的时候找到数组中最大值还有数组的和,然后进行一下二分,如果为数组最大值,遍历一遍,看是否刚刚能够构成最大值最小的组合
#include<bits/stdc++.h>
using namespace std;
int n, m, r, l,a[100001];
bool isTrue(int x) {int num = 0, total = 0;for (int i = 1; i <= n; i++) {if (total + a[i] <= x)total += a[i];else{total = a[i];num++;}}return num < m;
}
int main() {cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> a[i];l = max(l, a[i]);r += a[i];}while (l <= r) {int mid = (l + r) / 2;if (isTrue(mid))r = mid - 1;else l = mid+1;}cout << l;return 0;
}