CF-1353D Constructing the Array 题解

题目大意

给你一个长度为n的数组，这个数组中每一位都为0，你需要选择仅由0组成的最长子数组，如果最大长度相同的话，选择最左边那一个。

对你每一个选择的子数组来说，如果长度为奇，则$a[\frac{l+r}{2}]$赋值为$i$。如果长度为偶，则$a[\frac{l+r-1}{2}]$赋值为$i$。$i$为进行的第几步。

解题思路

这题本来没什么思路的。。。

群里大佬提醒了一下可以用优先队列

我就试了一下，一遍过了。。

其实思路很简单，构造一个按照长度由长到短，相等的时候优先靠左的优先队列。

定义一个结构体，储存$l,r,len$。优先队列的类型即为这个结构体。

起点为$l = 1,r = n,len = n$。

每次从队列中取出一个，按照题意分为左右两块区域。

然后一步一步插入即可。

需要手写一个判断的类函数。

完整代码

#include <iostream>
#include <cstring>
#include <string>
#include <functional>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 2e5 + 5;
struct a {
	int l, r, len;
};
struct cmp
{
	int operator() (a n, a m)
	{
		if (n.len == m.len)	return n.l > m.l;
		return n.len < m.len;//注意，和排序的时候是相反的
	}
};

priority_queue<a, vector<a>, cmp> q;//优先队列
int num[N];

int main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		a m;
		m.l = 1, m.r = n, m.len = n;
		q.push(m);
		memset(num, 0, sizeof(num));
		for (int i = 1; i <= n; i++) {
			a t = q.top();
			q.pop();
			int mid = (t.l + t.r) / 2;
			num[mid] = i;
			a m1, m2;
			m1.l = t.l, m1.r = mid - 1, m1.len = mid - t.l;
			m2.l = mid + 1, m2.r = t.r, m2.len = t.r - mid;
			q.push(m1);
			q.push(m2);
		}
		for (int i = 1; i <= n; i++) {
			string s = i == n ? "\n" : " ";
			cout << num[i] << s;
		}
		while (!q.empty())	q.pop();
	}
}