首页 > 试题广场 > 商品交易
[编程题]商品交易
  • 热度指数:610 时间限制: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
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,cnt=0;
    cin>>n;
    long a[n],s=0;
    bool d = false;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=1;i<n;i++){
        if(a[i]>a[i-1]){
            s += a[i]-a[i-1];
            if(!d)
                cnt++;
            d = true;
        }
        if(a[i]<a[i-1]){
            cnt += d;
            d = false;
        }
    }
    cnt += d;
    cout<<s<<" "<<cnt<<endl;
    return 0;
}

发表于 2019-10-21 17:56:16 回复(0)
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,res1=0,res2=0;
    long long num=0;
    cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=1;i<n;i++)
    {
        if (a[i] > a[i - 1]) 
        {
            num += a[i] - a[i - 1];
            res1 += res2 ^ 1;
            res2 = 1;
        } 
        else if (a[i] < a[i - 1]) {
            res1 += res2;
            res2 = 0;
        }
    }
    cout<<num<<" "<<res1+res2<<endl;
    return 0;
}

发表于 2019-08-18 22:12:01 回复(0)
//不用动态规划
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc  =new Scanner(System.in);
        int len = sc.nextInt();
        int[] in = new int[len];
        int judge = -1,time = 0;
        long out = 0;
        for(int i=0;i<len;i++){
            in[i] = sc.nextInt();
        }
        sc.close();
        for(int i=0;i<len-1;i++){
            if(judge==-1){
                if(in[i]<in[i+1]){
                    judge = in[i];
                    time++;
                }
            }else{
                if(judge<in[i]&&in[i]>in[i+1]){
                    out+=in[i]-judge;
                    time++;
                    judge = -1;
                }
            }
        }
        if(judge!=-1){
            out+=in[len-1]-judge;
            time++;
        }
        System.out.println(out+" "+time);
    }

}
发表于 2019-08-13 20:58:53 回复(0)
采用动态规划,dp[i][j]代表在第i个国家且容器剩余容量为j时的收益。由于容器最大容量为1,所以j只能为0或1。
由于除了收益还要比较交易次数,dp中不仅存储了收益还存储了已交易次数
dp[i][0] = max(dp[i-1][1] + a[i], dp[i-1][0])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - a[i])
(次数的计算比较简单所以不写了)

import java.util.*;
public class Main {
    public static class State {
        long money;
        int deal;
        public State(long money, int deal) {
            this.money = money;
            this.deal = deal;
        }
        public State(State h) {
            this.money = h.money;
            this.deal = h.deal;
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; ++i) {
                a[i] = sc.nextInt();
            }
            State[][] dp = new State[n][2];
            dp[0][0] = new State(0, 0);
            dp[0][1] = new State(-a[0], 1);
            for (int i = 1; i < n; ++i) {
                State sell = new State(dp[i - 1][1]);
                sell.money += a[i];
                sell.deal += 1;
                dp[i][0] = max(sell, dp[i - 1][0]);

                State buy = new State(dp[i - 1][0]);
                buy.money -= a[i];
                buy.deal += 1;
                dp[i][1] = max(dp[i - 1][1], buy);
            }
            System.out.println(dp[n - 1][0].money + " " + dp[n - 1][0].deal);
        }
    }
    public static State max(State h1, State h2) {
        if (h1.money != h2.money) {
            return h1.money > h2.money ? h1 : h2;
        }
        else {
            return h1.deal <= h2.deal ? h1 : h2;
        }
    }
}




编辑于 2019-08-11 14:50:18 回复(1)
n = int(input())
num = list(map(int, input().split()))
deal = 0
profit = 0
cnt = 0
for i in range(1,n):
    if num[i] > num[i-1]:
        profit += num[i]-num[i-1]
        if deal == 0:
            cnt += 1
        deal = 1
    if num[i] < num[i-1]:
        cnt += deal
        deal = 0
print(profit,cnt+deal)

发表于 2019-08-07 09:03:02 回复(3)