F - leeing Sunlight (二分答案)

àì夳堔傛蜴生んèń 2022-10-21 11:51 77阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1a2VyNg_size_16_color_FFFFFF_t_70]  
代码：

#include<bits/stdc++.h>
    #define ios ios::sync_with_stdio(false);cin.tie(0)
    const double N = 1e9;
    const double esp = 1e-4;
    using namespace std;
    
    double f[1000005][2];
    int n, m;
    
    double check(double k)
    { 
        double sum = 0;
        for(int i = 1; i <= n; i++){ 
            if(k > f[i][1]) sum += 1.0; 
            else if(k > f[i][0]) sum += ((k-f[i][0]) / (f[i][1]-f[i][0]));
        }
        return sum < m;
    }
    
    double binary_ans()
    { 
        double l = 0;
        double r = N;
        while((r-l) > esp)
        { 
            double mid = (r + l) / 2;
                if(check(mid))
                    l = mid;
                else
                    r = mid;
        }
        return l;
        
    }
    
    int main()
    { 
    	ios;
        cin >> n >> m;
        // f[i][0] 区间左
    	// f[i][1] 区间右
        for(int i = 1; i <= n; i++)
            cin >> f[i][0] >> f[i][1];
        
        double ans = binary_ans();
        cout << ans << endl;
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1a2VyNg_size_16_color_FFFFFF_t_70]: /images/20221021/61978e55e9c34241bc533adb53208347.png

发表评论取消回复

表情：

评论列表（有 0 条评论，77人围观）

还没有评论，来说两句吧...

相关阅读

相关二分答案总结

二分的三种实现形式： 1.最普通的： while(l<=r){ int mid=l+r>>1; if(check(m

曾经终败给现在/ 2024年03月30日 09:30/ 0 赞/ 23 阅读

相关【二分答案】CF803 D

感觉之前的\1900好简单 [Problem - D - Codeforces][] 题意： ![47e9ce79fee54c63a55acba3cac6e937.pn

客官°小女子只卖身不卖艺/ 2024年03月23日 22:41/ 0 赞/ 10 阅读

相关【二分答案】CF1661 C

[Problem - C - Codeforces][] 题意： ![b7962e76b90c402e95ec6324c654b1fa.png][] 思路：在chec

小咪咪/ 2024年03月22日 20:25/ 0 赞/ 9 阅读

相关【反悔贪心+二分答案+枚举】Educational Codeforces Round 149 (Rated for Div. 2) F. Editorial for Two

[Problem - F - Codeforces][] 题意：给定一个长度为N的数列，问你所有长度为K的子序列中，将子序列分割成两部分，max(左半部分，右半部分）的最

小咪咪/ 2024年03月16日 09:24/ 0 赞/ 7 阅读

相关 P1873 砍树（二分答案）

[传送][Link 1] 这是个高精度的题，如何暴力枚举，会爆炸，用了一次二分和一次枚举，时间复杂度是 O ( n l o g ( n ) ) O(nlog(n)) O(nl

Dear 丶/ 2022年11月10日 14:20/ 0 赞/ 88 阅读

相关 F - leeing Sunlight (二分答案)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

àì夳堔傛蜴生んèń/ 2022年10月21日 11:51/ 0 赞/ 78 阅读

相关 codeforces D. Multiplication Table 二分答案

D. Multiplication Table time limit per test 1 second memory limit per test 256 megab

傷城~/ 2022年07月24日 08:19/ 0 赞/ 123 阅读

相关 php+mysql不连续关键字查找(搜索lee可以搜索出loele和lee等等)

处理关键字格式为： $str='12345'; $strArray=str_split($str); $str=join("%",$strArray)

爱被打了一巴掌/ 2022年05月18日 10:18/ 0 赞/ 64 阅读

相关二分答案学习笔记

内容先![1660941-20190626085335054-1727597896.png][] 等我多做些题在来写转载于:https://www.cnblogs.c

谁践踏了优雅/ 2021年11月02日 09:16/ 0 赞/ 256 阅读

相关 POJ 1064 Cable master（二分答案）

嗯... 题目链接：[http://poj.org/problem?id=1064][http_poj.org_problem_id_1064] 其实

骑猪看日落/ 2021年10月23日 17:56/ 0 赞/ 183 阅读