商店

题目描述

一条街上有 $n$ 个商店，在第 $i$ 个商店，可以以 $a_i$ 的价格买入一个商品，也可以以 $a_i$ 的价格卖出一个商品。商品很沉，最多只能同时拿着 $1$ 个商品在街上走。现在按照给定顺序依次访问所有商店，那么，最大收益是多少？在获得最大收益的前提下，最少交易次数是多少？

输入格式

第一行一个整数 $T$ ($1 \le T \le 5$)，代表测试用例个数
下面 $T$ 组数据，其中每一组数据都占两行，其中
第一行一个整数 $n$ ($1 \le n \le 10^5$)，代表商店个数
下面一行 $n$ 个整数，其中第 $i$ 个数为 $a_i$ ($0 \le a_i < 2147483648$)，代表在第 $i$ 个商店可以买入或卖出商品的价格

输出格式

对于每个例子，输出一行两个整数，分别代表最大收益和获得最大收益的前提下最少的交易次数

测试样例

样例 1
输入:

1
5
9 10 7 6 8 

输出:

3 4

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//vector<ll> v;//存储商店的价格

int main() {
    int t;//测试用例个数
    cin >> t;
    for (int i = 0; i < t; i++) {
        //v.clear();//清空vector，防止上一次的样例干扰
        int n;//商店个数
        bool buyed = false;//刚开始时手里没货
        //分别是利润、交易次数、上一次买入的价格、上一次卖出的价格
        ll lirun = 0, cnt = 0, buy, sale = 1LL << (sizeof(ll)*8  - 2);
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) {
            ll now;
            scanf("%lld", &now);//读取输入
            if (buyed) {//如果手里有货
                if (now > buy) {//进行卖出
                    buyed = false;
                    lirun += now;
                    sale = now;
                    cnt++;
                } else if (now < buy) {//如果上一次买贵了，撤销上一次买入,这时才买入
                    lirun += buy;
                    lirun -= now;
                    buy = now;
                }
            } else {//如果手里没货
                if (now > sale) {//如果上一次卖便宜了，撤销上一次卖出,在这一次卖
                    lirun -= sale;
                    lirun += now;
                    sale = now;
                } else if (now < sale) {//进行买入
                    buy = now;
                    buyed = true;
                    lirun -= now;
                    cnt++;
                }
            }
        }
        if (buyed) {//如果没卖完，就撤销最后一次买入
            cnt--;
            lirun += buy;
        }
        printf("%lld %lld\n", lirun, cnt);
    }
    return 0;
}