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;
}