题意

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

限制：n不大于2000，每个数绝对值不大于1000

方法

遍历，统计

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

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

最后，我们通过$\mathrm{正}\mathrm{数}\mathrm{平}\mathrm{均}\mathrm{值}=\frac{\mathrm{正}\mathrm{数}\mathrm{总}\mathrm{和}}{\mathrm{正}\mathrm{数}\mathrm{个}\mathrm{数}}正数平均值\; =\; \backslash 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=\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 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)$