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

八、离散化

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、贪心的概念

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

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

例题---谈判

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

           2

           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;

相关推荐

  1. 指针_贪心_1921_D. Very Different Array

    2024-04-03 23:30:01       21 阅读
  2. ARM 汇编指令:(四) 运算指令

    2024-04-03 23:30:01       8 阅读

最近更新

  1. leetcode705-Design HashSet

    2024-04-03 23:30:01       5 阅读
  2. Unity发布webgl之后打开streamingAssets中的html文件

    2024-04-03 23:30:01       5 阅读
  3. vue3、vue2中nextTick源码解析

    2024-04-03 23:30:01       6 阅读
  4. 高级IO——React服务器简单实现

    2024-04-03 23:30:01       5 阅读
  5. 将图片数据转换为张量(Go并发处理)

    2024-04-03 23:30:01       4 阅读
  6. go第三方库go.uber.org介绍

    2024-04-03 23:30:01       6 阅读
  7. 前后端AES对称加密 前端TS 后端Go

    2024-04-03 23:30:01       7 阅读

热门阅读

  1. 初识人工智能---------自然语言处理&&词袋模型

    2024-04-03 23:30:01       5 阅读
  2. MySQL学习笔记(持续更行ing)

    2024-04-03 23:30:01       7 阅读
  3. C++从入门到精通——nullptr

    2024-04-03 23:30:01       4 阅读
  4. 大厂HashMap源码面试

    2024-04-03 23:30:01       4 阅读
  5. Linux进程状态

    2024-04-03 23:30:01       4 阅读
  6. 力扣--哈希表+滑动子块--串联所有单词子串

    2024-04-03 23:30:01       4 阅读
  7. MySQL两表联查之分组成绩第几问题

    2024-04-03 23:30:01       4 阅读
  8. Redis面试题15道

    2024-04-03 23:30:01       2 阅读