二分+前缀和/滑动窗口——成绩统计
成绩统计(二分+前缀和/滑动窗口)24年省赛
题目分析:
定位关键词——“至少要检查多少个人的成绩,才有可能选出 k 名同学,他们的方差小于一个给定的值 T”,也就是满足条件的最小值,可以考虑用二分。但是他需要可以二分,也就是单调性或者二段性。每次选择都是选择前x个数,然后在这前x个数里面找到一组个数为k的数,他们的方差满足条件,如果x可以找到,那么x继续增大也可以找到,因为增大后的x是包含了增大前的x的。举个例子,假设x=5。在a[1],a[2],a[3],a[4],a[5]中,我们可以找到a[2],a[3],a[5]满足方差小于T,那么当x=8时,对于a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]也一定存在a[2],a[3],a[5]满足方差小于T,因此具有单调性,也就是小的值满足条件,大的值也一定满足条件。
接下来考虑二分过程。
第一阶段二段性分析
当我检查了前mid个同学的成绩之后,如果可以找到一组数,个数为k,且方差小于T,那么我会尝试找更小的值是不是也满足条件,所以向左边走,即
if (check(mid)) {r = mid;} //因为mid是符合条件的,所以我要留着它,而不是l=mid+1
当我检查了前mid个同学的成绩之后,如果不可以找到一组数,个数为k,且方差小于T,那么我只能找更大的值,所以向右边走,即
else { l = mid + 1; }//因为mid是不符合条件的,所以我不要留着它,而不是r=mid
综上该题满足二段性,可以用二分,二分的板子就不说了,接下来说一下check函数如何写。
第二阶段写check函数
check(mid)要实现的作用是当我知道了前mid个学生的成绩后,能否快速找出k名同学,使得他们的方差小于T。如果不能则返回false,否则返回true。我们希望选出来的k名同学的方差尽可能小,方差衡量的是数据之间的差值,自然要选择数据相近的k个值,所以我们可以对原始数据进行排序,然后选择连续的k个值就可以了。但是怎么快速计算选出来的k个值的方差呢?这就要根据方差公式了。
对于 ∑ i = 1 k v i 2 \sum_{i=1}^k{v_i^2} ∑i=1kvi2、 ∑ i = 1 k v i \sum_{i=1}^k{v_i} ∑i=1kvi,我们可以通过前缀和、前缀平方和或者滑动窗口的形式快速得到。而对于剩余的可以直接计算得出。所以代码如下,
static boolean check(int mid) {
for (int i = 1; i <= mid; i++)
b[i] = a[i];
Arrays.sort(b, 1, mid + 1);//排序
long v2 = 0, v = 0;
for (int i = 1; i < k; i++) {//预处理数组b的前k-1项相关数据
v2 += 1L * b[i] * b[i];//求平方和
v += b[i];//求和
}
for (int i = k; i <= mid; i++) {
v2 += 1L * b[i] * b[i] - 1L * b[i - k] * b[i - k];//类似滑动窗口,加上当前值,去掉已经滑出去的值
v += b[i] - b[i - k];//类似滑动窗口,加上当前值,去掉已经滑出去的值
double avg = 1.0 * v / k;//得到平均值
if ((v2 - 2 * avg * v + k * avg * avg) / k < T)
return true;
}
return false;
}
刚刚的代码采用的是滑动窗口的思路,下面的代码使用的是前缀和的思路,
static boolean check(int mid) {
for (int i = 1; i <= mid; i++)
b[i] = a[i];
Arrays.sort(b, 1, mid + 1);
long[] sum_v2 = new long[mid+1], sum_v = new long[mid+1];
for (int i = 1; i <= mid; i++) {
sum_v2[i] = sum_v2[i-1] + 1L * b[i] * b[i];
sum_v[i] =sum_v[i-1] + b[i];
}
for (int i = k; i <= mid; i++) {
// v2 += 1L * b[i] * b[i] - 1L * b[i - k] * b[i - k];
// v += b[i] - b[i - k];
long v2 = sum_v2[i] - sum_v2[i-k];
long v = sum_v[i] - sum_v[i-k];
double avg = 1.0 * v / k;
if ((v2 - 2 * avg * v + k * avg * avg) / k < T)
return true;
}
return false;
}
第三步二分范围确定
那么这里的高度的最小值是1,最大值就是数组中元素的个数,也就是n。注意本题没有说一定能找到符合条件的高度,所以最后输出的时候要判断一下。
题目代码
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int n, k, T;
static int[] a, b;
static boolean check(int mid) {
for (int i = 1; i <= mid; i++)
b[i] = a[i];
Arrays.sort(b, 1, mid + 1);
long[] sum_v2 = new long[mid+1], sum_v = new long[mid+1];
for (int i = 1; i <= mid; i++) {
sum_v2[i] = sum_v2[i-1] + 1L * b[i] * b[i];
sum_v[i] =sum_v[i-1] + b[i];
}
for (int i = k; i <= mid; i++) {
// v2 += 1L * b[i] * b[i] - 1L * b[i - k] * b[i - k];
// v += b[i] - b[i - k];
long v2 = sum_v2[i] - sum_v2[i-k];
long v = sum_v[i] - sum_v[i-k];
double avg = 1.0 * v / k;
if ((v2 - 2 * avg * v + k * avg * avg) / k < T)
return true;
}
return false;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
k = scanner.nextInt();
T = scanner.nextInt();
a = new int[n + 1];
b = new int[n + 1];
for (int i = 1; i <= n; i++)
a[i] = scanner.nextInt();
int l = k, r = n;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
if(check(l))System.out.println(l);
else System.out.println(-1);
}
}