cf 700 A As Fast As Possible

题意：有$n$个小学生需要到距离为$l$的地方去，步行的速度是$v_1$，它们租了一辆大巴，速度是$v_2$，大巴上最多容纳$k$个乘客，每个小学生最多乘车一次，初始时大巴和小学生都在起点，问至少需要多长时间所有小学生都可以到达终点。时间精确到$10^{-6}$。数据范围$1 \leq l \leq 1e9, 1 \leq v_1 < v_2 \leq 1e9, 1 \leq k \leq n$。

分析：你可能会想到用大巴把小学生送到终点再折回，如此反复，直到最后一次不折回。但是样例$2$提示我们这种贪心不是最优的，大巴不一定要把小学生送到终点，因此考虑二分时间，那么假设时间$t$内可以完成目标，可以导出每个小学生的乘车距离最少是$\frac{v_2(l-v_1t)}{v_2-v_1}$，并且大巴需要折回至少$\frac{n}{ k }- [n \mod k = 0]$次，于是根据这两个信息得出最小花费时间与$t$作比较即可完成二分。代码如下：

 #include <algorithm>
 #include <cstdio>
 #include <cstring>
 #include <string>
 #include <queue>
 #include <map>
 #include <set>
 #include <stack>
 #include <ctime>
 #include <cmath>
 #include <iostream>
 #include <assert.h>
 #pragma comment(linker, "/STACK:102400000,102400000")
 #define max(a, b) ((a) > (b) ? (a) : (b))
 #define min(a, b) ((a) < (b) ? (a) : (b))
 #define mp std :: make_pair
 #define st first
 #define nd second
 #define keyn (root->ch[1]->ch[0])
 #define lson (u << 1)
 #define rson (u << 1 | 1)
 #define pii std :: pair<int, int>
 #define pll pair<ll, ll>
 #define pb push_back
 #define type(x) __typeof(x.begin())
 #define foreach(i, j) for(type(j)i = j.begin(); i != j.end(); i++)
 #define FOR(i, s, t) for(int i = (s); i <= (t); i++)
 #define ROF(i, t, s) for(int i = (t); i >= (s); i--)
 #define dbg(x) std::cout << x << std::endl
 #define dbg2(x, y) std::cout << x << " " << y << std::endl
 #define clr(x, i) memset(x, (i), sizeof(x))
 #define maximize(x, y) x = max((x), (y))
 #define minimize(x, y) x = min((x), (y))
 using namespace std;
 typedef long long ll;
 const int int_inf = 0x3f3f3f3f;
 const ll ll_inf = 0x3f3f3f3f3f3f3f3f;
 ) - );
 const double double_inf = 1e30;
 ;
 typedef unsigned long long ul;
 typedef unsigned int ui;
 inline int readint(){
     int x;
     scanf("%d", &x);
     return x;
 }
 inline int readstr(char *s){
     scanf("%s", s);
     return strlen(s);
 }

 class cmpt{
 public:
     bool operator () (const int &x, const int &y) const{
         return x > y;
     }
 };

 int Rand(int x, int o){
     //if o set, return [1, x], else return [0, x - 1]
     ;
     int tem = (int)((double)rand() / RAND_MAX * x) % x;
      : tem;
 }
 ll ll_rand(ll x, int o){
     ;
     ll tem = (ll)((double)rand() / RAND_MAX * x) % x;
      : tem;
 }

 void data_gen(){
     srand(time());
     freopen("in.txt", "w", stdout);
     ;
     printf("%d\n", kases);
     while(kases--){
         ll sz = 1e18;
         printf());
     }
 }

 struct cmpx{
     bool operator () (int x, int y) { return x > y; }
 };
 double power(double a, int p){
     .;
     while(p){
         ) ans *= a;
         p >>= ;
         a = a * a;
     }
     return ans;
 }
 int main(){
     //data_gen(); return 0;
     //C(); return 0;
     ;
     if(debug) freopen("in.txt", "r", stdin);
     //freopen("out.txt", "w", stdout);
     int n, l, v1, v2, k;
     while(~scanf("%d", &n)){
         l = readint(), v1 = readint(), v2 = readint(), k = readint();
         );
         double L = (double)l / v2, R = (double)l / v1;
         ){
             //printf("%.10f %.10f\n", L, R);
             //printf("err is %.10f\n", R - L);
             ;
             //printf("mid is %.10f\n", mid);
             double d = (double)v2 * (l - v1 * mid) / (v2 - v1);
             . * d * v1 * lamda / (v1 + v2) + d;
             ;
             ;
             if(ok){
                 . * d * lamda / (v1 + v2);
                 rhs += (l - lhs + d) / v2;
                 ;
             }
             if(ok) R = mid;
             else L = mid;
         }
         //if(n % k) ans += d / v2;
         printf("%.10f\n", L);
     }
     ;
 }

code：

这里还需要注意二分的精度不能太高，否则可能由于浮点误差跳不出循环。

巴特西

cf 700 A As Fast As Possible

最新文章

热门文章