题解：P6642 [CCO 2020] Exercise Deadlines

解析：

考虑依次填入每个位置。最后一个位置只能填

d_i=n

的位置，第

k

个位置只能填

d_i \ge k

。

我们随着

k

的减小，决策集合扩大。

那么对于第

n

个位置，一定选择

d_i=n

中最大的

i

。依次类推，第

k

个位置肯定选择决策集合中最大的数。

需要在线维护加入一个数，查询最大值和删除最大值，直接用优先队列即可。

最后再用树状数组求出逆序对。

代码：

CPP

#include<bits/stdc++.h>
#define int long long 
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define N 200005
using namespace std;
int n, d[N], c[N];
vector<int>u[N];
inline void add(int x) {
	for (; x <= n; x += x & -x)c[x]++;
}
inline int ask(int x) {
	int sum = 0;
	for (; x; x -= x & -x)sum += c[x];
	return sum;
}
priority_queue<int>q;
signed main() {
	scanf("%d", &n);
	int ans = 0;
	rep(i, 1, n)scanf("%d", &d[i]), u[d[i]].push_back(i);
	pre(i, n, 1) {
		for (int j = 0; j < (int)u[i].size(); j++)q.push(u[i][j]);
		if (q.empty()) {
			puts("-1");
			return 0;
		}
		int cur = q.top();
		q.pop();
		ans += ask(cur);
		add(cur);
	}
	printf("%lld\n", ans);
	return 0;
}

完结撒花，谢谢

题解：P6642 [CCO 2020] Exercise Deadlines

文章操作

解析：

代码：

相关推荐

评论

题解：P6642 [CCO 2020] Exercise Deadlines