代码编织梦想

AcWing 1210. 连号区间数

小明这些天一直在思考这样一个奇怪而有趣的问题:

在 1∼N 的某个排列中有多少个连号区间呢?

这里所说的连号区间的定义是:

如果区间 [L,R] 里的所有元素(即此排列的第 L 个到第 R 个元素)递增排序后能得到一个长度为 R−L+1 的“连续”数列,则称这个区间连号区间。

当 N 很小的时候,小明可以很快地算出答案,但是当 N 变大的时候,问题就不是那么简单了,现在小明需要你的帮助。

输入格式
第一行是一个正整数 N,表示排列的规模。

第二行是 N 个不同的数字 Pi,表示这 N 个数字的某一排列。

输出格式
输出一个整数,表示不同连号区间的数目。

数据范围
1≤N≤10000,
1≤Pi≤N
输入样例1:
4
3 2 4 1
输出样例1:
7
输入样例2:
5
3 4 2 5 1
输出样例2:
9
样例解释
第一个用例中,有 7 个连号区间分别是:[1,1],[1,2],[1,3],[1,4],[2,2],[3,3],[4,4]
第二个用例中,有 9 个连号区间分别是:[1,1],[1,2],[1,3],[1,4],[1,5],[2,2],[3,3],[4,4],[5,5]

思路

当题目说是排列的时候,说明数字没有重复

代码

import java.io.*;

public class Main {
    static final int N = 10010, INF =  100000000;
    static int[] a = new int[N];
    static int n;
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    
    public static void main(String[] args) throws Exception {
        n = Integer.parseInt(in.readLine());
        String[] s = in.readLine().split(" ");
        for (int i = 0; i < n; i ++ ) a[i] = Integer.parseInt(s[i]);
        
        int res = 0;
        
        for (int i = 0; i < n; i ++ ) {
            int max = -INF;
            int min = INF;
            for (int j = i; j < n; j ++) {
                min = Math.min(a[j], min);
                max = Math.max(a[j], max);
                if(max - min == j - i) res ++;
            }
        }
        System.out.print(res);
    }
}

AcWing 1236. 递增三元组

给定三个整数数组

A=[A1,A2,…AN],
B=[B1,B2,…BN],
C=[C1,C2,…CN],

请你统计有多少个三元组 (i,j,k) 满足:

1≤i,j,k≤N
Ai<Bj<Ck
输入格式
第一行包含一个整数 N。

第二行包含 N 个整数 A1,A2,…AN。

第三行包含 N 个整数 B1,B2,…BN。

第四行包含 N 个整数 C1,C2,…CN。

输出格式
一个整数表示答案。

数据范围
1≤N≤105,
0≤Ai,Bi,Ci≤105
输入样例:
3
1 1 1
2 2 2
3 3 3
输出样例:
27

思路

通过分析时间复杂度可知,我们的算法时间复杂度要么是n 要么是nlogn,从题目来看,应该是nlogn,也就是最多可以遍历一个数组,那么我们遍历哪个数组呢?如果我们遍历A或者C的话,例如枚举A,BC都会受到限制,统计数量时不能直接相乘,遍历C同理,但是如果我们遍历B,A , C 就是独立的,可以直接相乘
A < B < C

方法1:前缀和:求A在[0, Bj]之间有多少个数,每存在一个就+ 1;
我们先开一个cnt[i]数组,表示在A中,i这个值出现多少次:for(i = 0; i < n; i ++ ) cnt[A[i]]++; 然后再把cnt转为前缀和S[],S[i]就表示,前i个数之和。
在这里插入图片描述
S[Bj - 1] 是比Bj 小的有多少个

方法2:sort:二分
方法3:双指针

代码

import java.io.*;
import java.util.*;

public class Main {
    static final int N = 100010;
    static int n;
    static int[] a = new int[N];
    static int[] b = new int[N];
    static int[] c = new int[N];
    static int[] as = new int[N];
    static int[] cs = new int[N];
    static int[] s = new int[N];
    static int[] cnt = new int[N];
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    
    static int Int(String s) {
        return Integer.parseInt(s);
    }
    
    public static void main(String[] arge) throws Exception {
        n = Int(in.readLine());
        String[] x = in.readLine().split(" ");
        String[] y = in.readLine().split(" ");
        String[] z = in.readLine().split(" ");
        for (int i = 0; i < n; i ++ ) {
            a[i] = Int(x[i]) + 1;
            b[i] = Int(y[i]) + 1;
            c[i] = Int(z[i]) + 1;
        }
        
        for (int i = 0; i < n; i ++ ) cnt[a[i]] ++ ;
        for (int i = 1; i < N; i ++ ) s[i] = s[i - 1] + cnt[i];   // 求cnt[]的前缀和
        for (int i = 0; i < n; i ++ ) as[i] = s[b[i] - 1];
    
        // 求cs[]
        Arrays.fill(cnt, 0);
        Arrays.fill(s, 0);
        for (int i = 0; i < n; i ++ ) cnt[c[i]] ++ ;
        for (int i = 1; i < N; i ++ ) s[i] = s[i - 1] + cnt[i];
        for (int i = 0; i < n; i ++ ) cs[i] = s[N - 1] - s[b[i]];

        // 枚举每个b[i]
        long res = 0;
        for (int i = 0; i < n; i ++ ) res += (long)as[i] * cs[i];
        System.out.print(res);
    }
    
}

AcWing 1245. 特别数的和

小明对数位中含有 2、0、1、9 的数字很感兴趣(不包括前导 0),在 1 到 40 中这样的数包括 1、2、9、10 至 32、39 和 40,共 28 个,他们的和是 574。

请问,在 1 到 n 中,所有这样的数的和是多少?

输入格式
共一行,包含一个整数 n。

输出格式
共一行,包含一个整数,表示满足条件的数的和。

数据范围
1≤n≤10000
输入样例:
40
输出样例:
574

思路

先计算时间复杂度:n <= 10000 最多可以循环一遍,然后遍历每一个数,并一一对比每一位,最大时间复杂度为O(5)(因为最大就是10000最多5位) 所以最终的时间复杂度是O(5n),可以直接暴力。

代码

import java.util.*;

public class Main {
    static final int N = 10010;
    static int n, son;
    static Scanner in = new Scanner(System.in);
    
    public static void main(String[] args) {
        n = in.nextInt();
        
        for (int i = 1; i <= n; i ++) {
            int x = i;
            while (x > 0) {
                int t = x % 10;
                x = x / 10;
                if (t == 2 || t == 0 || t == 1 || t == 9){
                   son += i;
                   break;
                }
            }
            
        }
        System.out.print(son);
    }
}

字符串版:

import java.util.*;

public class Main {
    static int n, son;
    static Scanner in = new Scanner(System.in);
    
    public static void main(String[] args) {
        n = in.nextInt();
        
        for (int i = 1; i <= n; i ++) {
            String x = String.valueOf(i);
            int j = x.length();
            while (j -- > 0) {
                System.out.print(j);
                char t = x.charAt(j);
                if (t == '2' || t == '0' || t == '1' || t == '9'){
                   son += i;
                   break;
                }
            }            
        }
        System.out.print(son);
    }       
}

AcWing 1204. 错误票据

某涉密单位下发了某种票据,并要在年终全部收回。

每张票据有唯一的ID号。

全年所有票据的ID号是连续的,但ID的开始数码是随机选定的。

因为工作人员疏忽,在录入ID号的时候发生了一处错误,造成了某个ID断号,另外一个ID重号。

你的任务是通过编程,找出断号的ID和重号的ID。

假设断号不可能发生在最大和最小号。

输入格式
第一行包含整数 N,表示后面共有 N 行数据。

接下来 N 行,每行包含空格分开的若干个(不大于100个)正整数(不大于100000),每个整数代表一个ID号。

输出格式
要求程序输出1行,含两个整数 m,n,用空格分隔。

其中,m表示断号ID,n表示重号ID。

数据范围
1≤N≤100
输入样例:
2
5 6 8 11 9
10 12 9
输出样例:
7 9

思路

这道题输入比较坑;
方法一:用一个数组来保存每个数是否出现过,然后再遍历一次,找出断号处和重号出。
方法二:排序法:
排完序后,重号的必然挨在一起,我们遍历的时候,从1 开始,前后两个数对比,断号的话就是两个数之差为2,中间差了一个数。

代码

import java.io.*;
import java.util.*;

public class Main {
    static final int N = 100010;
    static int n, res1, res2;
    static int[] a = new int[N];
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    
    public static void main(String[] args) throws Exception {
        n = Integer.parseInt(in.readLine().trim());
        int k = 0;
        while (n -- > 0) {
            String[] s = in.readLine().split("\\s+");//split里面必须要写这个,不然测试无法通过,用“ ” 会把空字符读入,虽然也能AC,但测试用例过不了,很迷
            for (int i = 0; i < s.length; i ++ ) a[k++] = Integer.parseInt(s[i]);
        }
        Arrays.sort(a, 0, k);
        for (int i = 1; i < k; i ++) {
            if (a[i] == a[i - 1]) res1 = a[i];
            else if (a[i] >= a[i - 1] + 2) res2 = a[i] - 1;
        }
        System.out.print(res2 + " " + res1);
    }   
}

AcWing 466. 回文日期

在日常生活中,通过年、月、日这三个要素可以表示出一个唯一确定的日期。

牛牛习惯用 8 位数字表示一个日期,其中,前 4 位代表年份,接下来 2 位代表月份,最后 2 位代表日期。

显然:一个日期只有一种表示方法,而两个不同的日期的表示方法不会相同。

牛牛认为,一个日期是回文的,当且仅当表示这个日期的 8 位数字是回文的。

现在,牛牛想知道:在他指定的两个日期之间(包含这两个日期本身),有多少个真实存在的日期是回文的。

一个 8 位数字是回文的,当且仅当对于所有的 i(1≤i≤8) 从左向右数的第 i 个数字和第 9−i 个数字(即从右向左数的第 i 个数字)是相同的。

例如:

对于 2016 年 11 月 19 日,用 8 位数字 20161119 表示,它不是回文的。
对于 2010 年 1 月 2 日,用 8 位数字 20100102 表示,它是回文的。
对于 2010 年 10 月 2 日,用 8 位数字 20101002 表示,它不是回文的。
输入格式
输入包括两行,每行包括一个 8 位数字。

第一行表示牛牛指定的起始日期 date1,第二行表示牛牛指定的终止日期 date2。保证 date1 和 date2 都是真实存在的日期,且年份部分一定为 4 位数字,且首位数字不为 0。

保证 date1 一定不晚于 date2。

输出格式
输出共一行,包含一个整数,表示在 date1 和 date2 之间,有多少个日期是回文的。

输入样例:
20110101
20111231
输出样例:
1

思路

1、时间复杂度
2、空间复杂度
3、代码复杂度 //找一个最好写的

代码

代码1:先排除所有不符合条件的项

import java.util.*;

public class Main {
    static int star, end, res;
    static Scanner in = new Scanner(System.in);
    static int[] d = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    
    public static void main(String[] args) {
        star = in.nextInt();
        end = in.nextInt();
        for (int i = star / 10000; i < 10000; i ++ ) {
            int y = i, x = i;
            for (int j = 0; j < 4; j ++ ) {
                y = y * 10 + x % 10;
                x /= 10;
            } 
            
            if (star <= y && y <= end) {
                int day = y % 100;
                int mouth = y / 100 % 100;
                if (mouth == 0 || mouth > 12) continue;
                if (day == 0 || mouth != 2 && day > d[mouth]) continue;/*注意这里的符号优先级  “&&” > "||"  这条语句的意思是,当天数等于0 或者 当月份不是2月时且天数大于当月最大天数则跳过本次循环*/
                if (mouth == 2) {
                    int temp = 0;
                    if (i % 100 != 0 && i % 4 == 0 || i % 400 == 0) temp = 1;
                    if (day > 28 + temp) continue;
                }
                res ++;
            }
        }
        System.out.print(res);
    }
}

代码2:找出所有符合条件的然后累加

import java.util.*;

public class Main {
    static int star, end, res;
    static Scanner in = new Scanner(System.in);
    static int[] d = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    
    public static void main(String[] args) {
        star = in.nextInt();
        end = in.nextInt();
        for (int i = star / 10000; i < 10000; i ++ ) {
            int y = i, x = i;
            for (int j = 0; j < 4; j ++ ) {
                y = y * 10 + x % 10;
                x /= 10;
            } 
            
            if (star <= y && y <= end) {
                int day = y % 100;
                int mouth = (y / 100) % 100;
                if (0< day && day < 32 && 0 < mouth && mouth < 13){
                    if (mouth == 2) {
                        if (i % 100 != 0 && i % 4 == 0 || i % 400 == 0)
                            if (day <= d[mouth] + 1) res ++;
                    }
                    else if (day <= d[mouth]) res ++;
                }
                
            }
        }
        System.out.print(res);
    }
}

两者对比,明显是先排除不符合项的方法看着简洁,但有点绕,第二种方法就是顺着逻辑走的,但代码不大好看

AcWing 787. 归并排序(模板)

给定你一个长度为 n 的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式
输入共两行,第一行包含整数 n。

第二行包含 n 个整数(所有整数均在 1∼109 范围内),表示整个数列。

输出格式
输出共一行,包含 n 个整数,表示排好序的数列。

数据范围
1≤n≤100000
输入样例:
5
3 1 2 4 5
输出样例:
1 2 3 4 5

思路

在这里插入图片描述

import java.io.*;

public class Main {
    static final int N = 100010;
    static int[] q = new int[N];
    static int[] w = new int[N];
    
    static void merge_sort(int l, int r) {
        if (l >= r) return;
        
        int mid = (l + r) / 2;
        
        merge_sort(l, mid);
        merge_sort(mid + 1, r);
        
        int i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r) {
            if (q[i] < q[j]) w[k ++] = q[i ++];
            else w[k ++] = q[j ++];
        }
        while (i <= mid) w[k ++] = q[i ++];
        while (j <= r) w[k ++] = q[j ++];
        
        for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = w[j];
    }
    
    static int Int(String s) {
        return Integer.parseInt(s);
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Int(in.readLine());
        String[] s = in.readLine().split(" ");
        for (int i = 0; i < n; i ++ ) q[i] = Int(s[i]);
        
        merge_sort(0, n - 1);
        
        for (int i = 0; i < n; i ++ ) out.write(q[i] + " ");
        out.flush();
    }
    
}

AcWing 1219. 移动距离

X星球居民小区的楼房全是一样的,并且按矩阵样式排列。

其楼房的编号为 1,2,3…
当排满一行时,从下一行相邻的楼往反方向排号。

比如:当小区排号宽度为 6 时,开始情形如下:

1 2 3 4 5 6
12 11 10 9 8 7
13 14 15 …
我们的问题是:已知了两个楼号 m 和 n,需要求出它们之间的最短移动距离(不能斜线方向移动)。

输入格式
输入共一行,包含三个整数 w,m,n,w 为排号宽度,m,n 为待计算的楼号。

输出格式
输出一个整数,表示 m,n 两楼间最短移动距离。

数据范围
1≤w,m,n≤10000,

输入样例:
6 8 2
输出样例:
4

思路

可以把它想象成一个二维数组,模拟java的数组让下标从0,0开始,所以我们的m,n都减1,然后我们列出二维数组找一下规律:
在这里插入图片描述
我们可以发现,行号很好求,直接下取整就好,
x1 = m / w;
x2 = n / w;
然后我们观察一下列号,我们可以发现,数值模与宽度就是列号,例如第0 列的数字全%6=0,与列号对应,这里有一个细节,如果我们的m,n没有减1,那么第六列%6 会等于0,也就是下标从一开始的话,第六列我们需要特判一下,第六列不应该为0;这里因为m–,n-- 了,所以不用处理。然后我们发现当行号为奇数时,需要翻转当前行,所以我们需要分2种情况,另外,如何求倒转的数列的下标呢?我们来观察一下:
在这里插入图片描述
列号倒转:(一下数字均为列号)
5 与 0 掉换
4 与 1 掉换
3 与 2 掉换
我们可以发现 他们的总和都是5,所以我们求翻转的列号,只要用w - 1 - (模出来的列号)就可以了
即:
y1 = w - 1 - m % w;
y2 = w - 1 - n % w;

代码

import java.util.*;

public class Main {
    static int w, m, n;
    static int x1, y1, x2, y2, res;
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        w = in.nextInt();
        m = in.nextInt();
        n = in.nextInt();
        m --;
        n --;
        x1 = m / w; x2 = n / w;
        if (x1 % 2 == 0) y1 = m % w;
        else y1 = w - 1 - m % w;
        if (x2 % 2 == 0) y2 = n % w;
        else y2 = w - 1 - n % w;
        res = Math.abs(x2 - x1) + Math.abs(y2 - y1);
        System.out.print(res);
    }
}

AcWing 1229. 日期问题

小明正在整理一批历史文献。这些历史文献中出现了很多日期。

小明知道这些日期都在1960年1月1日至2059年12月31日。

令小明头疼的是,这些日期采用的格式非常不统一,有采用年/月/日的,有采用月/日/年的,还有采用日/月/年的。

更加麻烦的是,年份也都省略了前两位,使得文献上的一个日期,存在很多可能的日期与其对应。

比如02/03/04,可能是2002年03月04日、2004年02月03日或2004年03月02日。

给出一个文献上的日期,你能帮助小明判断有哪些可能的日期对其对应吗?

输入格式
一个日期,格式是”AA/BB/CC”。

即每个’/’隔开的部分由两个 0-9 之间的数字(不一定相同)组成。

输出格式
输出若干个不相同的日期,每个日期一行,格式是”yyyy-MM-dd”。

多个日期按从早到晚排列。

数据范围
0≤A,B,C≤9
输入样例:
02/03/04
输出样例:
2002-03-04
2004-02-03
2004-03-02

思路

看题目可知,有三种日期表达形式:年月日、月日年、日月年
先枚举19600101到20591231之间的日期,然后分别取出年月日判断是否是给定的表达

代码

import java.io.*;

public class Main {
    
    static int[] day = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    
    static boolean cheek_value(int y, int m, int d) {
        int c = 0;
        if (m == 0 || m > 12) return false;
        if (m != 2 && d > day[m] || d == 0) return false;
        if (m == 2) {
            if (y % 100 != 0 && y % 4 == 0 || y % 400 == 0) c = 1;
            if (d > 28 + c) return false;
        }
        return true;
    }
    
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] s = in.readLine().split("/");
        int a = Integer.parseInt(s[0]);
        int b = Integer.parseInt(s[1]);
        int c = Integer.parseInt(s[2]);
        
        for (int i = 19600101; i <= 20591231; i ++) {
            int y = i / 10000;
            int m = i %10000 / 100;
            int d = i % 100;
            if (cheek_value(y, m, d)){
                if (y % 100 == a && m == b && d == c ||
                    d == a && m == b && y % 100 == c ||
                    m == a && d == b && y % 100 == c)
                    System.out.printf("%d-%02d-%02d\n", y, m, d);
            }
        }
    }
}

AcWing 1231. 航班时间

小 h 前往美国参加了蓝桥杯国际赛。

小 h 的女朋友发现小 h 上午十点出发,上午十二点到达美国,于是感叹到“现在飞机飞得真快,两小时就能到美国了”。

小 h 对超音速飞行感到十分恐惧。

仔细观察后发现飞机的起降时间都是当地时间。

由于北京和美国东部有 12 小时时差,故飞机总共需要 14 小时的飞行时间。

不久后小 h 的女朋友去中东交换。

小 h 并不知道中东与北京的时差。

但是小 h 得到了女朋友来回航班的起降时间。

小 h 想知道女朋友的航班飞行时间是多少。

对于一个可能跨时区的航班,给定来回程的起降时间。

假设飞机来回飞行时间相同,求飞机的飞行时间。

输入格式
一个输入包含多组数据。

输入第一行为一个正整数 T,表示输入数据组数。

每组数据包含两行,第一行为去程的起降时间,第二行为回程的起降时间。

起降时间的格式如下:

h1:m1:s1 h2:m2:s2
h1:m1:s1 h3:m3:s3 (+1)
h1:m1:s1 h4:m4:s4 (+2)
第一种格式表示该航班在当地时间h1时m1分s1秒起飞,在当地时间当日h2时m2分s2秒降落。

第二种格式表示该航班在当地时间h1时m1分s1秒起飞,在当地时间次日h2时m2分s2秒降落。

第三种格式表示该航班在当地时间h1时m1分s1秒起飞,在当地时间第三日h2时m2分s2秒降落。

输出格式
对于每一组数据输出一行一个时间hh:mm:ss,表示飞行时间为hh小时mm分ss秒。

注意,当时间为一位数时,要补齐前导零,如三小时四分五秒应写为03:04:05。

数据范围
保证输入时间合法(0≤h≤23,0≤m,s≤59),飞行时间不超过24小时。

输入样例:
3
17:48:19 21:57:24
11:05:18 15:14:23
17:21:07 00:31:46 (+1)
23:02:41 16:13:20 (+1)
10:19:19 20:41:24
22:19:04 16:41:09 (+1)
输出样例:
04:09:05
12:10:39
14:22:05

思路

这个类似以前碰到过的题目:从船上扔一个木块,然后船走了20min,然后再回来捡小木块,但不给水速、船速、水向、船向,问捡回来需要多少分钟?
在这里插入图片描述
其实可以换一个参考系,把水当做参考系,木块相对于水是静止的,而船相对于水的速度就是船本身的速度,所以,船花了多少时间里开小木块,就得花多少时间回来捡。这道题也类似这样。
在这里插入图片描述
在这里插入图片描述

因为时间不能直接相减,所以先把原时间转化成秒,
想办法拿出倒数第二个字符,也就是天数

代码

import java.io.*;

public class Main {
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    static int get_time() throws Exception {
        int day = 0;
        String[] s = in.readLine().split(" ");
        String[] s1 = s[0].split(":");
        String[] s2 = s[1].split(":");
        if (s.length == 3) day = Int(s[2].charAt(s[2].length() - 2) + "");
        int time_1 = Int(s1[0]) * 3600 + Int(s1[1]) * 60 + Int(s1[2]);
        int time_2 = Int(s2[0]) * 3600 + Int(s2[1]) * 60 + Int(s2[2]) + day * 3600 * 24;
        return time_2 - time_1;
    }
    
    static int Int(String s) {
        return Integer.parseInt(s);
    }
    public static void main(String[] args) throws Exception {
        int n = Int(in.readLine());
        while (n -- > 0) {
            int time = (get_time() + get_time()) / 2; 
            int y = time / 3600;
            int m = time % 3600 / 60;
            int d = time % 60;
            System.out.printf("%02d:%02d:%02d\n", y, m, d);
        }
    }
}

AcWing 1241. 外卖店优先级

“饱了么”外卖系统中维护着 N 家外卖店,编号 1∼N。

每家外卖店都有一个优先级,初始时 (0 时刻) 优先级都为 0。

每经过 1 个时间单位,如果外卖店没有订单,则优先级会减少 1,最低减到 0;而如果外卖店有订单,则优先级不减反加,每有一单优先级加 2。

如果某家外卖店某时刻优先级大于 5,则会被系统加入优先缓存中;如果优先级小于等于 3,则会被清除出优先缓存。

给定 T 时刻以内的 M 条订单信息,请你计算 T 时刻时有多少外卖店在优先缓存中。

输入格式
第一行包含 3 个整数 N,M,T。

以下 M 行每行包含两个整数 ts 和 id,表示 ts 时刻编号 id 的外卖店收到一个订单。

输出格式
输出一个整数代表答案。

数据范围
1≤N,M,T≤105,
1≤ts≤T,
1≤id≤N
输入样例:
2 6 6
1 1
5 2
3 1
6 2
2 1
6 2
输出样例:
1
样例解释
6 时刻时,1 号店优先级降到 3,被移除出优先缓存;2 号店优先级升到 6,加入优先缓存。

所以是有 1 家店 (2 号) 在优先缓存中。

思路

暴力思路:
在这里插入图片描述
有题目可知,暴力的时间复杂度在(105)2
在暴力的基础上优化一下
模拟题写伪代码非常重要。
在这里插入图片描述

代码

import java.io.*;
import java.util.*;

public class Main {
    static final int N = 100010;
    static int[] score = new int[N];
    static int[] last = new int[N];
    static boolean[] st = new boolean[N];
    static PIIs[] PII = new PIIs[N];
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    
    static int Int(String s) {
        return Integer.parseInt(s);
    }
    
    public static void main(String[] args) throws IOException {
        String[] s = in.readLine().split(" ");
        int n = Int(s[0]);
        int m = Int(s[1]);
        int T = Int(s[2]);
        for (int i = 1; i <= m; i ++ ) {
            String[] s1 = in.readLine().split(" ");
            int ts = Int(s1[0]);
            int id = Int(s1[1]);
            PII[i] = new PIIs(ts, id);
        }
        Arrays.sort(PII, 1, m + 1);
        
        for (int i = 1; i <= m; ) {
            int j = i;
            while (j <= m && PII[i].ts == PII[j].ts && PII[i].id == PII[j].id) j ++;
            int t = PII[i].ts, id = PII[i].id, cnt = j - i;
            i = j;
            
            score[id] -= t - last[id] - 1;
            if (score[id] < 0) score[id] = 0;
            if (score[id] <= 3) st[id] = false;
            
            score[id] += cnt * 2;
            if (score[id] > 5) st[id] = true;
            //更新
            last[id] = t; //这里的t实际上是PII[j].ts只不过与PII[i].ts相等,所以这里取t没问题
        }
        
        for (int i = 1; i <= n; i++ ) {
            if (last[i] < T) {
                score[i] -= T - last[i];
                if (score[i] <= 3) st[i] = false;
            }
        }
        int res = 0;
        for (int i = 1; i <= n; i ++ ) {
            if (st[i]) res ++;
        }
        System.out.println(res);
    }
}

class PIIs implements Comparable<PIIs> {
    public int ts;
    public int id;
        
    public PIIs(int ts, int id) {
        this.ts = ts;
        this.id = id;
    }
        
    public int compareTo(PIIs o) {
        return this.ts != o.ts ? Integer.compare(this.ts, o.ts) : Integer.compare(this.id, o.id);
    }
}

AcWing 788. 逆序对的数量

给定一个长度为 n 的整数数列,请你计算数列中的逆序对的数量。

逆序对的定义如下:对于数列的第 i 个和第 j 个元素,如果满足 i<j 且 a[i]>a[j],则其为一个逆序对;否则不是。

输入格式
第一行包含整数 n,表示数列的长度。

第二行包含 n 个整数,表示整个数列。

输出格式
输出一个整数,表示逆序对的个数。

数据范围
1≤n≤100000
输入样例:
6
2 3 4 5 6 1
输出样例:
5

思路

利用归并排序的比较步骤,顺便计算出逆序对

代码

import java.io.*;

public class Main {
    static final int N = 100010;
    static long res; //因为会爆int,所以改用long
    static int[] temp = new int[N];
    
    static void merge_sort (int[] a, int l, int r) {
        if (l >= r) return;
        int mid = l + r >> 1;
        merge_sort(a, l, mid);
        merge_sort(a, mid + 1, r);
        int i = l, j = mid + 1, k = 0;
        
        while (i <= mid && j <= r) {
            if (a[i] <= a[j]) temp[k ++] = a[i ++];
            else {
                res += mid - i + 1;//利用每一次的比较,计算逆序对数量,由于已经排好序,只要右边数比i小,那么i之后的数都比右边大
                temp[k ++] = a[j ++];
            }
        }
        
        while (i <= mid) temp[k ++] = a[i ++];
        while (j <= r) temp[k ++] = a[j ++];
        
        for (i = l, j = 0; i <= r; i ++, j++ ) a[i] = temp[j];
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        String[] s = in.readLine().split(" ");
        int[] a = new int[n];
        for (int i = 0; i < n; i ++ ) a[i] = Integer.parseInt(s[i]);
        merge_sort(a, 0, n - 1);
        System.out.print(res);
    }
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/bbjlcc/article/details/115028554

noip2000税收与补贴问题 (模拟,排序)-爱代码爱编程

A1129. 税收与补贴问题 时间限制: 1.0s   内存限制: 256.0MB   总提交次数: 216   AC次数: 60   平均分: 52.66 将本题分享到:             查看未格式化的试题 

hdu 4500 小q系列故事——屌丝的逆袭(模拟枚举排序)-爱代码爱编程

小Q系列故事——屌丝的逆袭 Time Limit: 300/100 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 6144 Accepted Submission(s): 2298 Problem Description

c++程序设计基础(第五版)(上) 习题与解答-爱代码爱编程

习题与解答 C++程序设计基础(第5版)(上) 习题与解答 第1章练习题 同步练习1.1 一、选择题 1.一个最简单的C++程序,可以只有一个( )。 (A)库函数 (B)自定义函数 (C)main函数 (D)空函数 2.函

Java面试题大全(2020版)-爱代码爱编程

发现网上很多Java面试题都没有答案,所以花了很长时间搜集整理出来了这套Java面试题大全,希望对大家有帮助哈~ 本套Java面试题大全,全的不能再全,哈哈~ 博主已将以下这些面试题整理成了一个Java面试手册,是PDF版的。 关注博主的微信公众号:Java团长,然后回复“面试手册”即可获取~ 一、Java 基础 1. JDK 和 JRE 有什么

模拟(枚举)-第四届蓝桥杯省赛C++B组-连号区间数-爱代码爱编程

模拟(枚举)-第四届蓝桥杯省赛C++B组-连号区间数 题目: 小明这些天一直在思考这样一个奇怪而有趣的问题: 在 1∼N 的某个排列中有多少个连号区间呢? 这里所说的连号区间的定义是: 如果区间 [L,R] 里的所有元素(即此排列的第 L 个到第 R 个元素)递增排序后能得到一个长度为 R−L+1 的“连续”数列,则称这个区间连号区间。 当 N

枚举、模拟与排序-爱代码爱编程

文章目录 连号区间数递增三元组特别数的和错误票据回文日期归并排序移动距离日期问题航班时间外卖店优先级逆序对的数量 连号区间数 题目大意 小明这些天一直在思考这样一个奇怪而有趣的问题:在 1∼N的某个排列中有多少个连号区间呢?这里所说的连号区间的定义是:如果区间 [L,R]里的所有元素(即此排列的第 L 个到第 R 个元素)递增排序后能得到一个

哈尔滨学院夏令营day2-2:排序下+枚举-爱代码爱编程

7.堆排序: 堆排序思想—>完全二叉树 1)满二叉树 2)若不是满二叉树,最下面一层从左至右一次补齐。堆积性质:子结点的键值或索引总是小于(或大于)它的父节点。堆排序物理结构:数组逻辑结构:完全二叉树 已知数组元素下标为i,那么这个元素对应的左孩子下标为2i+1,右孩子下标为2i+2,父节点为(i-1)/2。 数组模拟举栗子:大根堆、小根堆 大根堆

关于排列与组合的枚举-爱代码爱编程

关于排列与组合的枚举 最近刷题的时候碰到了这两种题型,主要就是计算排列数和组合数,自己做了之后看了一些解题发现帮助挺大的,做一个小笔记~ 1.组合的枚举 洛谷P1157 组合的输出 组合就是从 n 个元素中抽出 r 个元素(不分顺序且 r ≤ n ),我们可以简单地将n个元素理解为自然数1, 2, …, n,从中任取 r 个数。 举个栗

2021算法竞赛入门班第一节课枚举贪心习题-爱代码爱编程

枚举贪心 题单链接 枚举常用算法:前缀和,差分数组,双指针(尺取法)。 文章目录 枚举贪心各题题解1. Flip Game2. Subsequence3.Quasi Binary4.Protecting the Flowers5.校门外的树6.明明的随机数7.[HNOI2003]激光炸弹8.铺地毯9.纪念品分组10.回文日期11.拼数12.毒瘤xo

连号区间数(模拟枚举)-爱代码爱编程

连号区间数 题目链接 小明这些天一直在思考这样一个奇怪而有趣的问题: 在 1∼N 的某个排列中有多少个连号区间呢? 这里所说的连号区间的定义是: 如果区间 [L,R] 里的所有元素(即此排列的第 L 个到第 R 个元素)递增排序后能得到一个长度为 R−L+1 的“连续”数列,则称这个区间连号区间。 当 N 很小的时候,小明可以很快地算出答案,但是当 N

枚举&模拟-爱代码爱编程

枚举&模拟 模拟 1210. 连号区间数 二重循环枚举所有子区间,然后sort,然后判断是否符合条件(满足max-min=b-a),这个判断条件是要想清楚的 #include<iostream> #include<algorithm> using namespace std; const int N =

专题(四) 枚举模拟排序 ——AcWing 466. 回文日期-爱代码爱编程

【题目描述】 AcWing 466. 回文日期 【思路】 回文日期 枚举 闰年 1 3 5 7 8 10 12 31天永不差 2 28/29 4 6 9 11 30天 智障 第一想法居然是去枚举所有合法日期然后判断是否是回文数 8位数的日期 只需枚举前四位年份 然后构造回文 判断该回文是否是真实存在 这样只需枚举 1000~9999 总共9k个数 i

暴力枚举-爱代码爱编程

  目录 0、枚举 简介  1、洛谷 P2241 统计方形(数据加强版) 2、洛谷 P3392 涂国旗 3、 Java 大学B 组试题D: 数的分解 0、枚举 简介 枚举是基于已有知识来猜测答案的一种问题求解策略。枚举的思想是不断地猜测,从可能的集合中一一尝试,然后再判断题目的条件是否成立。 要点 给出解空间 建立简洁的数学模

Java中输入输出-爱代码爱编程

Java中输入输出 目前Java支持文件I/O和流式I/O,数据流可分为二进制流和文本流,也称为字节流和字符流它们处理信息的基本单位分别为字节和字符java.io.File类用来表示物理磁盘上的实际文件或者目录,但是它不表示文件中的数据import java.io.File; import java.io.IOException; public clas