NC24267. [USACO 2019 Feb P]Cow Dating
描述
Bessie, in searching for a partner to the Valentine’s Day Barn Dance, has decided to try out this site. After making her account, FJ’s algorithm has given her a list of N possible matches (1≤N≤10^6). Going through the list, Bessie concludes that each bull has probability pi (0<pi<1) of accepting an invitation from her for the dance.
Bessie decides to send an invitation to each bull in a contiguous interval of the list. Virtuous as always, she wants exactly one partner. Please help Bessie find the maximum probability of receiving exactly one accepted invitation, if she chooses the right interval.
输入描述
The first line of input contains N (1≤N≤10^6). Each of the remaining N lines contain 10^6 times pi, which is an integer.
In at least 25% of the test cases, it is further guaranteed that N≤4000.
输出描述
Print 10^6 times the maximum probability of receiving exactly one accepted invitation, rounded down to the nearest integer.
示例1
输入:
3 300000 400000 350000
输出:
470000
说明:
The maximal probability results from selecting the interval from the 2nd to the 3rd cow.C++ 解法, 执行用时: 380ms, 内存消耗: 8264K, 提交时间: 2023-08-22 14:52:01
#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
double tmp1 = 1, tmp2 = 0, ans = 0, p[N];
int main() {
ios :: sync_with_stdio(false);
int n, t, i;
cin >> n;
for (i = 1; i <= n; ++i) {
cin >> p[i]; p[i] /= (1e6 * 1.0);
ans = max(ans, p[i]);
}
t = 1;
for (i = 1; i <= n; ++i) {
while (t <= n && tmp1 * tmp2 < tmp1 * (1 - p[t]) * (tmp2 + p[t] / (1 - p[t]))) {
tmp1 *= (1 - p[t]); tmp2 += p[t] / (1 - p[t]); ++t;
}
ans = max(ans, tmp1 * tmp2);
tmp1 /= (1 - p[i]); tmp2 -= p[i] / (1 - p[i]);
}
cout << (int)(ans * 1e6) << endl;
return 0;
}