CF 865D

洛谷题目翻译

假设每天都买,到最后的时候,所有没卖出去的邮票都可以原价出售(相当于没买).

每到新的一天,如果当前的价钱比以前某卖出的一天高,那就用今天卖前面那天的股票.

如果不存在上一行的情况且今天的价钱比我已经买了且没卖的最便宜的股票高,那我就把最便宜的那股卖了.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;

int n;
long long p[300001],ans;
priority_queue<long long ,vector<long long>,greater<long long> > q,q1;

int main() {
	scanf("%d",&n);
	for(int i = 1;i <= n; i++)
		scanf("%lld",&p[i]);
	q.push(p[1]);
	for(int i = 2;i <= n; i++) {
		if(q.empty()) {
			q.push(p[i]);
			int u = q1.top();
			if(p[i] > u) {
				ans = ans + p[i] - u;
				q1.pop();
				q1.push(p[i]);
			}
		}
		else {
			if(q1.empty()) {
				if(p[i] - q.top() > 0) {
					ans += p[i] - q.top();
					q.pop();
					q1.push(p[i]);
				}
				q.push(p[i]);
				continue; 
			}
			if(p[i] - q.top() > 0) {
				if(p[i] - q1.top() > p[i] - q.top()) {
					int v = q1.top();
					ans += p[i] - v;
					q.push(p[i]);
					q1.pop();
					q1.push(p[i]);
				}
				else {
					ans += p[i] - q.top();
					q.pop();
					q.push(p[i]);
					q1.push(p[i]);
				}
			}
			else {
				if(p[i] - q1.top() > 0) {
					ans += p[i] - q1.top();
					q1.pop();
					q1.push(p[i]);	
				}
				q.push(p[i]);
			}
		}
	}
	printf("%lld",ans);
	return 0;
}