首页 > 代码库 > 51nod 1215 数组的宽度
51nod 1215 数组的宽度
题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1215
题意：
分析：
计算出每一个数字作为最大值，最小值的范围；
然后结果就是乘法原理，因为，左右端点可以任意组合；
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 int n; 6 const int maxn = 5e4+10; 7 struct num { 8 long long value; 9 int maxleft,maxright;10 int minleft,minright;11 num():maxleft(1),maxright(1),minleft(1),minright(1){}12 }a[maxn];13 14 stack<pair<int,int> > S;15 16 17 void getMax()18 {19 while(!S.empty())20 S.pop();21 S.push(make_pair(a[0].value,0));22 for(int i=1;i<n;i++) {23 while(!S.empty()&&S.top().first<=a[i].value) {24 //int value = http://www.mamicode.com/S.top().first;25 int key = S.top().second;26 S.pop();27 28 a[i].maxleft +=a[key].maxleft;29 if(!S.empty()) {30 a[S.top().second].maxright +=a[key].maxright;31 }32 }33 S.push(make_pair(a[i].value,i));34 }35 while(!S.empty()) {36 int key = S.top().second;37 S.pop();38 if(!S.empty()) {39 a[S.top().second].maxright +=a[key].maxright;40 }41 }42 }43 44 void getMin()45 {46 while(!S.empty())47 S.pop();48 S.push(make_pair(a[0].value,0));49 for(int i=1;i<n;i++) {50 while(!S.empty()&&S.top().first>=a[i].value) {51 //int value = http://www.mamicode.com/S.top().first;52 int key = S.top().second;53 S.pop();54 55 a[i].minleft +=a[key].minleft;56 if(!S.empty()) {57 a[S.top().second].minright +=a[key].minright;58 }59 }60 S.push(make_pair(a[i].value,i));61 }62 while(!S.empty()) {63 int key = S.top().second;64 S.pop();65 if(!S.empty()) {66 a[S.top().second].minright +=a[key].minright;67 }68 }69 }70 71 int main()72 {73 74 scanf("%d",&n);75 for(int i=0;i<n;i++)76 scanf("%lld",&a[i].value);77 getMax();78 getMin();79 80 long long ans = 0;81 for(int i=0;i<n;i++) {82 ans +=a[i].value*a[i].maxleft*a[i].maxright;83 ans -=a[i].value*a[i].minleft*a[i].minright;84 }85 cout<<ans<<endl;86 87 return 0;88 }
51nod 1215 数组的宽度
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。