忻州网络公司网站建设,深圳企业网站制作公司哪家好,聊城网站开发培训,上海市城市建设工程学校网站贪心问题
P1803 凌乱的yyy / 线段覆盖
凌乱的yyy / 线段覆盖
题目背景
快 noip 了#xff0c;yyy 很紧张#xff01;
题目描述
现在各大 oj 上有 n n n 个比赛#xff0c;每个比赛的开始、结束的时间点是知道的。
yyy 认为#xff0c;参加越多的比赛#xff0c;no…贪心问题
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 (aibi)表示比赛开始、结束的时间。
输出格式
一个整数最多参加的比赛数目。
样例 #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≤aibi≤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();ListRace 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的数值表示即nvalint n (int) n1.nval;int[] match new int[1000001];//match数组初始化为-1Arrays.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 sst.sval,如果是整数用 int n(int) st.nval得到。
st.nextToken();
int i (int)st.nval; //st.navl默认解析出的格式是doublest.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 scnew Read();int nsc.nextInt();int msc.nextInt();numnew int[n];for(int i0;in;i) {num[i]sc.nextInt();}while(m--0) {int targetsc.nextInt();int left0;int rightn-1;while(leftright) {//二分模板int mid(leftright)/2;if(num[mid]target) {leftmid1;}else if(num[mid]target) {rightmid;}}if(num[left]target)System.out.print((left1) );else {System.out.print(-1 );}}}
}
//快读
class Read{StreamTokenizer stnew 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) {currentNumMath.max(nums[i],currentNumnums[i]);maxSumMath.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 stubScanner scnew Scanner(System.in);int nsc.nextInt();int a[]new int[n];long f[]new long[n1];for(int i0;in;i){a[i]sc.nextInt();}long maxa[0];f[0]0;for(int i0;in;i){f[i1]a[i];f[i1]Math.max(f[i1],f[i]a[i]);maxMath.max(max,f[i1]);}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[] anew int[n1];for(int i1;in;i){a[i]s.nextInt();}int[] dpnew int[n1];int ansInteger.MIN_VALUE;for(int i1;in;i){if(i1){dp[i]a[i];}else {dp[i]Math.max(a[i],dp[i-1]a[i]);}ansMath.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) (m1) 行每行两个整数第 ( i 1 ) (i 1) (i1) 行的整数 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就行了
