Codeforces Round 642 (Div. 3) D. Constructing the Array

发布时间:2024年01月08日

题目连接:Problem - 1353D - Codeforces

题意:根据所示方法构造数组。

我们可以发现每次填充一个数之后,我们就得到两段新的线段。所以按照题目所说的方法,我们模拟就可以得到答案。但我们需要把更新控制到nlog(n)以内。

每次选择,我们要先选择最长的字段,在长度相等的情况下选择最靠左边的。我们可以将最靠左边的这个条件转换为右边剩余长度最长的,这样字段和剩余长度的增减性相同,我们可以用pair来存储字段长度和剩余长度,用大根堆来存储每个线段,每次取出队头元素,得到答案。

#include <bits/stdc++.h>
#define int long long
#define x first
#define y second

using namespace std;
typedef pair<int,int> PII ;
const int N = 200010 ;
int n ;
int a[N] ;

void solve()
{
    cin >> n ;
    for(int i = 1 ; i <= n ; i ++) a[i] = 0 ;
    priority_queue<PII> h ;
    h.push({n , 0}) ;
    int cnt = 1 ;
    while(h.size())
    {
        auto t = h.top() ;
        h.pop() ;
        int y = n - t.y , x = n - t.y - t.x + 1 ;
        int mid = (x + y) / 2 ;
        a[mid] = cnt ++ ;

        if(mid - x != 0)
        {
            h.push({mid - x , n - mid + 1}) ;
        }
        if(y - mid != 0)
        {
            h.push({y - mid , n - y}) ;
        }
    }

    for(int i = 1 ; i <= n ; i ++)
        cout << a[i] << " " ;
    puts("") ;
}

signed main()
{
    int t ;
    cin >> t ;
    while(t --)
    {
        solve() ;
    }
    return 0 ;
}

文章来源:https://blog.csdn.net/weixin_50089904/article/details/135434458
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。