AcWing 2041. 干草堆
原题链接
简单
作者:
勿染
,
2022-01-26 16:45:21
,
所有人可见
,
阅读 149
import java.util.Arrays;
import java.util.Scanner;
public class Main {
//static final int N = 1000000;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int ns[] = new int[n + 1];//干草堆的差分数组
int k = scanner.nextInt();
for (int i = 0; i < k; i++) {
int a = scanner.nextInt();
int b = scanner.nextInt();
//差分数组
//对差分数组修改值
//递推改差分数组的值就是原来ns的值
ns[a]++;
if(b + 1 <= n)
ns[b + 1]--;
}
for (int i = 1; i <= n; i++) {
ns[i] = ns[i] + ns[i - 1];
}
Arrays.sort(ns, 1, n + 1);
System.out.println(ns[(n + 1) / 2]);
}
}