第四讲 枚举、模拟与排序-爱代码爱编程
文章目录
1.连号区间数(枚举💡skill)
思路:
小技巧:如果在区间[L,R]中,maxnn-minnR-L,则说明[L,R]区间的数是递增的。
很多时候都会用到
对于此题,我们只需要枚举l.r判断是否满足此关系式即可。如果满足那么这个区间的数排序后肯定是递增且连续的。
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int N = 10010;
static int[] a= new int[N];
static int n = 0,ans = 0;
public static void main(String[] args) throws Exception{
n = Integer.parseInt(br.readLine());
String[] aa = br.readLine().split(" ");
for(int i = 1; i <= n; i++) {
a[i] = Integer.parseInt(aa[i - 1]);
}
for(int i = 1; i <= n; i++) {
int maxn = a[i];
int minn = a[i];
for(int j = i; j <= n; j++) {
maxn = Math.max(maxn, a[j]);
minn = Math.min(minn,a[j]);
if(j - i == maxn - minn) {
ans++;
}
}
}
out.println(ans);
out.flush();
}
}
2.递增三元组(❤️前缀和/二分❤️)
💡💡💡法1:前缀和
借助B当作中间数,查找A中有多少个比B小的,C中有多少个比B大的;
我们需要记住A和C中每个数字出现的次数,采用num_a,num_c表示每个数出现的次数。
借助临时数组s[]表示所有数出现次数的前缀和。sum_a[]表示A的前缀和,sum_c[]表示c的前缀和
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int N = 100010;
static int[] a= new int[N];
static int[] b= new int[N];
static int[] c= new int[N];
static int[] num_a= new int[N];
static int[] num_c= new int[N];
static int[] sum_a= new int[N];
static int[] sum_c= new int[N];
static int[] s = new int[N];
static int n = 0;
static long ans = 0;
public static void main(String[] args) throws Exception{
input();
for(int i = 1; i < N; i++) {
s[i] = s[i - 1] + num_a[i];//a中1-i所有数出现的总数
}
for(int i = 1; i <= n; i++) {
sum_a[i] = s[b[i] - 1]; //小于bi的数有多少个
}
Arrays.fill(s, 0);
for(int i = 1; i < N; i++) {//注意此时的数据范围
s[i] = s[i - 1] + num_c[i];//a中1-i所有数出现的总数
}
for(int i = 1; i <= n; i++) {
sum_c[i] = s[N - 1] - s[b[i]]; //大于b[i]的数有多少个
}
for(int i = 1; i <= n;i++) {
ans = ans + (long)sum_a[i] * sum_c[i];
}
out.println(ans);
out.flush();
}
private static void input() throws Exception, Exception {
n = Integer.parseInt(br.readLine());
String[]aa = br.readLine().split(" ");
for(int i = 1; i <= n; i++) {
a[i] = Integer.parseInt(aa[i - 1]) + 1;
num_a[a[i]]++;
}
String[]bb = br.readLine().split(" ");
for(int i = 1; i <= n; i++) {
b[i] = Integer.parseInt(bb[i - 1]) + 1;
}
String[]cc = br.readLine().split(" ");
for(int i = 1; i <= n; i++) {
c[i] = Integer.parseInt(cc[i - 1]) + 1;
num_c[c[i]]++;
}
}
}
💡💡💡法2:二分
依旧是以B为分割点,将A和C数组排序,此时满足单调性,我们在A中找小于target的最后一个,在C中找大于target的第一个(后面的元素肯定都是大于target的)然后相乘即可。
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int N = 100010;
static int[] a= new int[N];
static int[] b= new int[N];
static int[] c= new int[N];
static int[] num_a= new int[N];
static int[] num_c= new int[N];
static int[] sum_a= new int[N];
static int[] sum_c= new int[N];
static int[] s = new int[N];
static int n = 0;
static long ans = 0;
public static void main(String[] args) throws Exception{
input();
Arrays.sort(a,1,1+n);
Arrays.sort(c,1,1+n);
for(int i = 1; i <= n; i++) {
int target = b[i];
int la = findLess(target);
int lc = findMore(target);
// System.out.println(la +" " +lc);
ans = ans + (long)la*lc;
}
System.out.println(ans);
}
//找大于的第一个
private static int findMore(int target) {
int l = 1, r = n;
int res = -1;
while(l <= r) {
int mid = (l + r) >> 1;
if(c[mid] > target) {
res = mid;
r = mid - 1;
}else {
l = mid + 1;
}
}
if(res == -1) {
return 0;
}else {
return (n - res + 1);
}
}
//找小于的最后一个
private static int findLess(int target) {
int l = 1, r = n;
int res = -1;
while(l <= r) {
int mid = (l +r) >> 1;
if(a[mid] < target) {
res = mid;
l = mid + 1;
}else {
r = mid - 1;
}
}
if(res == -1) {
return 0;
}else {
return res;
}
}
private static void input() throws Exception, Exception {
n = Integer.parseInt(br.readLine());
String[]aa = br.readLine().split(" ");
for(int i = 1; i <= n; i++) {
a[i] = Integer.parseInt(aa[i - 1]);
}
String[]bb = br.readLine().split(" ");
for(int i = 1; i <= n; i++) {
b[i] = Integer.parseInt(bb[i - 1]);
}
String[]cc = br.readLine().split(" ");
for(int i = 1; i <= n; i++) {
c[i] = Integer.parseInt(cc[i - 1]);
}
}
}
3.特别数的和(模拟)
很简单,n很小直接取出n的每一位去判断即可。
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int n = 0;
static long ans = 0;
public static void main(String[] args) throws Exception{
n = Integer.parseInt(br.readLine());
for(int i = 1; i <= n; i++) {
if(check(i)) {
ans = ans + (long)i;
}
}
System.out.println(ans);
}
private static boolean check(int x) {
while(x != 0) {
int t = x%10;
if(t == 2 || t == 0 || t == 1 || t == 9) {
return true;
}
x/=10;
}
return false;
}
}
思路:直接记录每个数字出现的次数,在最大值和最小值之间出现2次的肯定是重号,出现0次的肯定是断号。
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int n = 0;
static long ans = 0;
static int minn = (int) (1e5 + 10),maxn = -1;
static int[] count = new int[100010];
public static void main(String[] args) throws Exception{
int t = Integer.parseInt(br.readLine());
while(t-- > 0) {
// Arrays.fill(count, 0);
String[] aa = br.readLine().split(" ");
for(int i = 0; i < aa.length; i++) {
int num = Integer.parseInt(aa[i]);
maxn = Math.max(maxn, num);
minn = Math.min(minn,num);
count[num]++;
}
}
int c = 0,d = 0;
for(int i = minn; i <= maxn; i++) {
if(count[i] == 2) {
c = i;
}
if(count[i] == 0) {
d = i;
}
}
out.println(d + " " + c);
out.flush();
}
}
4.回文日期(枚举/LocalDate👍)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.time.LocalDate;
import java.util.Arrays;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int n = 0;
static long ans = 0;
public static void main(String[] args) throws Exception{
String str1 = br.readLine();
int y1 = Integer.parseInt(str1.substring(0,4));
int m1 = Integer.parseInt(str1.substring(4,6));
int d1 = Integer.parseInt(str1.substring(6,8));
String str2 = br.readLine();
int y2 = Integer.parseInt(str2.substring(0,4));
int m2 = Integer.parseInt(str2.substring(4,6));
int d2 = Integer.parseInt(str2.substring(6,8));
LocalDate t1= LocalDate.of(y1, m1, d1);//创建指定日期的LocalDate
LocalDate t2= LocalDate.of(y2, m2, d2);
while(!t1.isEqual(t2)) {
String t = t1.toString();
if(check(t)) {
ans++;
}
t1 = t1.plusDays(1); //向后跳转1天
}
String t = t1.toString();
//需要注意当两天重合的时候,需要判断一下
if(check(t)) {
ans++;
}
System.out.println(ans);
}
private static boolean check(String t) {
//String类型可以保存前导0,如果转为数字再操作的话可能丢失前导0
String[]x = t.split("-");
String t1 = x[0] + x[1] + x[2];
// System.out.println(t1);
StringBuilder t2 = new StringBuilder(t1);
t2.reverse();
String t3 = t2.toString();//必须采用String类型的变量来接收
if(t1.equals(t3)) {
return true;
}
return false;
}
}
5.归并排序
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int N = (int) (1e5 + 10);
static int[]is1 = new int[N];
static int[]is2 = new int[N];
static int n = 0;
public static void main(String[] args) throws Exception{
n = Integer.parseInt(br.readLine());
String[] aa = br.readLine().split(" ");
for(int i = 1; i <= n; i++) {
is1[i] = Integer.parseInt(aa[i - 1]);
}
mergesort(1,n);
for(int i = 1; i <= n; i++) {
System.out.print(is1[i] + " ");
}
}
private static void mergesort(int l, int r) {
if(l >= r)return;
int mid = (l + r) /2 ;
mergesort(l, mid);
mergesort(mid + 1, r);
merge(l,mid,r);
}
private static void merge(int l, int mid, int r) {
int i = l,j = mid + 1, k = l;
while(i <= mid && j <= r) {
if(is1[i] < is1[j]) {
is2[k++] = is1[i++];
}else {
is2[k++] = is1[j++];
}
}
while(i <= mid) {
is2[k++] = is1[i++];
}
while(j <= r) {
is2[k++] = is1[j++];
}
for(i = l; i <= r; i++) {
is1[i] = is2[i];
}
}
}
6.移动距离(模拟/new💡)
思路:
两个楼之间的最短距离就是曼哈顿距离,很明显我们需要找出m和n的坐标,对宽度w取模我们可以得到行号,列号的话与所在行的奇偶有关,奇数行是正序,偶数行是逆序的(画个图理解一下)就可以找到
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int n = 0,w = 0, m = 0;
public static void main(String[] args) throws Exception{
String[] wmn = br.readLine().split(" ");
boolean rev = false;
w = Integer.parseInt(wmn[0]);
m = Integer.parseInt(wmn[1]);
n = Integer.parseInt(wmn[2]);
int fir[] = count(m);
int sec[] = count(n);
System.out.println(Math.abs(fir[0]-sec[0]) + Math.abs(fir[1] - sec[1]));
}
static int[] count(int x) {
//temp[0]是行号,temp[1]是列号
int []temp = new int[2];
int mod = x % w; //列号
if(x%w == 0){
temp[0] = x/w;
}else{
temp[0] = x/w + 1;
}
int p = temp[0] % 2;//记录行号的奇偶
if(p == 1){
if(mod==0){
temp[1] = w;
}else{
temp[1] = mod;
}
}else{
if(mod == 0){
temp[1] = 1;
}else{
temp[1] = w - mod + 1;
}
}
return temp;
}
}
7.日期问题
思路:现在给定范围内进行枚举,然后判断是否为合法日期,最后看是否与所给的数相匹配,我们枚举的时候就已经实现了按照升序排序。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int days[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
static int n = 0,w = 0, m = 0;
static int a = 0, b = 0, c = 0;
public static void main(String[] args) throws Exception{
String[]d = br.readLine().split("/");
a = Integer.parseInt(d[0]);
b = Integer.parseInt(d[1]);
c = Integer.parseInt(d[2]);
for(int i = 19600101; i <= 20591231;i ++) {
int year = i / 10000, month = i % 10000 / 100,day = i % 100;
if(check(year,month,day)) {
if(com(year%100,month,day)||com(month,day,year%100)||com(day,month,year%100)) {
out.printf("%d-%02d-%02d\n",year,month,day);
}
}
}
out.flush();
out.close();
}
private static boolean check(int year, int month, int day) {
if(month == 0 || month > 12) {return false;}
if(day == 0) {return false;}
if(((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0))){
days[2] = 29;
}
else {
days[2] = 28;
}
if(day > days[month]) {
return false;
}
return true;
}
private static boolean com(int year, int month, int day) {
if(year == a && month == b && day == c) {
return true;
}
return false;
}
}
8.航班时间(转换题意)
思路:因为保证飞行时间不超过24小时,所以d一定是1位数。
本题的难点主要是转换题意,因为题意比较抽象,代码实现并不难(一般此时我们需要借助数学的思想去转换题意)
我们可以得出:
(1)去程起飞时间+飞行时间x+时差=去程降落时间;
(2)返程起飞时间+飞行时间x-时差=返程降落时间;
我们需要求的是飞行时间x(1)+(2)得到:
去程起飞时间+2*飞行时间x+返程起飞时间=去程降落时间+返程降落时间;
x=((去程降落时间-去程起飞时间)+(返程降落时间-返程起飞时间))/2
下面直接根据公式进行计算就可以了。
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int n = 0,w = 0, m = 0;
static int a = 0, b = 0, c = 0;
public static void main(String[] args) throws Exception{
int t = Integer.parseInt(br.readLine());
while(t-- > 0) {
String[] go = br.readLine().split(" ");
String[] back = br.readLine().split(" ");
int d1 = 0,d2 = 0;
String[]g1 = go[0].split(":");//去升的时间
String[]b1 = go[1].split(":");//去降的时间
String[]g2 = back[0].split(":");//回来升的时间
String[]b2 = back[1].split(":");//回来降的时间
if(go.length == 3) {
d1 = go[2].charAt(2) - '0';
}
if(back.length == 3) {
d2 = back[2].charAt(2) - '0';
}
int ans1 = get_seconds(b1,d1) - get_seconds(g1,0);
int ans2 = get_seconds(b2,d2) - get_seconds(g2,0);
int ans = (ans1 + ans2)/2;
int hh = ans/3600;
int mm = ans%3600/60;
int ss = ans % 60;
System.out.printf("%02d:%02d:%02d\n",hh,mm,ss);
}
}
private static int get_seconds(String[] t, int d1) {
int tol = 0;
int h = Integer.parseInt(t[0]);
int min = Integer.parseInt(t[1]);
int sed = Integer.parseInt(t[2]);
tol = d1*24*60*60 + h *60 * 60 + min*60 + sed;
return tol;
}
}
9.外卖店优先级(模拟)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int N = (int) (1e5 + 100);
static boolean[] ok = new boolean[N];
static int[] last = new int[N];
static int[] lev = new int[N];
static PII[] info = new PII[N];
static int n = 0,t = 0, m = 0;
static int a = 0, b = 0, c = 0;
public static void main(String[] args) throws Exception{
String []nmt = br.readLine().split(" ");
n = Integer.parseInt(nmt[0]);
m = Integer.parseInt(nmt[1]);
t = Integer.parseInt(nmt[2]);
for(int i = 1; i <= m;i++) {
String[] xy = br.readLine().split(" ");
int ts = Integer.parseInt(xy[0]);
int id = Integer.parseInt(xy[1]);
info[i] = new PII(ts,id);
}
Arrays.sort(info,1,m + 1, new cmp());
for(int i = 1; i <= m;i++) {
int ts = info[i].ts;
int ver = info[i].id;
if(ts > t) {
break;
}
if(ts == last[ver]) {
lev[ver] += 2;
last[ver] = ts;
}else {
lev[ver] += (ts - last[ver] - 1) * (-1);
if(lev[ver] < 0) {lev[ver] = 0;}
if (lev[ver] <= 3) {ok[ver] = false;}
lev[ver] += 2;
last[ver] = ts;
}
if(lev[ver] > 5) {
ok[ver] = true;
}
}
for(int i = 1; i <= n; i++) {
if(last[i] < t) {
lev[i] += (t - last[i])*(-1);
if (lev[i] < 0) {
lev[i] = 0;
}
if(lev[i] > 5) {
ok[i] = true;
}
if(lev[i] <= 3) {
ok[i] = false;
}
}
}
int ans = 0;
for(int i = 1; i <= n; i++) {
if(ok[i]) {
ans++;
}
}
System.out.println(ans);
}
}
class PII{
public PII(int ts, int id) {
this.ts = ts;
this.id = id;
}
int ts,id;
}
class cmp implements Comparator<PII>{
public int compare(PII o1, PII o2) {
return o1.ts - o2.ts;
}
}
10.逆序对的数量
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int N = (int) (1e5 + 10);
static int[]is1 = new int[N];
static int[]is2 = new int[N];
static int n = 0,ans = 0;
public static void main(String[] args) throws Exception{
n = Integer.parseInt(br.readLine());
String[] aa = br.readLine().split(" ");
for(int i = 1; i <= n; i++) {
is1[i] = Integer.parseInt(aa[i - 1]);
}
mergesort(1,n);
// for(int i = 1; i <= n; i++) {
// System.out.print(is1[i] + " ");
// }
System.out.println(ans);
}
private static void mergesort(int l, int r) {
if(l >= r)return;
int mid = (l + r) /2 ;
mergesort(l, mid);
mergesort(mid + 1, r);
merge(l,mid,r);
}
private static void merge(int l, int mid, int r) {
int i = l,j = mid + 1, k = l;
while(i <= mid && j <= r) {
if(is1[i] <= is1[j]) {
is2[k++] = is1[i++];
}else {
//is[]和is[]均为有序序列
//如果a[i] > a[j]那么[i,mid]的数全都大于j
is2[k++] = is1[j++];
//此处记录逆序对的对数
ans += (mid - i + 1);
}
}
while(i <= mid) {
is2[k++] = is1[i++];
}
while(j <= r) {
is2[k++] = is1[j++];
}
for(i = l; i <= r; i++) {
is1[i] = is2[i];
}
}
}