牛客网OJ题解--20210203
牛牛的朋友
https://ac.nowcoder.com/acm/problem/21545
本系列记录翀翀😐痛苦的刷题日志，所有题目均来自于牛客网OJ题目，坚持刷题谈起来容易做起来难，希望我可以坚持下去，这里仍然分享一段励志文案：每个人都有梦想，然而有些人把梦想变成了现实，有些人的梦想依旧是梦想，只因为他们为梦想付出的努力程度不一样，他们坚持的时间不一样，最终才有这样的结果。
NC21545-牛牛的朋友
题目链接
https://ac.nowcoder.com/acm/problem/21545
题目描述
牛牛有一群牛友，每只小牛都站在坐标轴上的某个位置，这群牛友很听牛牛的话，每当牛牛做个手势，每只小牛都会移动恰好X个单位的距离，要么向左，要么向右，现在告诉你每只小牛在移动前的位置，求移动之后最左边的牛与最右边的牛的最小距离。
第一行输入一个整数n (1 ≤ n ≤ 50)，表示牛的数量
第二行输入n个数pi (-1e8 ≤ pi ≤ 1e8)，表示每只牛的位置
第三行输入一个整数X (0 ≤ X ≤ 1e8)
测试样例
样例1
输入
3 -3 0 1 3
输出
3
样例2
输入
3 4 7 -7 5
输出
4
样例3
2 -100000000 100000000 100000000
输出
0
样例4
输入
9 3 7 4 6 -10 7 10 9 -5 7
输出
7
样例5
输入
4 -4 0 4 0 4
输出
4
样例6
输入
1 7 0
输出
0
解题思路
我们知道距离肯定是要缩小的，那么起初最左边的牛肯定是要向右走的，最右边的牛肯定是要向左走的。那么接下来我们枚举每一个中间就i的情况，假设向右走，那么在他左边的牛即使也向右走了，也不会比第i头牛的位置更靠右，而对于i+1向左走，那么i+1右边的牛也都向左走即可，因为这样最靠左的位置一定是第i+1头牛的位置。这样我们每次都计算出移动后的距离，选取最小距离的即可。
解题代码
#include <bits/stdc++.h>
using namespace std;
int arr[55];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> arr[i];
}
sort(arr + 1, arr + 1 + n); //要将初始位置从左到右排序
int x;
cin >> x;
int cnt = arr[n] - arr[1];
int left, right;
for (int i = 1; i < n; i++)
{
//i右边的所有牛左移，i自身以及i左边的所有牛右移
//那么最左边界值只能在1右移和i作业之间产生
left = min(arr[1] + x, arr[i + 1] - x);
//那么最右边界值只能在1右移和i作业之间产生
right = max(arr[n] - x, arr[i] + x);
if (right - left < cnt)
//如果距离更短，更新
{
cnt = right - left;
}
}
cout << cnt << endl;
system("pause");
return 0;
} NC16694-一元三次方程求解
题目链接
https://ac.nowcoder.com/acm/problem/16694
题目描述
有形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值 ≥ 1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。
提示：记方程f(x) = 0，若存在2个数x1和x2，且x1 < x2，f(x1)*f(x2) < 0，则在(x1，x2)之间一定有一个根。输入样例为a,b,c,d。
测试样例
输入
1 -5 -4 20
输出
-2.00 2.00 5.00
解题思路
就是按照题干说的思路，不断二分查找即可。当然貌似本体暴力枚举+0.01也可以过。一定要注意将变量声明为double,否则除出来是整数。
解题代码
#include <bits/stdc++.h>
using namespace std;
//找到的零点个数
int num = 0;
double a, b, c, d;
double f(double x)
{
//带入x计算
return a * x * x * x + b * x * x + c * x + d;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0);
cin >> a >> b >> c >> d;
//逐一尝试
for (double i = -100.00; i < 100.00; i++)
{
//二分法查找i~i+1内是否有0点
if (f(i) * f(i + 1) <= 0)
{
//可能i是0点
if (f(i) == 0)
{
cout << fixed << setprecision(2) << i << " ";
num++;
}
//或者i+1是0点，但是i和i+1不可能都是0点，题干说的
else if (f(i + 1) == 0)
{
//保留两位小数
cout << fixed << setprecision(2) << i + 1 << " ";
i++;
num++;
}
else
{
//或者在i和i+1区间内
double l = i, r = i + 1;
double m = (l + r) / 2;
//不断二分直至题干要求的精度
while (r - l >= 0.01)
{
if (f(l) * f(m) <= 0)
{
r = m;
}
else
{
l = m;
}
m = (l + r) / 2;
}
cout << fixed << setprecision(2) << m << " ";
num++;
}
}
//找到3个了就退出
if (num >= 3)
{
cout << endl;
break;
}
}
system("pause");
return 0;
} 
