列表

详情


OR163. 商品交易

描述

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

珐达采会按顺序依次经过序号分别为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

原站题解

C++ 解法, 执行用时: 10ms, 内存消耗: 1256KB, 提交时间: 2020-10-31

/*我是萌新*/
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include <iomanip>
#include<map>
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
//fixed<< setprecision(2)
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    ll n;
    cin >> n;
    ll a[100005];
    for (ll i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    ll x = 0, y = 0, flag = 0;
    for (ll i = 1; i < n; i++)
    {
        if (a[i] > a[i - 1])
        {
            x+=(a[i]-a[i-1]);
            if(!flag)y++;
            flag=1;
        }
        else if(a[i]<a[i-1])
        {
            y+=flag;
            flag=0;
        }
    }
   y+=flag;
    cout << x << " " << y << '\n';
}

C++ 解法, 执行用时: 11ms, 内存消耗: 2176KB, 提交时间: 2020-08-25

/*我是萌新*/
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include <iomanip>
#include<map>
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;
//ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
//ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
//fixed<< setprecision(2)
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    ll n;
    cin >> n;
    ll a[100005];
    for (ll i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    ll x = 0, y = 0, flag = 0;
    for (ll i = 1; i < n; i++)
    {
        if (a[i] > a[i - 1])
        {
            x+=(a[i]-a[i-1]);
            if(!flag)y++;
            flag=1;
        }
        else if(a[i]<a[i-1])
        {
            y+=flag;
            flag=0;
        }
    }
   y+=flag;
    cout << x << " " << y << '\n';
}

上一题