Codeforces 1353D Constructing the Array

9785 단어 Codeforces
제목 링크:https://codeforces.com/contest/1353/problem/D사고방식: 우리는 모든 처리해야 할 하위 라인을 {길이, 왼쪽 점 번호, 오른쪽 점 번호} 순서대로 우선 대기열에 저장하고 하나씩 처리하면 된다.코드:
#include

using namespace std;

struct seg {
	int len, l, r;
	bool operator < (const seg & s) const {
		return len == s.len ? s.l < l : s.len > len;
	}
};
void solve(int & n) {
	priority_queue<seg> que;
	que.push(seg{n, 1, n});
	vector<int> ans(n + 1);
	int cnt = 1;
	while(!que.empty()) {
		seg s = que.top();
		que.pop();
		int mid = s.l + s.r;
		if(mid & 1) mid = (mid - 1) >> 1;
		else mid >>= 1;
		ans[mid] = cnt++;
		if(mid - 1 >= s.l) que.push(seg{mid - s.l, s.l, mid - 1});
		if(s.r >= mid + 1) que.push(seg{s.r - mid, mid + 1, s.r});
	}
	for(int i = 1; i <= n; i++) printf("%d ", ans[i]);
	putchar('
'
); } int main() { #ifdef MyTest freopen("Sakura.txt", "r", stdin); #endif int kase; scanf("%d", &kase); while(kase--) { int n; scanf("%d", &n); solve(n); } return 0; }

좋은 웹페이지 즐겨찾기