题意

给n个数,求负数的个数,正数的平均数。

限制:n不大于2000,每个数绝对值不大于1000

方法

遍历,统计

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

以样例1 2 3 4 5 6 7 8 9 0为例

负数个数 正数个数 正数总和
初始化 0 0 0
1 0 1 1
2 0 2 3
3 0 3 6
4 0 4 10
5 0 5 15
6 0 6 21
7 0 7 28
8 0 8 36
9 0 9 45
0 0 9 45

最后,我们通过=正数平均值 = \frac{正数总和}{正数个数} 得到要求的值

代码

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

复杂度分析

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

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

维护平均值取代维护总和

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

avg=avgoldcount+valuecount+1avg=\frac{avg_{old} \cdot count + value}{count+1}

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

注意:数据量过大的情况,可能有精度丢失的问题,建议能用整数做中间过程的,还是不要用浮点数

代码

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

复杂度分析

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

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