关注
楼上大佬单调栈解法太强了
能不能帮忙看看我的代码是否可行,应该是O(nlogn)的复杂度。
dp[i]表示 以i为结尾的子序列的最大值的和
const int maxn = 1e5+7;
typedef long long ll;
int pos[maxn];
int val[maxn*10];
ll dp[maxn*10];
int max_pos(int s, int e)
{
if(s > e) return -1;
if(s == e) return pos[s];
int mid = s + (e-s)/2;
int l = max_pos(s,mid);
int r = max_pos(mid+1,e);
return l > r ? l : r;
}
int main()
{
int n;
while(~scanf("%d",&n)) {
int mx = -1;
for(int i = 0;i < n;i ++) {
scanf("%d",val+i);
mx = max(mx,val[i]);
}
double sum = 0;
memset(pos,-1,sizeof(pos));
for(int i = 0;i < n;i ++) {
int p = max_pos(val[i]+1,mx);
pos[val[i]] = i;
if(p == -1) dp[i] = val[i] * 1LL * (i-p);
else dp[i] = dp[p] + val[i] * 1LL * (i-p);
sum += dp[i];
}
sum = 2*sum / ((n+1) * n);
printf("%.6lf\n",sum);
}
return 0;
}
查看原帖
点赞 评论
相关推荐
_mos_:估计面试官在美国

点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 26届的你们有几段实习? #
34560次浏览 396人参与
# 打工人的工作餐日常 #
50280次浏览 378人参与
# 你被哪些公司秒挂过? #
26158次浏览 221人参与
# 月薪多少能在一线城市生存 #
17628次浏览 231人参与
# 如何提高实习转正率? #
9961次浏览 147人参与
# 你后悔自己读研吗? #
14112次浏览 214人参与
# 你认为哪些项目算烂大街? #
13926次浏览 256人参与
# 你以为的实习VS真实的实习 #
19418次浏览 181人参与
# 当下环境,你会继续卷互联网,还是看其他行业机会 #
116368次浏览 804人参与
# 双非能在秋招上岸吗? #
220110次浏览 1165人参与
# 追觅科技求职进展汇总 #
17276次浏览 119人参与
# 最难的技术面是哪家公司? #
7797次浏览 67人参与
# 机械校招之路总结 #
93098次浏览 1891人参与
# 哪些公司真双非友好? #
14407次浏览 80人参与
# 找工作时的取与舍 #
82063次浏览 587人参与
# 网申一定要掌握的小技巧 #
10270次浏览 66人参与
# 拼多多求职进展汇总 #
648661次浏览 5185人参与
# 海康威视求职进展汇总 #
489135次浏览 3619人参与
# 你小时候最想从事什么职业 #
103967次浏览 1787人参与
# 产品实习,你更倾向大公司or小公司 #
159101次浏览 1963人参与