题解：P13095 炒股高手

chenyizhen · 2025-07-06 20:37:42 · 题解

题目：

对于每一份“鸡债” 计算其在 [s_{i},t_{i}] 内最大收益。

思路：

由于我们可以无限次的买卖，所以就可贪心一下，最优策略是在每一个价格上升的相邻两天（即 a_{i}<a_{i+1}）进行买入和卖出。

这样，总收益倍数等于所有上升段的收益倍数的乘积。这样对于对对数就是直接相加减（对数运算：底数相乘等于指数相加）。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
inline void read(int &a){
    char ch;int f=1,k=0;ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
    a=k*f;
}
int a[N],pre[N],n,m,k,s[N],t[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    read(n),read(m);
    for(int i=1;i<=n;i++){
        read(a[i]);
        pre[i]=pre[i-1];
        if(i>=2 and a[i]>a[i-1])
            pre[i]+=a[i]-a[i-1];
    }
    read(k);
    for(int i=1;i<=m;i++){
        read(s[i]),read(t[i]);
        cout<<k+pre[t[i]]-pre[s[i]]<<"\n";
    }
    return 0;
}

题解到此就结束了！祝各位 OIer 学有所成。