2-25算法习题总结

发布于：2024-02-28 ⋅ 阅读:(114) ⋅ 点赞:(0)

贪心问题

P1803 凌乱的yyy / 线段覆盖

凌乱的yyy / 线段覆盖

题目背景

快 noip 了，yyy 很紧张！

题目描述

现在各大 oj 上有 n n n 个比赛，每个比赛的开始、结束的时间点是知道的。

yyy 认为，参加越多的比赛，noip 就能考的越好（假的）。

所以，他想知道他最多能参加几个比赛。

由于 yyy 是蒟蒻，如果要参加一个比赛必须善始善终，而且不能同时参加 2 2 2 个及以上的比赛。

输入格式

第一行是一个整数 n n n，接下来 n n n 行每行是 2 2 2 个整数 a i , b i   ( a i < b i ) a_{i},b_{i}\ (a_{i}<b_{i}) ai​,bi​ (ai​<bi​)，表示比赛开始、结束的时间。

输出格式

一个整数最多参加的比赛数目。

样例 #1

样例输入 #1

3
0 2
2 4
1 3

样例输出 #1

2

提示

  • 对于 20 % 20\% 20% 的数据， n ≤ 10 n \le 10 n≤10；
  • 对于 50 % 50\% 50% 的数据， n ≤ 1 0 3 n \le 10^3 n≤103；
  • 对于 70 % 70\% 70% 的数据， n ≤ 1 0 5 n \le 10^{5} n≤105；
  • 对于 100 % 100\% 100% 的数据， 1 ≤ n ≤ 1 0 6 1\le n \le 10^{6} 1≤n≤106， 0 ≤ a i < b i ≤ 1 0 6 0 \le a_{i} < b_{i} \le 10^6 0≤ai​<bi​≤106。

代码如下:
自己写的一直卡在70分,有三个点没过!

package exercise.luogu.greedy;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

class Race {
    int start;
    int end;

    public Race(int start, int end) {
        this.start = start;
        this.end = end;
    }

}

public class P1803 {

    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            int n = sc.nextInt();
            List<Race> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                list.add(new Race(sc.nextInt(), sc.nextInt()));
            }

            Collections.sort(list, Comparator.comparingInt(o -> o.end));

            int endTime = list.get(0).end;

            int count = 1;
            for (int i = 1; i < list.size(); i++) {
                if (list.get(i).start >= endTime) {
                    count++;
                    endTime = list.get(i).end;
                }
            }

            System.out.println(count);
        }
    }
}

看别人的题解

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;

public class Main{
    public static void main(String[] args) throws IOException {
    	// 创建一个StreamTokenizer对象n1，用于从标准输入（System.in）读取并解析tokens。  
        // 使用了InputStreamReader和BufferedReader来创建一个缓冲的字符输入流。
        StreamTokenizer n1 = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        //读取一个数据
        n1.nextToken();
        //从n1中获取最近读取的token的数值表示（即nval）
        int n = (int) n1.nval;
        int[] match = new int[1000001];
        //match数组初始化为-1
        Arrays.fill(match,-1);
        for (int i = 0; i < n; i++) {
            n1.nextToken();
            int begin = (int) n1.nval;
            n1.nextToken();
            int end = (int) n1.nval;
			//这样为了获得最早的开始时间
            if(match[end] == -1){
                match[end] = begin;
            }else if(match[end] < begin){
                match[end] = begin;
            }

        }
        
        int nowtime = 0;
        int out = 0;
        for (int i = 0; i < match.length; i++) {
            if(nowtime <= match[i]){
                nowtime = i;
                out++;
            }

        }
        System.out.println(out);
    }
}

总结

用Java解题一般用Scanner类来进行输入，但对时间要求严格的题，用它可能会超时，POJ1823的时候就遇到这样的问题，后改用StreamTokenizer类进行输入才能AC。后者处理输入的效率要高点。

1、类java.io.StreamTokenizer可以获取输入流并将其分析为Token（标记）。
StreamTokenizer的nextToken方法读取下一个标记

2、默认情况下，StreamTokenizer认为下列内容是Token:字母、数字、除c和c++注释符号以外的其他符号。
如符号“/”不是Token，注释后的内容也不是，而”/”是Token。单引号和双引号以及其总的内容，只能算一个Token。

3、为了提高效率，使用BufferedReader，如下，创建StreamTokenizer对象

StreamTokenizer st =new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

4、为了从流中获取标记，可以调用StreamTokenizer的nextToken()方法。调用nextToken()方法以后，如果标记是字符串，可用 String s=st.sval,如果是整数用 int n=(int) st.nval得到。

st.nextToken();     
int i = (int)st.nval;     //st.navl默认解析出的格式是double

st.nextToken();     
int j = (int)st.nval; 

st.nextToken();     
String s = st.sval;

问题:

  int nowtime = 0;
        int out = 0;
        for (int i = 0; i < match.length; i++) {
            if(nowtime <= match[i]){
                nowtime = i;
                out++;
            }

        }
        System.out.println(out);
    }

这部分代码我现在还是不太明白

排序问题

P1271 【深基9.例1】选举学生会

【深基9.例1】选举学生会

题目描述

学校正在选举学生会成员，有 n n n（ n ≤ 999 n\le 999 n≤999）名候选人，每名候选人编号分别从 1 1 1 到 n n n，现在收集到了 m m m（ m ≤ 2000000 m \le 2000000 m≤2000000）张选票，每张选票都写了一个候选人编号。现在想把这些堆积如山的选票按照投票数字从小到大排序。

输入格式

输入 n n n 和 m m m 以及 m m m 个选票上的数字。

输出格式

求出排序后的选票编号。

样例 #1

样例输入 #1

5 10
2 5 2 2 5 2 2 2 1 2

样例输出 #1

1 2 2 2 2 2 2 2 5 5

代码如下:
自己写的一直卡在60分,有两个点没过!

package exercise.luogu.sort.two;
import java.util.Scanner;

public class P1271 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[m];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextInt();
        }
        shellSort2(arr);
    }

    public static void shellSort2(int[] arr) {
        for (int gap = arr.length / 2; gap > 0; gap = gap / 2) {
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int tmp = arr[j];
                if (arr[j] < arr[j - gap]) {
                    while (j - gap >= 0 && tmp < arr[j - gap]) {
                        //移动
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    arr[j] = tmp;
                }
            }
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

看别人的题解

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] a = new int[sc.nextInt() + 1];
        int m = sc.nextInt();
        for (int i = 0; i < m; i++)
            a[sc.nextInt()]++;
        StringBuilder s = new StringBuilder();  // 创建字符串缓冲区对象,用于存储数据
        for (int i = 1; i < a.length; i++)
            while (a[i]-- != 0)
                s.append(i + " ");  // 追加空格
        System.out.println(s);
    }
}

总结

1.我自己写的有点复杂,别人写的是一个很好的结构.
2.a数组作为每个人的票数.
3.通过边a数组,可以得到每个人的票数,之间字符串拼接即可;

二分查找问题

P2249 【深基13.例1】查找

题目描述

输入 n n n 个不超过 1 0 9 10^9 109 的单调不减的（就是后面的数字不小于前面的数字）非负整数 a 1 , a 2 , … , a n a_1,a_2,\dots,a_{n} a1​,a2​,…,an​，然后进行 m m m 次询问。对于每次询问，给出一个整数 q q q，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 − 1 -1 −1 。
输入格式

第一行 2 2 2 个整数 n n n 和 m m m，表示数字个数和询问次数。

第二行 n n n 个整数，表示这些待查询的数字。

第三行 m m m 个整数，表示询问这些数字的编号，从 1 1 1 开始编号。

输出格式

输出一行， m m m 个整数，以空格隔开，表示答案。

样例 #1

样例输入 #1

11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6

样例输出 #1

1 2 -1

提示

数据保证， 1 ≤ n ≤ 1 0 6 1 \leq n \leq 10^6 1≤n≤106， 0 ≤ a i , q ≤ 1 0 9 0 \leq a_i,q \leq 10^9 0≤ai​,q≤109， 1 ≤ m ≤ 1 0 5 1 \leq m \leq 10^5 1≤m≤105

本题输入输出量较大，请使用较快的 IO 方式。

代码如下:
自己写的一直卡在80分,有两个点没过!

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[n];
        int[] crr = new int[m];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextInt();
        }
        for (int i = 0; i < crr.length; i++) {
            crr[i] = sc.nextInt();
            int index = binarySearch(arr, crr[i]);
            if (index == -1) {
                System.out.print(-1 + " ");
            } else {
                System.out.print((index + 1) + " ");
            }
        }
    }

    public static int binarySearch(int[] arr, int findValue) {
        return binarySearchHelper(arr, 0, arr.length - 1, findValue, -1);
    }

    public static int binarySearchHelper(int[] arr, int left, int right, int findValue, int result) {
        if (left > right) {
            return result;
        }
        int mid = left + (right - left) / 2;
        if (arr[mid] < findValue) {
            return binarySearchHelper(arr, mid + 1, right, findValue, result);
        } else if (arr[mid] > findValue) {
            return binarySearchHelper(arr, left, mid - 1, findValue, result);
        } else {
            return binarySearchHelper(arr, left, mid - 1, findValue, mid);
        }
    }
}

看别人的题解

import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Scanner;
 
public class Main {
	static int num[];
	public static void main(String[] args) throws Exception{
		Read sc=new Read();
		int n=sc.nextInt();
		int m=sc.nextInt();
		num=new int[n];
		for(int i=0;i<n;i++) {
			num[i]=sc.nextInt();
		}
		while(m-->0) {
			int target=sc.nextInt();
			int left=0;
			int right=n-1;
			while(left<right) {//二分模板
				int mid=(left+right)/2;
				 if(num[mid]<target) {
					left=mid+1;
				}
				else if(num[mid]>=target) {
					right=mid;
				}
			}
			if(num[left]==target)
				System.out.print((left+1)+" ");
			else {
				System.out.print("-1 ");
			}
		}
		
	}
}
//快读
class Read{
	StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	public int nextInt() throws Exception{
		st.nextToken();
		return (int)st.nval;
	}
}

总结

1.首先使用StreamTokenizer 输入的话比Scanner要快
2.这个二分查找的算法也比我写的要好

分治问题

P1115 最大子段和

最大子段和

题目描述

给出一个长度为 n n n 的序列 a a a，选出其中连续且非空的一段使得这段和最大。

输入格式

第一行是一个整数，表示序列的长度 n n n。

第二行有 n n n 个整数，第 i i i 个整数表示序列的第 i i i 个数字 a i a_i ai​。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

7
2 -4 3 -1 2 -4 3

样例输出 #1

4

提示

样例 1 解释

选取 [ 3 , 5 ] [3, 5] [3,5] 子段 { 3 , − 1 , 2 } \{3, -1, 2\} {3,−1,2}，其和为 4 4 4。

数据规模与约定

  • 对于 40 % 40\% 40% 的数据，保证 n ≤ 2 × 1 0 3 n \leq 2 \times 10^3 n≤2×103。
  • 对于 100 % 100\% 100% 的数据，保证 1 ≤ n ≤ 2 × 1 0 5 1 \leq n \leq 2 \times 10^5 1≤n≤2×105， − 1 0 4 ≤ a i ≤ 1 0 4 -10^4 \leq a_i \leq 10^4 −104≤ai​≤104。

代码如下

自己写的代码,第一个点出错

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();//行数和列数
        int[] nums = new int[n];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = sc.nextInt();
        }
        int maxSum = nums[0];
        int currentNum = nums[0];
        for (int i = 0; i < nums.length; i++) {
            currentNum=Math.max(nums[i],currentNum+nums[i]);
            maxSum=Math.max(maxSum,currentNum);
        }
        System.out.println(maxSum);
    }
}

别人的题解!

分治方法

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int a[]=new int[n];
		long f[]=new long[n+1];
		for(int i=0;i<n;i++)
		{
			a[i]=sc.nextInt();
		}
		long max=a[0];
		f[0]=0;
		for(int i=0;i<n;i++)
		{
			f[i+1]=a[i];
			f[i+1]=Math.max(f[i+1],f[i]+a[i]);
			max=Math.max(max,f[i+1]);
		}
		System.out.println(max);
	}

}

动态规划方法

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
         int n= s.nextInt();
         int[] a=new int[n+1];
         for(int i=1;i<=n;i++){
             a[i]=s.nextInt();
         }
     int[] dp=new int[n+1];
     int ans=Integer.MIN_VALUE;
     for(int i=1;i<=n;i++)
     {
         if(i==1){dp[i]=a[i];}
         else {
             dp[i]=Math.max(a[i],dp[i-1]+a[i]);
         }
         ans=Math.max(ans,dp[i]);
     }
        System.out.println(ans);
}
}

总结

我看不懂他的代码啊!!!

动态规划问题

P1616 疯狂的采药

疯狂的采药

题目背景

此题为纪念 LiYuxiang 而生。

题目描述

LiYuxiang 是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同种类的草药，采每一种都需要一些时间，每一种也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是 LiYuxiang，你能完成这个任务吗？

此题和原题的不同点：

1 1 1. 每种草药可以无限制地疯狂采摘。

2 2 2. 药的种类眼花缭乱，采药时间好长好长啊！师傅等得菊花都谢了！

输入格式

输入第一行有两个整数，分别代表总共能够用来采药的时间 t t t 和代表山洞里的草药的数目 m m m。

第 2 2 2 到第 ( m + 1 ) (m + 1) (m+1) 行，每行两个整数，第 ( i + 1 ) (i + 1) (i+1) 行的整数 a i , b i a_i, b_i ai​,bi​ 分别表示采摘第 i i i 种草药的时间和该草药的价值。

输出格式

输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

样例 #1

样例输入 #1

70 3
71 100
69 1
1 2

样例输出 #1

140

提示

数据规模与约定

  • 对于 30 % 30\% 30% 的数据，保证 m ≤ 1 0 3 m \le 10^3 m≤103 。
  • 对于 100 % 100\% 100% 的数据，保证 1 ≤ m ≤ 1 0 4 1 \leq m \le 10^4 1≤m≤104， 1 ≤ t ≤ 1 0 7 1 \leq t \leq 10^7 1≤t≤107，且 1 ≤ m × t ≤ 1 0 7 1 \leq m \times t \leq 10^7 1≤m×t≤107， 1 ≤ a i , b i ≤ 1 0 4 1 \leq a_i, b_i \leq 10^4 1≤ai​,bi​≤104。

代码如下:
自己的代码90分,有一个点不过



import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        int n = sc.nextInt();
        int[] val = new int[n];
        int[] time = new int[n];
        int dp[] = new int[t + 1];

        for (int i = 0; i < n; i++) {
            time[i] = sc.nextInt();
            val[i] = sc.nextInt();
        }

        // 完全背包问题：每种药材都可以采多次
        for (int i = 0; i < n; i++) { // 遍历每种药材
            for (int j = time[i]; j <= t; j++) { // 遍历背包容量，注意从time[i]开始
                // 当前药材可以放入背包中，比较放入与不放入哪种情况价值更高
                dp[j] = Math.max(dp[j], dp[j - time[i]] + val[i]);
            }
        }
        System.out.println(dp[t]);
    }
}

别人的代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        int m = sc.nextInt();
        long[] dp = new long[t + 1];
        int[] w = new int[m];
        int[] v = new int[m];
        for (int i = 0; i < m; i++) {
            w[i]=sc.nextInt();
            v[i]=sc.nextInt();
        }
        for (int i = 0; i < m; i++) {
            for (int j = w[i]; j <= t; j++) {
                dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
            }
        }
        System.out.println(dp[t]);
    }
}

总结

dp使用int会超范围,要改成long就行了

本文含有隐藏内容，请 开通VIP 后查看

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布