2018中国大学生程序设计竞赛 – 网络选拔赛 1001 Buy and Resell [模拟]

                                              1001 Buy and Resell

 题目：有1-n个货物，可以在某个点buy，然后在后面的点resell，可以同时买多个，问最大的利润和最小的交易次数。

题解：模拟运算，前 i 天都是可以买的，加入待卖序列(x, 0)，对于第 i 天如果最小的待卖的价格比a[i]小，那么说明可以卖，然后将(a[i], 1)加入队列，表示已经卖出,这样模拟一下;

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5+7;

int n;
ll a[maxn];
struct node{
    ll num,index;
    node(ll a,ll b)
    {
        num = a;
        index = b;
    }
    friend bool operator < (node a,node b)
    {
           if(a.num == b.num) return a.index < b.index;
           return a.num > b.num;
    }
};

priority_queue <node> q;

int main()
{
    //freopen("in.txt", "r", stdin);
	int t; scanf("%d", &t);
	while(t--)
	{
		scanf("%d", &n);
		ll x = 0, y = 0;
		for(int i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
            q.push(node(a[i], 0));
            node temp = q.top();
            if(a[i]>temp.num) {
                x += (a[i] - temp.num);
                q.pop();
                q.push(node(a[i], 1));
            }
		}
        while(!q.empty()) {
            if(q.top().index == 1) y++;
            q.pop();
        }
	    printf("%lld %lld\n", x, 2ll*y);
	}
	return 0;
}