返回题解分享
讨论 / 题解分享/ 帖子详情

成绩统计(编程题) - 题解

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+10;
ll n,k,T;
ll a[N],b[N],aa[N],s1[N],s2[N];
bool check(ll n){
    for(int i=1;i<=n;i++)b[i]=a[i];
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++){
        s1[i]=s1[i-1]+b[i];
        s2[i]=s2[i-1]+b[i]*b[i];
    }
    for(int i=1,e=k;e<=n;e++,i++){
        if(k*(s2[e]-s2[i-1])-(s1[e]-s1[i-1])*(s1[e]-s1[i-1])<k*k*T){
            return true;
        }
    }
    return false;

}
int main(){
    cin>>n>>k>>T;
    for(int i=1;i<=n;i++)cin>>a[i];
    ll l=k,r=n,mid;
    while(l<r){
        mid=(l+r)>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    if(r==n&&!check(n))cout<<-1;
    else cout<<l;
    return 0;
}
4 回复 0 转发 0 喜欢 12 阅读
回复 (4)
默认 最新
露米 1 天前
看到你对这个题解的持续完善了,逻辑依然非常清晰稳健。

利用二分搜索结合前缀和来处理方差问题,确实是一个很扎实的思路。特别是你通过公式变形巧妙地避开了浮点数精度误差,这种处理方式对很多正在学习的小伙伴来说都很有参考价值。

我注意到代码目前在 check 函数内部进行了排序。如果想让程序在面对更大数据量时运行得更加游刃有余,或许可以尝试先对整个数组进行一次全局排序,然后在二分过程中直接利用有序性来滑动窗口计算。你可以思考看看,在数组有序的前提下,连续的 $k$ 个元素是否依然能满足寻找最小方差的性质呢?

这种不断打磨、寻找更优解的过程,正是编程最迷人的地方。如果在尝试过程中有任何新的想法,或者调整时遇到了小卡顿,都可以随时分享出来,我们一起讨论 🙂

加油,看到你一步步把代码写得更稳健,真的很为你开心。期待你的下一次分享。
0
露米 2026/4/1
看到你分享的题解了,逻辑非常清晰,代码风格也很整洁。

利用二分搜索配合前缀和来处理方差相关的计算,是一个非常扎实且巧妙的思路。特别是你通过公式变形避开了浮点数精度的问题,这一点对于处理这类编程题来说非常关键,看得出你在细节上花了不少心思。

我注意到在 check 函数里,代码目前会对当前范围内的成绩进行排序。如果想让程序运行得更轻快一点,你觉得有没有可能在二分搜索之前,先对整个数组进行一次全局排序呢?你可以试着思考一下,在数组有序的前提下,连续的 $k$ 个元素是否依然能满足寻找最小方差的性质。

这种不断打磨和优化代码的过程,其实就是进步最快的时候。如果尝试过程中遇到了新的疑问,欢迎随时分享出来,我们一起讨论 🙂

另外,看到你对边界情况(比如最后输出 -1)的处理也非常周全,这种细心在解决复杂问题时真的很宝贵。

慢慢积累,你的思路会越来越稳健的。加油,期待看到你的下一次分享。
0
露米 2026/2/24
看到你分享的代码了,逻辑写得非常清晰。

利用二分搜索配合前缀和来处理方差问题,是一个非常扎实且巧妙的思路。特别是你通过公式变形避开了浮点数精度的问题,这种对细节的把控对很多同学来说都很有启发。

我注意到在 check 函数里,代码目前会对当前范围内的成绩进行排序。如果想进一步优化运行效率,你觉得有没有可能在二分搜索之前就完成排序工作呢?你可以尝试思考一下,如果整个数组是有序的,连续的 $k$ 个元素是否依然能满足寻找最小方差的性质。

如果有新的想法,欢迎随时分享出来。慢慢积累,你的思路会越来越稳健的。加油 🙂
另外,看到你对边界情况(比如最后输出 -1)的处理也非常周全,这种细心在解决编程问题时真的很关键。

如果之后想尝试更具挑战性的优化,也可以关注一下在计算过程中如何更稳妥地处理可能的大数溢出,这样你的代码会更加无懈可击。

如果大家对这个题目有不同的解法,也欢迎在回帖里一起交流。在这里,每一个思考的过程都是被珍惜的。期待你的下一次分享 🙂
0
露米 2026/2/7
看到你分享的题解了,逻辑很清晰。

利用二分搜索配合前缀和来处理方差相关的计算,是一个非常稳妥且巧妙的思路。特别是你通过公式变形避开了浮点数精度的问题,这一点对很多刚接触这类题目的同学来说很有参考价值。

我注意到在 check 函数里,代码会对当前范围内的成绩进行排序。如果想让程序运行得更快一点,你觉得有没有可能通过改变排序的时机,或者利用一些预处理来实现呢?

期待你的更多分享 🙂
另外,看到你对边界情况(比如最后输出 -1)的处理也非常周全,这种细心在解决编程问题时真的很关键。

慢慢积累,你的思路会越来越稳健的。加油,期待看到你的下一次进步。
0