ARC194B题解

首先贪心地考虑（好吧我是看样例看出来的），按照数值从大到小的顺序来操作。即先将更大的数排到它应该去的位置。
然后我们考虑对于每一个数它产生的代价。对于第

i

个数，我们假设它最后会排到第

j

位。会发现，当我们要去操作这个数的时候，它会因为它左边的比它更大的数已经排到右边而向左移。我们设它左边的比它更大的数有

x

个，则它会产生的代价应该是

\cfrac{(i-x-1+j)\times |i-x-j|}{2}

。这个式子是等差数列求和算出来的，其中首项应该是

j

，末项是

i-x-1

。
然后我们考虑

x

的求法。这其实就是一个求逆序对的求法，只不过固定了一个数，用线段树或者树状数组即可。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const int MAXN = 2e5+5;


ll n;
ll p[MAXN];
ll qd[MAXN]; //前面的大于 p[i] 的个数
pll ps[MAXN];
//树状数组
ll lowbit(ll x)
{
	return (x&(-x));
}

ll c[MAXN];

ll Sum(ll x)
{
	ll sum = 0;
	for(ll i = x;i > 0;i -= lowbit(i))
	{
		sum += c[i];
	}
	return sum;
}

void modify(ll x,ll k)
{
	for(ll i = x;i <= n;i += lowbit(i))
	{
		c[i] += k;
	}
	return;
}

int main()
{
	scanf("%d", &n);
	for(int i = 1;i <= n;i++)
	{
		scanf("%lld", &p[i]);
		qd[i] = Sum(n) - Sum(p[i]); 
        modify(p[i], 1LL);
        // 这两行就是计算在 p[i] 前面的大于 p[i] 的数的个数
		ps[i] = pll(p[i], i);
	}
	sort(ps + 1, ps + n + 1);
	ll ans = 0;
	for(int i = 1;i <= n;i++)
	{
        //ps[i].second 对应前文的 i
        //qd[ps[i].second] 对应前文的 x
        //i 对应前文的 j
		ll nowid = ps[i].second - qd[ps[i].second];
		ans += ((nowid-1 + i) * (ll)abs(nowid - i) >> 1LL);
	}
	printf("%lld", ans);


	return 0;
}

文章操作

代码

相关推荐

评论

ARC194B题解