D. Constructing the Array
12639 ワード
タイトル: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コード:
考え方:この問題について思いついたことは二叉樹で検索できるが、どうやって書くかずっと考えていなかった.他人のコードを見て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();
}
}
}