题意

给n个数，求负数的个数，非负数的平均数。

限制：$nn$不大于$5000050000$，每个数绝对值不大于$10^{6}10^6$

方法

遍历，统计

对于遍历，我们通过记录负数个数，非负数个数，和非负数总和。最后得到要求的值

以样例数据-12 1 2为例

最后，我们通过$\mathrm{非}\mathrm{负}\mathrm{数}\mathrm{平}\mathrm{均}\mathrm{值}=\frac{\mathrm{非}\mathrm{负}\mathrm{数}\mathrm{总}\mathrm{和}}{\mathrm{非}\mathrm{负}\mathrm{数}\mathrm{个}\mathrm{数}}非负数平均值\; =\; \backslash frac\{非负数总和\}\{非负数个数\}$ 得到要求的值

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int neg = 0; // 负数个数
    int nneg = 0; // 非负数个数
    int cnt = 0; // 非负数总和
    int v;
    while(~scanf("%d",&v)){
        if(v<0)neg++; // 是负数
        else{ // 是非负数
            nneg++; // 计数+1
            cnt+=v; // 更新和
        }
    }
    printf("%d\n%.1f\n",neg,nneg==0?0:(double)cnt/nneg); // 平均值
    return 0;
}

复杂度分析

时间复杂度: 我们对于每个输入，处理代价为常数，所以总时间复杂度为$O(n)O(n)$

空间复杂度: 我们只用了常数大小的额外空间，所以空间复杂度为$O(1)O(1)$

维护平均值取代维护总和

当我们增加了一个非负数。注意到平均值变化为

$avg=\frac{av{g}_{old}\cdot count+value}{count+1}avg=\backslash frac\{avg\_\{old\}\; \backslash cdot\; count\; +\; value\}\{count+1\}$

所以我们可以去维护平均值

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int neg = 0;
    int nneg = 0;
    double avg = 0; // 记录平均值 取代记录总和
    int v;
    while(~scanf("%d",&v)){
        if(v<0)neg++;
        else{
            avg = (avg*nneg+v)/(nneg+1); // 更新平均值
            nneg++;
        }
    }
    printf("%d\n%.1f\n",neg,avg);
    return 0;
}

复杂度分析

时间复杂度: 我们对于每个输入，处理代价为常数，所以总时间复杂度为$O(n)O(n)$

空间复杂度: 我们只用了常数大小的额外空间，所以空间复杂度为$O(1)O(1)$