【推导】Codeforces Round #364 (Div. 2) D. As Fast As Possible

一种方法是二分总时间,复杂度O(nlogn)。

另外我们可以证明,当所有人同时到达终点的时候,是最优的,因为没有人的时间“浪费”了。

我们又发现,每个人的运动过程总是两段,要么是走路,要么是坐车。于是每个人的运动都是等价的(坐车的时间也相等,走路的时间也相等)。

这里借用一下这个推导,懒得写了。

(http://blog.csdn.net/say_c_box/article/details/52001850)

根据上面的过程得出d以后,于是有d*(组数-1)+l1=l,然后就可以解出l1,然后l1/v2+(l-l1)/v1就是答案,因为每个人的运动过程相同,我们只需要算第一组人的运动总时间即可。

#include<cstdio>
using namespace std;
int n,K;
double l,v1,v2;
int main(){
	while(scanf("%d%lf%lf%lf%d",&n,&l,&v1,&v2,&K)!=EOF){
		int zu=n/K+(n%K ? 1 : 0);
		double l1=l*(v1+v2)/(2.0*v1*((double)zu-1.0)+v1+v2);
		printf("%.10f\n",l1/v2+(l-l1)/v1);
	}
	return 0;
}
时间: 07-03

【推导】Codeforces Round #364 (Div. 2) D. As Fast As Possible的相关文章

!Codeforces Round #364 (Div. 2) C. They Are Everywhere

https://codeforces.com/contest/701/problem/C binary search strings two pointers #include<bits/stdc++.h> using namespace std; const int N=1e5+5; char s[N]; int main(){ int n,tot=0; cin>>n; getchar(); map<char,int>cnt; for(int i=1;i<=n;

Codeforces Round #364 (Div. 2) ABCDE

A. Cards 题解: 目的是将n个数分成n/2个人,每个人2个,要求和一样,保证有解 排序一下再选取就行了 代码: #include<bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define se second #define fs first #define ll long long typedef pair<int,int> P; const int INF=1

Codeforces Round #364 (Div. 1) 700B(树)

题目大意 在n颗结点的树上有2k个需要配对的点,把他们两两配对,使得路程和最大并输出 选取一个点v lv表示v与父亲的边 那么考虑lv被经过的次数,对于一个最大的情况,lv应该为min(sv, 2*k - sv) ,其中sv是v子树中需要配对的点(包括v) 假如lv比这个值小,那么必定有a和b在v的子树外,c和d在子树内,它们分别配对 但是如果这样的话,让a和c配对,b和d配对,显然更优 所以lv只能等于min(sv, 2*k - sv) 最后输出所有点的这个值的和即可 #include <io

Codeforces Round #364 (Div. 2) - A B C

A - Cards /* 题意 : 有 n 张牌 ,每张牌都有一个数值 ,分给 n/2 个人 ,每个人手中的牌的数值加起来要相等, 一张牌只可分一个人. ( n 是偶数 ,且题目保证答案存在 ) 输出每个人手中的 牌的编号 . 解题 : 结构体存下牌的数值和编号,然后 sort 一下,从两边输出就好辣(因为答案保证存在). */ #include<cstdio> #include<cstring> #include<algorithm> #include<iost

Codeforces Round #364 (Div. 2)

还是4个1a 记录代码 A 1 //#define txtout 2 //#define debug 3 #include<bits/stdc++.h> 4 #define mt(a,b) memset(a,b,sizeof(a)) 5 using namespace std; 6 typedef long long LL; 7 const double pi=acos(-1.0); 8 const double eps=1e-8; 9 const int inf=0x3f3f3f3f; 10

Codeforces Round #364 (Div. 2) C

Description Sergei B., the young coach of Pokemons, has found the big house which consists of n flats ordered in a row from left to right. It is possible to enter each flat from the street. It is possible to go out from each flat. Also, each flat is

Codeforces Round #364 (Div. 1)B. Connecting Universities

题目链接:传送门 题目大意:n个点构成一棵树,给定 k*2 点,要分成 k 组,使每组点之间的距离之和最大. 题目思路:因为是求距离之和最大,所以我们可以知道这样一个性质.如果以一条边为界,两边的子树均有给定的点,则这条边一定会经过 min(左边的给定点数,右边的给定点数)次. 那么这条边的贡献就是经过的次数. #include <iostream> #include <cstdio> #include <cstdlib> #include <cmath>

Codeforces Round #364 (Div. 2) B

Description Vasya has the square chessboard of size n × n and m rooks. Initially the chessboard is empty. Vasya will consequently put the rooks on the board one after another. The cell of the field is under rook's attack, if there is at least one roo

codeforces 700a//As Fast As Possible// Codeforces Round #364(Div. 1)

题意:n个人要运动ll长,有个bus带其中几个人,问最短时间 最后所有人在同一时间到终点是用时最少的.由于搭bus相当于加速,每个人的加速时间应该一样.先计算bus走过的路程route.看第一个人被搭t分钟(也就是所有人以后都搭t分钟),剩余的人走t分钟,route+=v2*t.bus到了v2*t的位置,人在v1*t的位置.bus回去接人,被接的人继续前进.route2=(v2*t-v1*t)/(v1+v2)*v2(相向而行).接到人后再走v2*t,结果就是这样往复.最后一次不回头.如果要接a次