题目链接:

-------------------------------------------------------------------------------------------

大概看一下发现题目给了一些条件限制 然后要解一个方程组

不过数据范围很大 如果直接去解的话显然很困难

考虑到此题是建立在概率的模型上的 因此我们可以用前缀和的方式先把输入处理一下

 

然后就转化为以下子问题

$0 <= x_1, y_1, x_2, y_2 <= 1$

$x_1 * y_1 = a$

$x_2 * y_2 = b$

$x_1 + x_2 = 1$

$y_1 + y_2 = 1$

给定$a\ b$求解$x_1\ x_2\ y_1\ y_2$

 

在草稿纸上画画我们可以发现此处是可以三分的

不过继续观察下我们可以限定所有的$y_i <= x_i$

于是就可以写更为简单的二分了

并且在这个限定条件下 每次求出的解实际上是相互独立的

因此对于每一对解 我们都可以通过二分处理

这样这题就以$O(nlog(10^6))$愉快地解决了

 

1 #include 
     
       2 using namespace std; 3 const int N = 1e5 + 10; 4 double p1[N], p2[N]; 5 double ans1[N], ans2[N]; 6 int n; 7 int main() 8 { 9     scanf("%d", &n);10     for(int i = 1; i <= n; ++i)11         scanf("%lf", &p1[i]);12     for(int i = 2; i <= n; ++i)13         p1[i] += p1[i - 1];14     for(int i = 1; i <= n; ++i)15         scanf("%lf", &p2[i]);16     for(int i = n - 1; i; --i)17         p2[i] += p2[i + 1];18     for(int i = 1; i < n; ++i)19     {20         double L, R, mid;21         int t = 0;22         L = max(sqrt(p1[i]), ans1[i - 1]);23         R = 1;24         while(++t <= 30)25         {26             mid = (L + R) / 2;27             if((1 - mid) * (1 - p1[i] / mid) <= p2[i + 1])28                 R = mid;29             else30                 L = mid;31         }32         ans1[i] = R;33         ans2[i] = p1[i] / R;34     }35     ans1[n] = ans2[n] = 1;36     for(int i = n; i > 1; --i)37     {38         ans1[i] -= ans1[i - 1];39         ans2[i] -= ans2[i - 1];40     }41     for(int i = 1; i <= n; ++i)42         printf("%.8f%c", ans1[i], i != n ? ' ' : '\n');43     for(int i = 1; i <= n; ++i)44         printf("%.8f%c", ans2[i], i != n ? ' ' : '\n');45     return 0;46 }