java构造器构造数组_构造数组

àì夳堔傛蜴生んèń 2023-03-05 09:45 15阅读 0赞

java构造器构造数组

**Problem statement:**

**问题陈述：**

You are given an array *a* of length *n* consisting of zeros. You perform *n* actions with this array: during the *i*\-th action, the following sequence of operations appears:

您会得到一个长度为*n*的数组*a* ，该数组由零组成。 您使用此数组执行*n个*操作：在第*i*个操作期间，将出现以下操作序列：

Choose the maximum by length subarray (continuous subsegment) consisting only of zeros, among all such segments choose the leftmost one;

选择仅由零组成的最大长度子数组(连续子段)，在所有此类段中，选择最左边的一个；

Let this segment be *\[l;r\]*. If *r-l+1* is odd (not divisible by 2) then assign (set) *a\[(l+r)/2\]:=i* (where *i* is the number of the current action), otherwise (if *r-l+1* is even) assign (set) *a\[(l+r-1)/2\]:=i*.

将此段设为*\[l; r\]* 。 如果*r-1 + 1*是奇数(不能被2整除)，则分配(设置) *a \[(l + r)/ 2\]：= i* (其中*i*是当前动作的编号)，否则(如果*r-1 +1*是偶数)分配(set) *a \[(l + r-1)/ 2\]：= i* 。

**Input:**

**输入：**

The first line of the input contains one integer t (1≤t≤10^4) — the number of test cases. Then t test cases follow.

输入的第一行包含一个整数t(1≤t≤10^ 4)-测试用例的数量。 然后是t个测试用例。

The only line of the test case contains one integer n (1≤n≤2⋅10^5) — the length of a.

测试用例的唯一一行包含一个整数n(1≤n≤2⋅10^ 5)-a的长度。

It is guaranteed that the sum of n over all test cases does not exceed 2⋅10^5 (∑n≤2⋅10^5).

确保所有测试用例的n之和不超过2⋅10^ 5(∑n≤2⋅10 ^ 5)。

**Output:**

**输出：**

For each test case, print the answer — the array *a* of length *n* after performing *n* actions described in the problem statement. Note that the answer exists and unique.

对于每个测试用例，执行问题陈述中描述的*n个*动作后，打印答案-长度为*n*的数组*a* 。 请注意，答案存在且唯一。

**Examples:**

**例子：**

Consider the array a of length 5 
    (initially a=[0,0,0,0,0]). Then it changes as follows:
    
    Firstly, 
        we choose the segment [1;5] and 
        assign a[3]:=1, so a becomes [0,0,1,0,0];
    then 
        we choose the segment [1;2] and 
        assign a[1]:=2, so a becomes [2,0,1,0,0];
    then
        we choose the segment [4;5] and 
        assign a[4]:=3, so a becomes [2,0,1,3,0];
    then 
        we choose the segment [2;2] and 
        assign a[2]:=4, so a becomes [2,4,1,3,0];
    and at last 
        we choose the segment [5;5] and 
        assign a[5]:=5, so a becomes [2,4,1,3,5].

Problem source: [https://codeforces.com/contest/1353/problem/D][https_codeforces.com_contest_1353_problem_D]

问题来源： [https][https_codeforces.com_contest_1353_problem_D] ： [//codeforces.com/contest/1353/problem/D][https_codeforces.com_contest_1353_problem_D]

**Solution Approach**

**解决方法**

We will use the heap data structure to solve this problem (we will use max heap), since the problem is to assign count variable *i*, we will create priority queue with pair, the first part of the pair is the size of subarray and the second part of the pair is another pair which contains indices *l* and *r*, left index and right index of the subarray.

我们将使用堆数据结构来解决此问题(我们将使用最大堆)，因为问题是分配计数变量*i* ，所以我们将创建具有对的优先级队列，该对的第一部分是子数组的大小和该对的第二部分是另一对，其中包含子数组的索引*l*和*r* ，左索引和右索引。

A/c to the question if the size of the left and right subarray with the equal number of 0s in them we have to choose the left part, so to solve the problem we multiply the indexes with -1 so that left part is chosen.

对于是否必须在其中包含相等的0的左右子数组的大小的问题，我们必须选择左边部分，因此，为了解决该问题，我们将索引乘以-1以选择左边部分。

While a priority queue is not empty, we pick the max element from the top of the priority queue and pop it from the priority queue.

当优先级队列不为空时，我们从优先级队列的顶部选择max元素，然后将其从优先级队列中弹出。

Now, *l*=be the left index of the subarray and r be the right index of the subarray. We take the mid index as *(l+r)/2* and fill it with *cnt* and increment it with one each time. If *l==r* then there is no possibility of partition among it so simply continue, else one part will be the subarray of *l* to *mid-1* and the other part will be *mid+1* to *r* with *length* (*mid-l*) and (*r-mid*) respectively.

现在， *l* =是子数组的左索引，r =是子数组的右索引。 我们将中间索引设为*(l + r)/ 2* ，并用*cnt*填充它，并每次增加1。 如果*l == r*则不可能在其中进行划分，因此只需继续，否则一部分将是*l*到*mid-1*的子数组，另一部分将是*mid + 1*到*r*的*长度* ( *mid-l* )，并且( *r-mid* )。

Push them with their respective length and indices into the priority queue.

将它们及其各自的长度和索引推送到优先级队列中。

We repeat the process untill the priority queue is not empty.

我们重复该过程，直到优先级队列不为空。

**C++ Implementation:**

**C ++实现：**

#include <bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    
    ll arr[200005];
    
    // solve function to solve the entire problem which 
    // takes n as the parameter,n is size of the array arr[].
    void solve(ll n)
    {
        // priority queue as our max heap
        priority_queue<pair<ll, pair<ll, ll> > > pq; 
        // Here, pq with pair of len and pair of 
        // indices as its elements.
        
        // base case as len of entire array as first input 
        // from index 1 to n but its multiplied with -1 
        // so that left sub-array can be chosen if len of two 
        // sub-arrays are equals.
        pq.push({ n, { -1, -n } });
        
        // initialise count as 1.
        ll cnt = 1;
        
        // if priority_queue is not empty 
        // then do the following operation.
        while (!pq.empty()) {
            // declare pair
            pair<ll, pair<ll, ll> > p = pq.top();
            pq.pop();
            ll l = p.second.first * (-1); // initialize left index
            ll r = p.second.second * (-1); // initialise right index
            ll mid = (l + r) / 2; // take mid index of the sub-array
            arr[mid] = cnt; // assign cnt value to mid index.
            cnt++; // increment count variable.
    
            // base case condition if only single element is present.
            if (l == r)
                continue;
            else {
                // declare left subarray
                if ((mid - 1) >= 0 and (mid - 1) >= l) {
                    ll len = mid - l; // len of left sub-array
                    pq.push({ len, { (-1) * l, (-1) * (mid - 1) } });
                }
                // declare right sub-array
                if ((mid + 1) <= n and (mid + 1) <= r) {
                    ll len = r - mid; // len of right sub-array
                    pq.push({ len, { (-1) * (mid + 1), (-1) * r } });
                }
            }
        }
        
        // iterate through final result array.
        for (ll i = 1; i <= n; i++)
            cout << arr[i] << " ";
        cout << "\n";
    }
    
    int main()
    {
        ll t;
        
        cout << "Enter number of test cases: ";
        cin >> t;
        
        while (t--) {
            cout << "Enter size of array: ";
            ll n;
            cin >> n;
        
            // call solve function.
            solve(n);
        }
        
        return 0;
    }

**Output:**

**输出：**

Enter number of test cases: 4
    Enter size of array: 5
    2 4 1 3 5 
    Enter size of array: 4
    3 1 2 4 
    Enter size of array: 9
    6 2 4 7 1 8 3 5 9 
    Enter size of array: 3
    2 1 3

*  Time Complexity for the above approach: **O(nlogn)**
    
    上述方法的时间复杂度： **O(nlogn)**
 *  space Complexity for the above approach: **O(n)**
    
    上述方法的空间复杂度： **O(n)**

> 翻译自: [https://www.includehelp.com/icp/constructing-the-array.aspx][https_www.includehelp.com_icp_constructing-the-array.aspx]

java构造器构造数组

[https_codeforces.com_contest_1353_problem_D]: https://codeforces.com/contest/1353/problem/D
[https_www.includehelp.com_icp_constructing-the-array.aspx]: https://www.includehelp.com/icp/constructing-the-array.aspx