瑞安 网站建设,域名解析网站登录,网站建设是如何寻找客户的,wordpress手机版app导航重新排序
问题描述
给定一个数组 A 和一些查询 Li,Ri 求数组中第 Li 至第 Ri个元素之和。
小蓝觉得这个问题很无聊, 于是他想重新排列一下数组, 使得最终每个查询结果的和尽可能地大。小蓝想知道相比原数组, 所有查询结果的总和最多可以增加多少?
输入格式
输入第一行包含…重新排序
问题描述
给定一个数组 A 和一些查询 Li,Ri 求数组中第 Li 至第 Ri个元素之和。
小蓝觉得这个问题很无聊, 于是他想重新排列一下数组, 使得最终每个查询结果的和尽可能地大。小蓝想知道相比原数组, 所有查询结果的总和最多可以增加多少?
输入格式
输入第一行包含一个整数 n 。
第二行包含 n 个整数 A1,A2,⋯ ,An相邻两个整数之间用一个空格分隔。
第三行包含一个整数 m 表示查询的数目。
接下来 m 行, 每行包含两个整数 Li、Ri相邻两个整数之间用一个空格分隔。
输出格式
输出一行包含一个整数表示答案。
样例输入
5
1 2 3 4 5
2
1 3
2 5样例输出
4样例说明
原来的和为 6142061420, 重新排列为 (1,4,5,2,3)(1,4,5,2,3) 后和为 101424101424, 增 加了 4。
运行限制
最大运行时间1s最大运行内存: 512M
思路分析
要想排列前后差值最大排列前的初始数组我们无法控制那么就只能想办法改变排列后的数组让最大的数放在位置出现最多次的地方进一步来说就是最大的数要出现最多次然后依次递减数的大小和位置出现的次数那么如何去判断哪个位置出现了多少次呢
不妨定义一个count数组来表示如果l,r这段被求一次那么这一段区间内的出现次数就都需要1这不正是差分所能实现的吗因此我们不妨每次count[l];count[r1]--;然后进行差分操作自然就将每个位置的出现次数计算出了再将其排序同时与排序过的原数组对应位置一一相乘得到的值无疑是最大的
为什么直接相乘就可以
因为我们的count数组存的是位置出现次数我们要求的让他是和最大的数相乘而较小的那些数刚好会乘以count数组中的0因此得到的值就是要求。
代码实现
package com.zxy.exam;import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;public class _重新排序 {static int N 100010;static long[] arr new long[N];//原数组static long[] count new long[N];//位置出现次数static long[] b new long[N];//前缀和数组static int n,m;static long sum1,sum2;static BufferedReader bf new BufferedReader(new InputStreamReader(System.in));static PrintWriter pw new PrintWriter(System.out);public static void main(String[] args) throws IOException {String s bf.readLine();n Integer.parseInt(s);String[] s1 bf.readLine().split( );for (int i 1; i n; i) {arr[i]Integer.parseInt(s1[i-1]);//读入数据b[i]b[i-1]arr[i];//前缀和}s bf.readLine();m Integer.parseInt(s);while(m -- 0){String[] s2 bf.readLine().split( );int l Integer.parseInt(s2[0]);int r Integer.parseInt(s2[1]);sum1b[r]-b[l-1];count[l];count[r1]--;}for (int i 1; i n; i) {count[i]count[i-1];}Arrays.sort(arr);Arrays.sort(count);//count数组特别大而且有很多0因此一定要遍历到最后一位或者就从最后一位倒着遍历/*int pN-1;while (count[p]!0){sum2 count[p]*arr[p];//更新后的和p--;}*/for (int i 1; i N-1; i) {sum2 count[i]*arr[i];}System.out.println(sum2-sum1);}
}
找素数
这道题目很简单找到第1000002个素数但是素数是蓝桥杯的高频考点一定要复习一下
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {int ans 0;int i 2;while(true){if (isPrime(i)){ans;if(ans 100002){System.out.println(i);return;}}i;} }static boolean isPrime(int n) {for(int i 2; i (int) Math.sqrt(n); i){if (n % i 0){return false;}}return true;}
}卡牌
问题描述
这天, 小明在整理他的卡牌。
他一共有 n 种卡牌, 第 i 种卡牌上印有正整数数 i(i∈[1,n]), 且第 i 种卡牌 现有 ai 张。
而如果有 n 张卡牌, 其中每种卡牌各一张, 那么这 nn 张卡牌可以被称为一 套牌。小明为了凑出尽可能多套牌, 拿出了 m 张空白牌, 他可以在上面写上数 i, 将其当做第 i 种牌来凑出套牌。然而小明觉得手写的牌不太美观, 决定第 ii 种牌最多手写 bi 张。
请问小明最多能凑出多少套牌?
输入格式
输入共 3 行, 第一行为两个正整数 n,m。
第二行为 n 个正整数 a1,a2,…,an。
第三行为 n 个正整数 b1,b2,…,bn 。
输出格式
一行, 一个整数表示答案。
样例输入
4 5 1 2 3 4 5 5 5 5
样例输出
3
样例说明
这 5 张空白牌中, 拿 2 张写 1 , 拿 1 张写 2 , 这样每种牌的牌数就变为了 3,3,3,4, 可以凑出 3 套牌, 剩下 2 张空白牌不能再帮助小明凑出一套。
评测用例规模与约定 对于 30%的数据, 保证 n≤2000;
对于 100% 的数据, 保证 n≤2×105;ai,bi≤2*n;m≤n2 。
运行限制
最大运行时间1s 最大运行内存: 512M
分析
很明显的二分题目mid是可以凑出的套数如果mid可以满足条件也就是mid这个套数是可以实现的那么比mid小的所有套数也一定是可以实现的因此答案在mid-r中也就是lmid。
另一个难点就是如何判断这个套数是否能实现也即是check函数的写法我们定义t为套数还要定义tmp表示万能牌的数量这里需要枚举每一种牌如果ta[i]那么这种牌就可以实现直接continue节省时间如果ta[i]b[i]那么很明显实现不了如果ta[i]tmp那么也是实现不了的那么剩下的就是a[i]配合万能牌可能实现t的情况了t-a[i]tmp那么我们的万能拍就被消耗了这么多张tmp就要减去差值如果a[i]配合万能牌也不够t那就实现不了。
代码实现
package com.zxy.exam;import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;public class _卡牌 {static BufferedReader bf new BufferedReader(new InputStreamReader(System.in));static PrintWriter pw new PrintWriter(System.out);static int N 100010;static int[] a new int[N];static int[] b new int[N];static int n ;static long m;public static void main(String[] args) throws IOException {String[] s bf.readLine().split( );n Integer.parseInt(s[0]);m Integer.parseInt(s[1]);s bf.readLine().split( );for (int i 0; i s.length; i) {a[i]Integer.parseInt(s[i]);}s bf.readLine().split( );for (int i 0; i s.length; i) {b[i]Integer.parseInt(s[i]);}int l 0;int r n*2;while (l r){int mid l r 1 1;if (check(mid)){l mid;}else r mid - 1;}pw.println(l);pw.flush();}private static boolean check(int t) {long tmp m;for (int i 0; i n; i) {if (a[i]t) continue;if (b[i]a[i]t) return false;if (tmp a[i] t) return false;if (t - a[i] tmp){tmp - (t-a[i]);}else {return false;}}return true;}
}
染色时间
问题描述
小蓝有一个 n 行 m* 列的白色棋盘, 棋盘的每一个方格都可以被染成彩色。
每个方格有一个染色时间 tij*, 不同方格的染色时间可能不同。如果一个方 格被触发了染色, 这个方格就会在 tij 秒之后变成彩色, 然后将自己上下左右四 个方向相邻的方格触发染色。每个方格只能被触发染色一次, 第一次触发之后 的触发为无效触发。
给定每个方格的染色时间, 在时刻 0 触发第一行第一列的方格染色, 请问 多长时间后整个棋盘完成染色。
输入格式
输入的第一行包含两个整数 n,m, 分别表示棋盘的行数和列数。
接下来 n* 行, 每行 m 个正整数, 相邻的整数之间用一个空格分隔, 表示每 个方格的染色时间。该部分的第 i* 行第 j* 个整数表示 tij, 即第 i* 行第 j* 列的方 格的染色时间。
输出格式
输出一行包含一个整数, 表示整个棋盘完成染色的时间。
样例输入
2 31 2 34 5 6样例输出
12运行限制
最大运行时间1s最大运行内存: 256M
分析
这道题目很明显的dfs模板题需要注意的是这个染色时间他是四个方向同时进行的因此我们要找的是最大的时间所以count要不断进行比较从而找到消耗时间最多的那个格子。
需要注意的是自己手写的这个储存坐标的类一定要重写Comparable方法否则无法顺利存如队列中
代码实现
package com.zxy.exam;import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class _染色时间 {static int N 510;static int[][] a new int[N][N];static int[] dx {-1,0,1,0};static int[] dy {0,1,0,-1};static int count 0;static int n,m;public static void main(String[] args) {Scanner scan new Scanner(System.in);n scan.nextInt();m scan.nextInt();for (int i 0; i n; i) {for (int j 0; j m; j) {a[i][j]scan.nextInt();}}dfs();}private static void dfs() {QueueColor q new LinkedList();q.add(new Color(0,0,a[0][0]));a[0][0]0;while (!q.isEmpty()){Color tmp q.poll();if (tmp.getTime() count ){count tmp.getTime();}for (int i 0; i 4; i) {int x dx[i]tmp.x;int y dy[i] tmp.y;if (x 0 x m y 0 y m a[x][y]0){q.add(new Color(x,y,tmp.timea[x][y]));a[x][y]0;}}}System.out.println(count);}}
class Color implements ComparableColor{int x;int y;int time;Overridepublic int compareTo(Color o) {return this.time - o.time;}public Color(int x, int y, int time) {this.x x;this.y y;this.time time;}public int getX() {return x;}public void setX(int x) {this.x x;}public int getY() {return y;}public void setY(int y) {this.y y;}public int getTime() {return time;}public void setTime(int time) {this.time time;}
}
