首页 > 代码库 > UESTC 1015 Lweb and pepper --前，后缀最值
UESTC 1015 Lweb and pepper --前，后缀最值
题意： n种食物，每种含花椒的概率为Pi，现在已经选择了[L,R]这个区间（下标）的食物，要再选一个，使总的食物只有一种含花椒的概率最大，问选哪个最好，相同的选下标小的。
解法： 就不写解法了。此处有官方题解： http://acm.uestc.edu.cn/bbs/read.php?tid=5835
维护一个前缀后缀的最值即可。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#define Mod 1000000007#define eps 1e-8using namespace std;#define N 100002int preMax[N],bacMax[N],preMin[N],bacMin[N];double pMax[N],pMin[N],bMax[N],bMin[N],p[N];int sgn(double x){ if(x < -eps) return -1; if(x > eps) return 1; return 0;}int main(){ int t,n,i,m,L,R; cin>>t; while(t--) { scanf("%d",&n); for(i=1;i<=n;i++) scanf("%lf",&p[i]); preMax[0] = 0; preMin[0] = 0; pMax[0] = -1; pMin[0] = Mod; bacMax[n+1] = n+1; bacMin[n+1] = n+1; bMax[n+1] = -1; bMin[n+1] = Mod; for(i=1;i<=n;i++) { preMax[i] = preMax[i-1]; preMin[i] = preMin[i-1]; pMax[i] = pMax[i-1]; pMin[i] = pMin[i-1]; if(p[i] > pMax[i]) pMax[i] = p[i], preMax[i] = i; if(p[i] < pMin[i]) pMin[i] = p[i], preMin[i] = i; } for(i=n;i>=1;i--) { bacMax[i] = bacMax[i+1]; bacMin[i] = bacMin[i+1]; bMax[i] = bMax[i+1]; bMin[i] = bMin[i+1]; if(p[i] >= bMax[i]) bMax[i] = p[i], bacMax[i] = i; if(p[i] <= bMin[i]) bMin[i] = p[i], bacMin[i] = i; } scanf("%d",&m); while(m--) { scanf("%d%d",&L,&R); L++,R++; double B = 1.0, E = 0.0; for(i=L;i<=R;i++) B *= (1-p[i]), E += p[i]/(1-p[i]); if(sgn(1-E) > 0) { if(pMax[L-1] >= bMax[R+1]) printf("%d\n",preMax[L-1]-1); else printf("%d\n",bacMax[R+1]-1); } else { if(pMin[L-1] <= bMin[R+1]) printf("%d\n",preMin[L-1]-1); else printf("%d\n",bacMin[R+1]-1); } } } return 0;}
UESTC 1015 Lweb and pepper --前，后缀最值
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。