做汽车配件的都在那个网站做呀,上传网站内容,企业网站建站系统,中国包装设计网参考
【算法2-2】常见优化技巧 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) P1102 A-B 数对P1638 逛画展P1115 最大子段和P7072 [CSP-J2020] 直播获奖P2671 [NOIP2015 普及组] 求和P4147 玉蟾宫P2866 [USACO06NOV] Bad Hair Day SP1950 长方形P2032 扫描P2216 [HAOI…参考
【算法2-2】常见优化技巧 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) P1102 A-B 数对P1638 逛画展P1115 最大子段和P7072 [CSP-J2020] 直播获奖P2671 [NOIP2015 普及组] 求和P4147 玉蟾宫P2866 [USACO06NOV] Bad Hair Day SP1950 长方形P2032 扫描P2216 [HAOI2007] 理想的正方形UVA11572 唯一的雪花 Unique SnowflakesP4653 [CEOI2017] Sure BetP3143 [USACO16OPEN] Diamond Collector SP7910 [CSP-J 2021] 插入排序P1578 奶牛浴场P3467 [POI2008] PLA-PosteringP1886 滑动窗口 /【模板】单调队列P2880 [USACO07JAN] Balanced Lineup GP1714 切蛋糕P1725 琪露诺
双指针
一般来说双指针可以优化原本需要O(n2)时间的遍历求连续区间满足某一条件的这种问题而且数据规模比较大
P1102 A-B 数对
1-6二分做过。
package _1_6;import java.io.*;
import java.util.Arrays;public class P1102 {private static StreamTokenizer in;private static PrintWriter out;private static long[] nums;private static long c;private static int n;public static void main(String[] args) throws IOException {in new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));out new PrintWriter(System.out);in.nextToken();n (int) in.nval;in.nextToken();c (long) in.nval;nums new long[n];for (int i 0; i n; i) {in.nextToken();nums[i] (long) in.nval;}// 先排序Arrays.sort(nums);// algo 双指针long count 0;int l 0, r 0;for (int i 0; i n; i) {// 找到第一个nums[l]-nums[i]c,nums[r]-nums[i]c则l~r-1区间就是-nums[i]cwhile (l n nums[l] - nums[i] c) l;while (r n nums[r] - nums[i] c) r;// 如果ln则表示找不到对应值if (l n nums[l] - nums[i] c r 1 nums[r - 1] - nums[i] c)count r - l;}out.println(count);out.flush();out.close();}
}P1638 逛画展
看着n的数量级只能O(n)时间才AC可以用双指针
package _2_2;import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;public class P1638 {private static StreamTokenizer in;public static void main(String[] args) throws IOException {in new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));int n nextInt();int m nextInt();int[] draws new int[n 1];// visited存当前范围包含了画师i的次数int[] visited new int[m 1];// cnt表示包含了画师的种数int cnt 0;for (int i 1; i n; i) {draws[i] nextInt();}// algo 双指针int l, r;l 1;r l - 1;// r右移一直到包含所有画师while (cnt ! m r n - 1) {r;// 如果当前这幅画的画师没有被包含那就加入if (visited[draws[r]] 0) {cnt;}visited[draws[r]] 1;}// 去除左端重复的画师while (r - l 1 m visited[draws[l]] 1) {visited[draws[l]]--;l;}if (r - l 1 m) {System.out.printf(%d %d, l, r);return;}// 此时lr区间已经满足了条件包含所有画师的目前最短但是也有可能后续还有更短的区间// 继续r1每次去除左端重复如果区间更小了那就更新如果相同不更新因为多组解得l更小的int minl l, minr r;while (r n - 1) {r;visited[draws[r]] 1;// 去除左端重复的画师while (r - l 1 m visited[draws[l]] 1) {visited[draws[l]]--;l;}// 更新更短的区间if (r - l minr - minl) {minr r;minl l;}}System.out.printf(%d %d, minl, minr);}public static int nextInt() throws IOException {in.nextToken();return (int) in.nval;}
}
空间换时间
题外话之前不是有一道异或题吗4Mb的空间Java根本AC不了
P7072 [CSP-J2020] 直播获奖
首先想到的就是每次读入选手的成绩后排序然后求出前w%个人的最低成绩。
Java的Arrays.sort用了一个TimSort时间复杂度是O(ologn)。不过注释说如有部分排序了那这个算法的实际时间远低于nlgn。
不过这样的话这个朴素的写法的时间复杂度是O(n2logn)可以过104的数量级但是后面三个105就TLE。
这里有个注意的点Arrays.sort(T[],start,end,Comparator)这里的数组要用包装类的
package _2_2;import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.Comparator;public class P7072 {private static StreamTokenizer in;private static PrintWriter out;public static void main(String[] args) throws IOException {in new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));out new PrintWriter(System.out);int n nextInt();double w nextInt() * 0.01;Integer[] scores new Integer[n 1];for (int i 1; i n; i) {// 当前i个人前w%就是i*0.01*w个人然后再获得最后一个人的成绩scores[i] nextInt();// 降序排序,这里要用Integer包装类所以也可以选择从后面往前面选Arrays.sort(scores, 1, i 1, Comparator.reverseOrder());int t (int) (i * w);if (t 1) {t 1;}out.printf(%d , scores[t]);}out.flush();out.close();}public static int nextInt() throws IOException {in.nextToken();return (int) in.nval;}
}
关键点在排序时间上可以使用时间复杂度为O(n)的桶排序点题用空间换时间1-2曾做到过一道桶排序。因为桶排序不是比较排序所以不受O(ologn)的限制比较排序这个时间复杂度是最优的了。还有一点题中的值范围600所以空间也不用开很大也可以想到桶排序。
package _2_2;import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.Comparator;public class P7072 {private static StreamTokenizer in;private static PrintWriter out;public static void main(String[] args) throws IOException {in new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));out new PrintWriter(System.out);int n nextInt();double w nextInt() * 0.01;int[] scores new int[605];for (int i 1; i n; i) {scores[nextInt()];// 当前i个人前w%就是i*0.01*w个人然后再获得最后一个人的成绩int t (int) (i * w);if (t 1) {t 1;}// 找第t个人的分数注意降序int j;for (j 604; j 0; j--) {if (scores[j] 0) {// 这里会对scores操作所以一次性-去这样就不会改变scores了反正判断也是t0t - scores[j];}// 因为可能重分所以t0的时候也算找到分数线if (t 0) {out.printf(%d , j);break;}}}out.flush();out.close();}public static int nextInt() throws IOException {in.nextToken();return (int) in.nval;}
}
P2671 [NOIP2015 普及组] 求和
按照颜色分组想到了把等式移相一下没想到。
单调栈
P2866 [USACO06NOV] Bad Hair Day S
什么是单调栈单调栈(C/C)-CSDN博客 就是栈里维护一个单调序列可解题型如下往一边找第一个比自身大/小的值 以这道题为例都是往右边找第一个自身条件的数所以从后往前遍历。 如果栈空直接保存结果-1如果栈顶元素满足条件自身直接保存结果为栈顶元素此题要的是下标比较的时候用的是下标对应值如果栈顶元素不满足条件自身则出栈直到情况1或2。 package _2_2;import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.LinkedList;public class P2866 {private static StreamTokenizer in;private static int n;private static int[] hs;private static LinkedListInteger stack;public static void main(String[] args) throws IOException {in new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));n nextInt();hs new int[n 1];stack new LinkedListInteger();for (int i 1; i n; i) {hs[i] nextInt();}long cnt 0;// 注意从后往前遍历for (int i n; i 0; i--) {int t findHeigher(i);if (t -1) {cnt n - i;} else {cnt t - i - 1;}}System.out.println(cnt);}// algo 单调栈public static int findHeigher(int i) {// 弹出栈顶直到满足情况1或2返回结果(注意栈里存的是下标)压入当前值while (stack.size() 0 hs[stack.getFirst()] hs[i]) {stack.removeFirst();}// 栈空返回结果-1压入当前值if (stack.size() 0) {stack.addFirst(i);return -1;} else {// 这里要先获取栈顶元素再压栈int t stack.getFirst();stack.addFirst(i);return t;}}public static int nextInt() throws IOException {in.nextToken();return (int) in.nval;}
}
单调队列
P1886 滑动窗口 /【模板】单调队列
什么是单调队列单调队列 - Lan_Sky - 博客园 (cnblogs.com)、[数据结构]–单调队列-CSDN博客 单调队列通常解决动态小区间中寻找极值问题。 动态区间找最小值使用单调递增序列队首就是最小值动态区间找最大值使用单调递减序列队首就是最大值 中间操作都是类似的例如找最小值要维护单调递增序列 如果当前遍历到的值违反了队列的单调要求那么就要把元素从队尾出队每次都要把新元素从队尾入队。 如果当前队列中的元素的下标已经不在滑动窗口内了则这个值从队首出队。 为什么最小值是维护单调递增序列可以见2。
因为窗口在滑动所以即使目前这个值不是最小的但是窗口滑动之后他有可能成为最小的因为他被放在了极小的后面窗口又向右边滑动所以要存起来。但是如果当前这个值比队列一些元素都小放入队列后即使找最小值也已经不可能再找队首那部分的值了都有更小的了所以前面的要出队。
package _2_2;import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.LinkedList;public class P1886 {private static StreamTokenizer in;private static PrintWriter out;private static LinkedListInteger queue;public static void main(String[] args) throws IOException {in new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));out new PrintWriter(System.out);int n nextInt();int k nextInt();int[] num new int[n 1];for (int i 1; i n; i) {num[i] nextInt();}// algo 单调队列queue new LinkedListInteger();// 求最小值维护递增队列for (int i 1; i n; i) {// 把队首部分不在滑动窗口内的值去掉这里i属于窗口右边界窗口部分i-k1~iwhile (queue.size() 0 queue.getFirst() (i - k 1)) {queue.removeFirst();}// 从队尾开始维护队列单调递增while (queue.size() 0 num[queue.getLast()] num[i]) {queue.removeLast();}// 入队queue.add(i);// 输出当前最值注意右边界i从k开始才算一个完整窗口if (i k) {out.printf(%d , num[queue.getFirst()]);}}out.println();queue.clear();// 求最大值维护递减队列for (int i 1; i n; i) {// 把队首部分不在滑动窗口内的值去掉这里i属于窗口右边界窗口部分i-k1~iwhile (queue.size() 0 queue.getFirst() (i - k 1)) {queue.removeFirst();}// 从队尾开始维护队列单调递减while (queue.size() 0 num[queue.getLast()] num[i]) {queue.removeLast();}// 入队queue.add(i);// 输出当前最值注意右边界i从k开始才算一个完整窗口if (i k) {out.printf(%d , num[queue.getFirst()]);}}out.flush();out.close();}public static int nextInt() throws IOException {in.nextToken();return (int) in.nval;}
}
60%AC有几个TLE那换静态数组
package _2_2;import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.LinkedList;public class P1886 {private static StreamTokenizer in;private static PrintWriter out;private static LinkedListInteger queue;private static int n;private static int k;private static int[] nums;public static void main(String[] args) throws IOException {in new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));out new PrintWriter(System.out);n nextInt();k nextInt();nums new int[n 1];for (int i 1; i n; i) {nums[i] nextInt();}fun2();out.flush();out.close();}// algo 单调队列静态数组版public static void fun2() {int[] queue new int[n 1];// 双指针指向队首尾此时sizetail-head1所以表示空即tail1headint head 1, tail 0;// 求最小值维护递增队列for (int i 1; i n; i) {// 把队首部分不在滑动窗口内的值去掉这里i属于窗口右边界窗口部分i-k1~iwhile (tail - head 1 0 queue[head] (i - k 1)) {head;}// 从队尾开始维护队列单调递增while (tail - head 1 0 nums[queue[tail]] nums[i]) {tail--;}// 入队queue[tail] i;// 输出当前最值注意右边界i从k开始才算一个完整窗口if (i k) {out.printf(%d , nums[queue[head]]);}}out.println();queue new int[n 1];head 1;tail 0;// 求最大值维护递减队列for (int i 1; i n; i) {// 把队首部分不在滑动窗口内的值去掉这里i属于窗口右边界窗口部分i-k1~iwhile (tail - head 1 0 queue[head] (i - k 1)) {head;}// 从队尾开始维护队列单调递增while (tail - head 1 0 nums[queue[tail]] nums[i]) {tail--;}// 入队queue[tail] i;// 输出当前最值注意右边界i从k开始才算一个完整窗口if (i k) {out.printf(%d , nums[queue[head]]);}}}public static int nextInt() throws IOException {in.nextToken();return (int) in.nval;}
}
就多了一个AC
区间最值
P4147 玉蟾宫
P1950 长方形
P2216 [HAOI2007] 理想的正方形
都是提高题
浅谈用极大化思想解决最大子矩形问题-CSDN博客
