Minimum Sum(二分+RMQ查找下标) AtCoder Grand Contest 005

本文主要是介绍Minimum Sum(二分+RMQ查找下标) AtCoder Grand Contest 005，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Minimum Sum

题目描述

输入

输出

样例输入

3
2 1 3

样例输出

9

题意：给出n个数，找出所有L（1~n）----R（L~n）的最小值的和。

按一般的想法来做，要用3层for循环这样肯定超时。

先找出从1-n之间的最小值，记住下标i，那么这一个最小值就会被用到（i-L+1）*（R-i+1）次，之后把这个数组从最小值哪里分成两个新的数组，之后再重复之前的过程。

这个过程和快速排序的过程类似。

然后每一次找最小值下标时如果直接找也会超时，这时候就要用到RMQ算法了。

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
ll a[200105];
ll sum=0;
int d[200105][35],n;void init()
{int i,j;for(i=0;i<n;i++)d[i][0]=i;for(j=1;(1<<j)<=n;j++)for(i=0;i+(1<<j)-1<n;i++)d[i][j]=a[d[i][j-1]] < a[d[i+(1<<(j-1))][j-1]]? d[i][j-1]:d[i+(1<<(j-1))][j-1];
}
int RMQ_indx_min(int s,int v)
{int k=(int)(log((v-s+1)*1.0)/log(2.0));return a[d[s][k]]<a[d[v-(1<<k)+1][k]]? d[s][k]:d[v-(1<<k)+1][k];
}void dfs(int l,int r)
{if(l==r){sum+=(ll)a[l];return ;}int minn=RMQ_indx_min(l,r);sum=sum+(ll)(minn-l+1)*(r-minn+1)*a[minn];if(l<=minn-1)dfs(l,minn-1);if(r>=minn+1)dfs(minn+1,r);
}
int main (){scanf("%d",&n);for(int i=0;i<n;i++)scanf("%lld",&a[i]);init();dfs(0,n-1);printf("%lld\n",sum);return 0;
}

这篇关于Minimum Sum(二分+RMQ查找下标) AtCoder Grand Contest 005的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---