首页 > 其他 > 详细

数学+栈/列+思维——namomo round c

时间:2020-07-09 12:33:21      阅读:52      评论:0      收藏:0      [点我收藏+]

最近做的一道很好的题目,感觉很需要直觉才能想到

/*
转化:将a[]转化成差分数组
那么原来的操作[l,r]就变成了a[l]-1,a[r+1]+1
最后的目标是将这个数组的所有元素变成0
为了使操作次数最小,只有两种操作:在正数上的-1操作,在负数上的+1操作,    
                                  并且差分数组每个前缀和必须保持为非负 
(这个结论在差分数组上很容易得出,但是在原数组上就比较难看出来。。)
2 0 2 0 2 _ 最后一个用来占位,代表0 
2 -2 2 -2 2 -2
那么我们就可以推出,代价必定为 sum{(ri-li)^2} = sum{ri^2} + sum{li^2} - sum{2*ri*li}
要求最大代价,那么sum{2*ri*li}要最小,所以用栈维护正数 
要求最小代价,那么sum{2*ri*li}要最大,所以用队列维护正数 
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define mod 1000000007 
#define N 500005
#define fr front()
#define tp top()

ll n,a[N],sum,b[N],base;

void solvemin(){//sum{2*ri*li}最大 
    for(int i=0;i<=n+1;i++)b[i]=a[i];
    queue<ll>q;
    for(int i=1;i<=n+1;i++)    {
        if(b[i]>0)q.push(i);
        else {
            while(abs(b[i])){
                if(abs(b[i])<b[q.fr]){
                    sum=(sum+2ll*q.fr*i%mod*abs(b[i])%mod)%mod;
                    b[q.fr]-=abs(b[i]);b[i]=0;
                    break;
                }
                sum=(sum+2ll*q.fr*i%mod*b[q.fr]%mod)%mod;
                b[i]+=b[q.fr];b[q.fr]=0;
                q.pop();
            }
        }
    }
}
void solvemax(){//sum{2*ri*li}最小 
    for(int i=0;i<=n+1;i++)b[i]=a[i];
    stack<ll>s;
    for(int i=1;i<=n+1;i++){
        if(b[i]>0)s.push(i);
        else {
            while(abs(b[i])){
                if(abs(b[i])<b[s.tp]){
                    sum=(sum+2*s.tp*i%mod*abs(b[i])%mod)%mod;
                    b[s.tp]-=abs(b[i]);b[i]=0;
                    break; 
                }
                sum=(sum+2*s.tp*i%mod*b[s.tp]%mod)%mod;
                b[i]+=b[s.tp];b[s.tp]=0;
                s.pop();
            }
        }
    }
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=n+1;i>=1;i--){
        a[i]=a[i]-a[i-1];
        base=(base+abs(a[i])*i%mod*i%mod)%mod;
    }
    solvemin();cout<<(base-sum+mod)%mod<< ;sum=0;
    solvemax();cout<<(base-sum+mod)%mod<<\n;sum=0;
} 

 

数学+栈/列+思维——namomo round c

原文:https://www.cnblogs.com/zsben991126/p/13272895.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!