因为只能带一个, 买卖价格又一样, 所以只要右边的比左边的大, 就从这买下来然后带到下一个卖掉就行了 (我想到别处再卖的话大不了再重新买回来嘛)
所以给 max(w[i]-w[i-1],0) 维护一个前缀和就行了
- #include<bits/stdc++.h>
- #define pa pair<int,int>
- #define CLR(a,x) memset(a,x,sizeof(a))
- using namespace std;
- typedef long long ll;
- const int maxn=1e6+10;
- inline ll rd(){
- ll x=0;char c=getchar();int neg=1;
- while(c<'0'||c>'9'){if(c=='-') neg=-1;c=getchar();}
- while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
- return x*neg;
- }
- int N,M;
- ll s[maxn];
- int main(){
- //freopen(".in","r",stdin);
- int i,j,k;
- N=rd();
- for(i=2,j=rd();i<=N;i++){
- k=rd();
- s[i]=s[i-1]+max(k-j,0);
- j=k;
- }M=rd();
- for(i=1;i<=M;i++){
- int l=rd(),r=rd();
- printf("%lld\n",s[r]-s[l]);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2805335.html