http://bakapiano.site/statement.pdf

题目描述

Klee’s definition of playing is throwing explosives all over the place; she is particularly fond of “fish
blasting” — throwing bombs in lakes full of fish.
Today, Klee also plans to blast fish in Starfell Lake. There are n fish in Starfell Lake. Klee will use a bomb
with power x, then, every fish whose HP less than or equal to x will be blasted.
However, Klee doesn’t know HP of every fish. Instead, she only knows HP of the i-th fish is a uniformly
random real number in [li, ri]. Now, Klee wants to determine minimum possible x such that the expected
number of blasted fish is greater or equal to m.Your answer will be considered correct, if its absolute or relative error does not exceed 10−4.
More formally, if your answer is a and jury’s answer is b, your answer will be consideredcorrect if |a−b|max(1,b) ≤ 10−4
Input
The first line contains two integers n, m (1 ≤ m ≤ n ≤ 105) — the number of fish and Klee’s expection of
the number of blasted fish.
In the following n line, each line contains two real numbers li, ri (0 ≤ li ≤ ri ≤ 109), which means HP of
the i-th fish will be a random real number in [li, ri].
Output
Output minimum possible x such that the expected number of blasted fish is greater or equal to m.

样例

输入 :2 1
-------1.4 2.8
-------1.4 2.8

输出 :2.1000000000

样例解释： 两条鱼的HP 在 一下区间 目标是炸1条鱼 （2.1 - 1.4）/(2.8 - 1.4) + (2.1 - 1.4) / (2.8 - 1.4) == 1

题目的大意就是 为炸m条鱼 我最少需要放多少炸药

分析后 为 浮点数二分 但是当时不知道咋想的 一直 有一组样例出不来

1 1

0 1000000000 正确答案输出1000000000 但是当时写的程序就是出不来 以为是超过了double 的范围

一直改 一直改 到最后才发现 while(l - r > []) 取得精度过高

并且check函数 没有写对。。。 真是傻

此外之前写的 long double 更能提高精度 double 精度范围为16位

long double 输入为 long double c = 0; scanf(“%Lf”, &c); printf(“%Lf”,c);

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>
#include<iomanip>

using namespace std;
typedef pair < double ,double> PII;
const int maxn = 1e5 + 10;
PII a[maxn];int n;
double m ;//目标值m
bool cmp(PII A, PII B)
{
    return A.first < B.first;
    return A.second < B.second;
}
bool check(double mid)
{
    double res = 0;
    for(int i = 1 ; i <= n ; i ++)  
    {
        double fenmu = mid - a[i].first;
        double fenzi = a[i].second - a[i].first;//  0

        if(mid >= a[i].second)
        res += 1.0;
        else if(mid < a[i].first)
        res += 0;
        else if(fenmu >= 0)
        res += (fenmu) / (fenzi);     
    }
    if(res >= m * 1.0)
    return true;
    else
    return false;
}
int main()
{
    scanf("%d %lf", &n, &m);
    for(int i = 1 ; i <= n ; i ++)
    scanf("%lf %lf",&a[i].first, &a[i].second);
    //sort(a + 1 , a + n + 1, cmp);
    double l = 0 , r = (1e9 + 1) * 1.0;
    while(r - l > 1e-6) /////////////////////////////////////////////////  之前写的 (l - r > 1e-10)
    {
        double mid = (r + l) / 2.0;
        if(check(mid)) r = mid;
        else l = mid ;
    }
    printf("%.13f\n",l);
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla