解题思路

题目描述了一个商人在 个国家按顺序交易神秘石的问题：

  1. 每个国家的神秘石价格为
  2. 商人同一时刻只能持有一块神秘石
  3. 需要计算：
    • 最大获利金额
    • 最少交易次数（在获得最大利润的情况下）

解题思路：

  1. 遍历价格数组，当遇到价格上升时：
    • 累加差价到总利润
    • 如果是新的上升序列，交易次数加1
  2. 当遇到价格下降时：
    • 如果之前有上升标记，交易次数加1
    • 重置上升标记

代码

#include <iostream>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    ll n;
    cin >> n;
    ll a[100005];
    for (ll i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    ll profit = 0, trades = 0;
    bool rising = false;
    
    for (ll i = 1; i < n; i++) {
        if (a[i] > a[i-1]) {
            profit += (a[i] - a[i-1]);
            if (!rising) trades++;
            rising = true;
        } else if (a[i] < a[i-1]) {
            trades += rising;
            rising = false;
        }
    }
    trades += rising;  // 处理最后一段上升序列
    
    cout << profit << " " << trades << '\n';
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] prices = new long[n];
        
        for (int i = 0; i < n; i++) {
            prices[i] = sc.nextLong();
        }
        
        long profit = 0;
        int trades = 0;
        boolean rising = false;
        
        for (int i = 1; i < n; i++) {
            if (prices[i] > prices[i-1]) {
                profit += (prices[i] - prices[i-1]);
                if (!rising) trades++;
                rising = true;
            } else if (prices[i] < prices[i-1]) {
                trades += rising ? 1 : 0;
                rising = false;
            }
        }
        trades += rising ? 1 : 0;
        
        System.out.println(profit + " " + trades);
    }
}

n = int(input())
prices = list(map(int, input().split()))

profit = 0
trades = 0
rising = False

for i in range(1, n):
    if prices[i] > prices[i-1]:
        profit += prices[i] - prices[i-1]
        if not rising:
            trades += 1
        rising = True
    elif prices[i] < prices[i-1]:
        trades += 1 if rising else 0
        rising = False

trades += 1 if rising else 0

print(profit, trades)

算法及复杂度

  • 算法：贪心算法
  • 时间复杂度： - 只需要遍历一次价格数组
  • 空间复杂度： - 需要存储输入的价格数组