首页 > 试题广场 >

商品交易

[编程题]商品交易

热度指数：2886 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

珐达采下个月要去鸥洲各国考察一趟，采购流通神秘石并从中搞点油水。

珐达采会按顺序依次经过序号分别为1, 2, 3, …, n的鸥洲国家，在第i个国家神秘石的流通价格为Ai鸥。因为行程紧张，在每个国家的停留时间有限，所以他只能花费Ai鸥买入一块神秘石，或者卖出一块手中的神秘石获得Ai鸥，或者什么都不做，而且因为神秘石的保存需要极其先进的高级材料容器，其材料稀有且制作困难，珐达采只有一份容器，故无论何时珐达采手里最多只能拥有一块神秘石。

珐达采想知道最终能从中获利最大多少鸥。因为交易需要手续费，所以珐达采还想知道在获利最大收益的同时，最少需要交易多少次。因为珐达采是大财阀，所以你可以认为他一开始金钱无限。

输入描述:

第一行一个数n。（1≤n≤100000）

第二行n个数，第i个数表示Ai。（1≤Ai≤1e9）

输出描述:

共一行，两个数，分别代表最大收益和对应的最少交易次数。

示例1

输入

5
9 7 10 1 5

输出

7 4

算法知识视频讲解

Java

楊佬叁cbbb

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        // 不持有宝石的收益和交易次数 
        long value0 = 0,cnt0 = 0;
        // 持有宝石的收益和交易次数 
        long value1 = -arr[0],cnt1 = 1;
        
        for (int i = 1; i < n; i++) {
            if(value0<value1+arr[i]){
                value0 = value1+arr[i];
                cnt0 = cnt1+1;
            }
            if(value1<value0-arr[i]){
                value1 = value0-arr[i];
                cnt1 = cnt0+1;
            }
        }

        long max = 0,minCnt = 0;
        for (int i = 1; i < n; i++) {
            if(value0>max){
                max = value0;
                minCnt = cnt0;
            }else if(value0==max){
                minCnt = Math.min(minCnt,cnt0);
            }
        }
        System.out.println(max+" "+minCnt);
    }
}

发表于 2022-08-31 18:10:53 回复(0)

Java

牛客865521580号

不能用int表示最大收益！！！

import java.util.*;
public class Main {

    public static  void main(String []args){
        Scanner in=new Scanner(System.in);
        while(in.hasNext()){

            int n=in.nextInt();
            long nums[]=new long [n];
            for (int i = 0; i < n; i++) {
                nums[i]=in.nextInt();
            }

            int out=0;
            long m=0;
            int i=0;
            int j=-1;
            for (int k = 1; k <n ; k++) {
                if (j==-1){
                    if (nums[k]>nums[i])j=k;
                    if (nums[k]<nums[i])i=k;

                }
                else {
                    if (nums[k]<nums[j]){
                        out++;
                        m+=nums[j]-nums[i];
                        i=k;
                        j=-1;
                    }
                    else if (nums[k]>nums[j])j=k;

                }


            }
            if (j!=-1){
                out++;
                m+=nums[j]-nums[i];
            }
            System.out.println(m+" "+out*2);
        }
    }
}

发表于 2020-07-31 15:17:33 回复(0)