D. Constructing the Array


タイトル:http://codeforces.com/contest/1353/problem/D 題意:与えられた数字に対して、1、最大の長さのサブ配列(連続サブセグメント)を選択するには、このようなすべてのセグメントの中で、最も左側の1つだけを選択します.2、この[l;r][l;r]を.r−l+1 r−l+1が奇数(22にすることができない)である場合、a[l+r 2]:=ia[l+r 2]:=i(どこでiiが現在の動作の番号であるか)を割り当てると、(r−l+1 r−l+1が偶数である場合)a[l+r−12]:=ia[l+r−12]:=iとなる.
考え方:この問題について思いついたことは二叉樹で検索できるが、どうやって書くかずっと考えていなかった.他人のコードを見てPriorityQueueというAPIを使った人がいて、内部自体が二叉樹であることを調べたが、特に分からなかった.
PriorityQueueの内部構造方法の説明:https://blog.csdn.net/u013309870/article/details/71189189
ACコード:
package   ;
import java.io.*;
import java.math.*;
import java.math.BigInteger;
import java.util.*;
public class    {
 public static void main (String[] args) {
  Scanner sc=new Scanner(System.in);
         int t = sc.nextInt();
         while (t-- > 0) {
             int n = sc.nextInt();
             int k = 1;
             int[] arr = new int[n];
             PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {//  ,     ,           
                 int len1 = a[1]-a[0]+1, len2 = b[1]-b[0]+1;
                 if (len1 != len2) return (len2-len1); 
                 return (a[0]-b[0]);});
  
             pq.add(new int[]{0, n-1});//           
             while (!pq.isEmpty()) {//pq    
                 int[] cur = pq.poll();//                           
                 int len = cur[1] - cur[0] + 1;
                 int mid = (cur[1]+cur[0])/2;//    
                 arr[mid] = k++;
                 if (len == 1) continue;//len 1    
                 if ((mid-1) >= cur[0])
                     pq.offer(new int[]{cur[0], mid-1});
                 if ((mid+1) <= cur[1])
                     pq.offer(new int[]{mid+1, cur[1]});
             }
             for (int elem: arr) System.out.print(elem + " " );
             System.out.println();
         }
     }
}