题目描述：
在x轴上有n个人，每个人有一个移动速度 vi, 现在需要找一个地方让大家聚到一起开会，问你最少需要多少时间才可以让所有人都到达同一个点
输入格式：
第一行输入一个整数n
第二行输入n个整数
xi 表示每个人初始的位置
第三行输入n个整数
vi 表示每个人的移动速度
输出格式：
输出一个浮点数，保留五位小数，四舍五入。比如答案为2.333336，就输出2.33334
样例输入1：
3
7 1 3
1 2 1
样例输出1：
2.00000
样例输入2：
10
2 3 5 7 11 13 17 19 23 29
6 5 4 3 2 1 2 3 4 5
样例输出2：
2.75000
大家可以给个思路么？
这道题目是求所有人都到达同一个点的最短时间。
思路：
1.先求出初始位置的最大值和最小值。
2.再求出所有人移动速度的最大值。
3.最后用 (最大位置 - 最小位置) ÷ 最大移动速度 即为所有人到达同一点的最短时间。
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=1e5+10;
int n,p[N],v[N];
double dfs(double x)
{
double l=1e9,r=-1e9;
for(int i=0;i<n;i++)
{
l=min(l,p[i]+v[i]*x);
r=max(r,p[i]+v[i]*x);
}
return (r-l)/2.0;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>p[i];
for(int i=0;i<n;i++) cin>>v[i];
double l=0,r=1e9;
while(r-l>1e-5)
{
double mid=(l+r)/2.0;
if(dfs(mid)<=0) r=mid;
else l=mid;
}
printf("%.5f",r);
return 0;
}
话不多说，上代码
include<iostream>
#include<cmath>
using namespace std;
int main() {
int n;
cin>>n;
double a[n],b[n];
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++) cin>>b[i];
double sum=0;
for(int i=0;i<n;i++) sum+=(a[i]*b[i]);
double res=sum/n;
cout<<fixed<<setprecision(5)<<res<<endl;
return 0;
}
话不多说，先上思路
假设我们用时 t
那么每个人所能走到的范围就确定了，即为 pos[i] - t * v[i] ~ pos[i] + t * v[i]
那么，如果这个 t 是一个可行的值，那么，所有线段一定有公共部分。
而且因为 t 越长，范围越大，越可能相交，所以满足单调性，可以二分求解。
望 采纳
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
const double eps = 1e-5;
int n;
int pos[N + 5],v[N + 5];
bool check(double mid) {
double min_r = 1e18;
for(int i = 1;i <= n;i++)
min_r = min(min_r,pos[i] + mid * v[i]);
for(int i = 1;i <= n; i++)
if (pos[i] - mid * v[i] > min_r)
return false;
return true;
}
int main() {
double l = 0,r = 1e18;
scanf("%d",&n);
for(int i = 1;i <= n;i++)
scanf("%d",&pos[i]);
for(int i = 1;i <= n;i++)
scanf("%d",&v[i]);
while(r - l >= eps) {
double mid = (l + r) / 2;
if (check(mid)) {
r = mid;
} else {
l = mid;
}
}
printf("%.5lf",l);
return 0;
}
参考一下https://blog.csdn.net/linjiayina/article/details/104038784
思路：
首先，需要定义一个变量来存储最终的时间。
然后，需要两重循环来计算每个人的位置、速度和最小时间，
然后，可以使用if条件语句来比较每个人的位置和最小时间
最后，可输出最终的最小时间
代码：
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
int x[n], v[n];
for(int i=0;i<n;i++)
cin >> x[i];
for(int i=0;i<n;i++)
cin >> v[i];
double minTime = 0;
for(int i=0;i<n;i++) {
for(int j=i+1;j<n;j++) {
if(x[i]/v[i] < x[j]/v[j]) {
minTime = max(minTime, (x[j]-x[i])/v[i]);
} else {
minTime = max(minTime, (x[i]-x[j])/v[j]);
}
}
}
cout << fixed << setprecision(5) << minTime;
return 0;
}
可以参考下面的代码,可以的画 请点击”采纳“：
#include<iostream>
#include<cmath>
using namespace std;
const int N=1010;
int n;
double x[N],v[N];
double check(double t)
{
double l=0,r=0;
for(int i=0;i<n;i++)
{
l=min(l,x[i]-v[i]*t);
r=max(r,x[i]+v[i]*t);
}
return (r-l)/2;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>x[i];
for(int i=0;i<n;i++) cin>>v[i];
double l=0,r=1e9;
while(r-l>1e-5)
{
double mid=(l+r)/2;
if(check(mid)<0) r=mid;
else l=mid;
}
printf("%.5lf",l);
return 0;
}