鹤山做网站公司,浅谈一下网络营销的几个误区,抖音代运营联系方式,wordpress筛选最新文章目录 题目大意#xff1a;
思路解析#xff1a;
代码#xff1a; Problem - E - Codeforces
题目大意#xff1a;
现在给你一个排列#xff0c;排列的定义是如果排列长度为n#xff0c;则他应该出现1-n的每个数字一次#xff0c;但是顺序是无序的#xff0c;现在问…
目录 题目大意
思路解析
代码 Problem - E - Codeforces
题目大意
现在给你一个排列排列的定义是如果排列长度为n则他应该出现1-n的每个数字一次但是顺序是无序的现在问你通过旋转使得这个排列变为有序的每个位置需要多少次旋转就可以让他变为有序。旋转操作定义为让现在排列在不是有序的位置进行左移。例如3 2 4 1 5现在有序的位置 2 和 5所以我们让 1 3 4这上面位置的数字进行旋转旋转一次后数列变为 1 2 3 4 5。
思路解析
我们现在知道了我们只能进行旋转我们需要得到它这个位置进行旋转的次数因为每次旋转一次就会左移一次其实就是看它对应位置的距离。 给出一个例子
214653123456 1 和 1 的位置距离5
2 和 2 的位置距离1
3 和 3 的位置距离3这里 包括了 2 和 2 的距离
4 和 4 的位置距离1
5 和 5 的位置距离0
6 和 6 的位置距离2。例如 这里包括了5和5的距离
但是这些距离其实包括了已经不需要移动的距离或者在移动过程中有些距离已经不需要移动了这是需要减去的。所以我们可以通过每个位置上面的ai来计算它前往的有序位置距离它当前位置的距离。 计算公式为
ai i, x ai - iai i, x ai n - i
通过上面分析我们知道这样的距离其实是包括了一些多余的距离多余的距离通过上面分析我们知道就是在旋转时比我们先达到终点的点那我们可以把这个距离看作一个线段如果它比我们先达到终点则这个线段应该完全被我的线段包含。如 6 - 6 的线段为 4 - 6. 5 - 5 的线段为 5 - 5. 6 - 6 的线段完全包含5 - 5 的线段所以 6 - 6 的线段距离为 6 - 4 - 1。完全包含几个线段就减去几。这里线段的查询和更新使用二叉索引数完成。
因为ai i情况下的线段为 i --- ai n 。因为有些线段跨越了n这将ai i情况下的线段分为两个i --- aiin --- ain。
代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.Scanner;/*** ProjectName: study3* FileName: Ex27* author:HWJ* Data: 2023/11/26 0:48*/
public class Ex27 {static int[] f;static int n;public static void main(String[] args) throws IOException {StreamTokenizer in new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));in.nextToken();int t (int)in.nval;for (int o 0; o t; o) {in.nextToken();n (int)in.nval;int[] res new int[n 1];int[] arr new int[n 1];f new int[2 * n 5];int[][] rgs new int[2 * n 5][2];int p 0;for (int i 1; i n; i) {in.nextToken();arr[i] (int)in.nval;if (i arr[i]){rgs[p][0] i;rgs[p][1] arr[i];rgs[p][0] i n;rgs[p][1] arr[i] n;}else {rgs[p][0] i;rgs[p][1] arr[i] n;}}Arrays.sort(rgs, 0, p, ((o1, o2) - {return o2[0] - o1[0];}));for (int i 0; i p; i) {if (rgs[i][0] n){res[arr[rgs[i][0]]] rgs[i][1] - rgs[i][0] - (qre(rgs[i][1]) - qre(rgs[i][0] - 1));}incre(rgs[i][1]);}for (int i 1; i n; i) {System.out.print(res[i] );}System.out.println();}}public static int qre(int x){int res 0;for (; x 0; x - x -x) {res f[x];}return res;}public static void incre(int x){for (; x 2 * n; x x -x) {f[x] 1;}}
}
