归并排序
import java.util.*;
import java.io.*;
public class Main {
static final int N = 100005;
static int n, m, k;
static int[] a = new int[N];
static int[] t = new int[N];
public static void main(String[] args) throws Exception {
//Scanner sc = new Scanner(System.in);
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] s = bf.readLine().split(" ");
n = Integer.parseInt(s[0]);
s = bf.readLine().split(" ");
for(int i = 1; i <= n; i ++)
{
a[i] = Integer.parseInt(s[i - 1]);
}
merge_sort(1, n);
for(int i = 1; i <= n; i ++)
{
bw.write(a[i] + " ");
}
bw.flush();
}
public static void merge_sort(int l, int r)
{
if(l >= r) return;
int mid = (l + r) >> 1;
merge_sort(l, mid);
merge_sort(mid + 1, r);
int i = l, j = mid + 1, k = 0;
while(i <= mid && j <= r)
{
if(a[i] < a[j])
{
t[k ++] = a[i ++];
}
else t[k ++] = a[j ++];
}
while(i <= mid) t[k ++] = a[i ++];
while(j <= r) t[k ++] = a[j ++];
for(int o = l, p = 0; o <= r; o ++, p ++) a[o] = t[p];
}
}
前缀和
一维
import java.util.*;
import java.io.*;
public class Main {
static final int N = 100005;
static int[] a = new int[N];
static int[] s = new int[N];
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
for(int i = 1; i <= n; i ++)
{
a[i] = sc.nextInt();
s[i] = s[i - 1] + a[i];
}
while(m -- > 0)
{
int l = sc.nextInt(), r = sc.nextInt();
System.out.println(s[r] - s[l - 1]);
}
}
}
二维
import java.util.*;
import java.io.*;
public class Main {
static final int N = 1005;
static int[][] a = new int[N][N];
static int[][] s = new int[N][N];
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt(), q = sc.nextInt();
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
{
a[i][j] = sc.nextInt();
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
}
while(q -- > 0)
{
int x1 = sc.nextInt(), y1 = sc.nextInt(), x2 = sc.nextInt(), y2 = sc.nextInt();
System.out.printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
}
}
}
差分
一维
import java.util.*;
import java.io.*;
public class Main {
static final int N = 100100;
static int[] d = new int[N];
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int q = sc.nextInt();
for(int i = 1; i <= n; i ++)
{
int x;
x = sc.nextInt();
cf(i, i, x);
}
while(q -- > 0)
{
int l = sc.nextInt(), r = sc.nextInt(), c = sc.nextInt();
cf(l, r, c);
}
for(int i = 1; i <= n; i ++) d[i] += d[i - 1];
for(int i = 1; i <= n; i ++)
{
System.out.printf("%d ", d[i]);
}
}
public static void cf(int l, int r, int w)
{
d[l] += w;
d[r + 1] -= w;
}
}
二维
import java.util.*;
import java.io.*;
public class Main {
static final int N = 1010;
static int[][] d = new int[N][N];
public static void main(String[] args) throws Exception {
//Scanner sc = new Scanner(System.in);
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] ss = bf.readLine().split(" ");
int n = Integer.parseInt(ss[0]);
int m = Integer.parseInt(ss[1]);
int q = Integer.parseInt(ss[2]);
for(int i = 1; i <= n; i ++)
{
String[] s = bf.readLine().split(" ");
for(int j = 1; j <= m; j ++)
{
int x = Integer.parseInt(s[j - 1]);
cf(i, j, i, j, x);
}
}
while(q -- > 0)
{
ss = bf.readLine().split(" ");
int x1 = Integer.parseInt(ss[0]), y1 = Integer.parseInt(ss[1]), x2 = Integer.parseInt(ss[2]), y2 = Integer.parseInt(ss[3]);
int w = Integer.parseInt(ss[4]);
cf(x1, y1, x2, y2, w);
}
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
d[i][j] = d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1] + d[i][j];
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j ++)
bw.write(d[i][j] + " ");
bw.write("\n");
}
bw.flush();
}
public static void cf(int x1, int y1, int x2, int y2, int w)
{
d[x1][y1] += w;
d[x2 + 1][y1] -= w;
d[x1][y2 + 1] -= w;
d[x2 + 1][y2 + 1] += w;
}
}
区间合并
import java.util.*;
import java.io.*;
public class Main {
static final int N = 100010, MOD = 1000000007;
static class PII implements Comparable<PII> //相当于定义了一个C++里面的pair二元组
{
int x, y;
public PII(int x, int y)
{
this.x = x;
this.y = y;
}
public int compareTo(PII v)
{
return x - v.x;
}
}
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
//BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
//BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = sc.nextInt();
List<PII> list = new ArrayList<>();
for(int i = 1; i <= n; i ++)
{
int l = sc.nextInt();
int r = sc.nextInt();
list.add(new PII(l, r));
}
Collections.sort(list); //用collections来进行排序
int res = 0;
int st = (int)-2e9; //定义为负无穷的方法
int ed = (int)-2e9;
for(int i = 0; i < list.size(); i ++)
{
PII t = list.get(i);
if(st == (int)-2e9 || ed < t.x)
{
st = t.x;
ed = t.y;
res ++;
}
else ed = Math.max(ed, t.y);
}
System.out.println(res);
}
}
