Compute'sOCD

第一行有三个整数 n, A, B $(1 \le n \le 10^5, 1\le A, B \le 10^4)$ 分别表示 Compute 获得的人物卡的数量，氪金使属性 +1 和 -1 所需要的花费。

接下来一行有 n 个整数 $x_1, x_, \ldots, x_n$ $(1\le x_i \le 10^9)$ ，分别表示 Compute 获得的每张卡的属性值 $x_i$ 。

C++ 解法, 执行用时: 48ms, 内存消耗: 2752K, 提交时间: 2022-03-05 16:43:28

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
priority_queue<int> L;
priority_queue<int, vector<int>, greater<int> > R;
int n,ma,mb;
long long s,lsum,rsum;
int main()
{
	scanf("%d%d%d",&n,&ma,&mb);
	scanf("%d",&s); printf("0\n");
	lsum=rsum=0;
	for (int i=2; i<=n; i++)
	{
		int x; scanf("%d",&x);
		if (x<=s) L.push(x),lsum+=x; else R.push(x),rsum+=x;
		while ((L.size()+1)*ma<R.size()*mb) lsum+=s,L.push(s),s=R.top(),rsum-=s,R.pop();
		while (L.size()*ma>(R.size()+1)*mb) rsum+=s,R.push(s),s=L.top(),lsum-=s,L.pop();
		long long ans=(s*L.size()-lsum)*ma+(rsum-s*R.size())*mb;
		printf("%lld\n",ans);
	}
	return 0;
}

详情