离散化、贪心、双指针、二分、倍增、构造、位运算

本文主要是介绍离散化、贪心、双指针、二分、倍增、构造、位运算，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

八、离散化

1、离散化简介

把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。
离散化是一种将数组的值域压缩，从而更加关注元素的大小关系的算法。
当原数组中的数字很大、负数、小数时(大多数情况下是数字很大)，难以将“元素值”表示为”数组下标“，一些依靠下标实现的算法和数据结构无法实现时，我们就可以考虑将其离散化。
离散化数组要求内部是有序的(一般是去重的，当然也存在不去重的方法，但是比较少见)，其中可以直接通过离散化下标得到值。

例题

输入一个长度为n的数组An，输出第i个数在数组从小到大排序后的排名，数字大小相同时排名一样。(n<=1e5,Ai<.1e9)

输入：5

5 4 4 2 1 4 3 3 2 1

package 无忧.第二章.基础算法;import java.util.*;public class _08离散化 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] arr = new int[n];int[] a = new int[n];Set<Integer> set = new HashSet<>();for (int i = 0; i < n; i++) {arr[i] = sc.nextInt();a[i] = arr[i];}Arrays.sort(a);int k = 0;Map<Integer,Integer> map = new HashMap<>();for (int i = 0; i < n; i++) {set.add(a[i]);map.put(a[i],set.size());}for (int i = 0; i < n; i++) {System.out.print(map.get(arr[i]) + " ");}}
}

九、贪心

1、贪心的概念

建立数学模型来描述问题
把求解的问题分成若干子问题
对每一字问题求解，得到子问题的局部最优解
把子问题的解局部最优解合成原来解问题的一个解

总结：从局部最优做到全局最优

例题---谈判

https://www.lanqiao.cn/problems/545/learning/

在很久很久以前，有n个部落居住在平原上，依次编号为1到n。第i个部落的人数为 $t_{i}$ 。有一年发生了荒灾。年轻的政治家小兰想要说服所有部落一同应对灾害，他能通过谈判来说服部落进行联合。每次谈判，小蓝只能邀请两个部落参加，花费的金币数量为两个部落的人数之和，谈判的效果是两个部落联合成一个部落(人数为原来两个部落的人数之和)

输入描述：输入的第一行包含一个整数n，表示部落的数量。

第二行包含n个正整数，依次表示每个部落的人数。

输出描述：输出一个整数，表示最小花费。

示例：4

9 1 3 5 31

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);List<Integer> list = new ArrayList<>();int n = sc.nextInt();for (int i = 0; i < n; i++) {int a = sc.nextInt();list.add(a);}Collections.sort(list);long sum = 0;while (list.size()>1){int a = list.get(0);int b = list.get(1);sum += a + b;list.remove(0);list.remove(0);list.add(a+b);Collections.sort(list);}System.out.println(sum);sc.close();}
}

例题---重新排序

给定一个数组A和一些查询 $L{_{i}}$ ， $R_{i}$ ，求数组中第 $L{_{i}}$ 至第 $R_{i}$ 个元素的之和。小蓝觉得这个问题很无聊，于是他想重新排列一下数组，使得最终每个查询结果的和尽可能地大。小蓝想知道相比原数组，所有查询结果的总和最多可以增加多少？

输入格式：输入第一行包含一个整数n。

第二行包含n个整数 $A_{1},A_{2},...,A_{n}$ ，相邻两个整数之间用一个空格分隔。

第三行包含一个整数m表示查询的数目。

接下来m行，每行包含两个整数 $L{_{i}}$ 、 $R_{i}$ ，相邻两个整数之间用一个空格分隔。

输出格式：输出一行包含一个整数表示答案。

示例：5

1 2 3 4 5

1 3

2 5 4

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.lang.invoke.MethodHandles;
import java.util.Arrays;
import java.util.StringTokenizer;public class Main {public static void main(String[] args) {MyScanner sc = new MyScanner();int n = sc.nextInt();int[] arr = new int[n];for (int i = 0; i < n; i++) {arr[i] = sc.nextInt();}int q = sc.nextInt();int[] d = new int[n];while(q-->0){int l = sc.nextInt()-1;

这篇关于离散化、贪心、双指针、二分、倍增、构造、位运算的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！