P9956 [USACO20DEC] Daisy Chains B

nightwatch.ryan · 2023-12-18 21:45:23 · 题解

思路

本题需要求 (i,j) 区间的花瓣数量的平均值，1\le i\le j\le N。用前缀和来存储第 1 朵花到第 i 朵花的所有花瓣之和。然后枚举所有可能的区间，遍历区间所有的花。注意，判断一朵花是不是平均的，我们要用乘法，因为除法会出现小数。

代码

#include<iostream>
int p[105],sum[200],res,n;
int main(){
    std::cin>>n;
    sum[0]=0;
    for(int i=1;i<=n;i++){
        std::cin>>p[i];
        sum[i]=sum[i-1]+p[i];//这里利用了前缀和的思想 
    }
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            int summ=sum[j]-sum[i-1];//求i,j这一个区间的花瓣总数 
            int flowerSum=j-i+1;//求这一个区间的花的总数 
            for(int k=i;k<=j;k++){//枚举i,j这个区间的每一朵花 
                if(summ==flowerSum*p[k]){//这里为了避免除出来有小数，使用花朵总数*当前花的花瓣数和这一个区间的花瓣总数进行比较 
                    res++;
                    break;//注意，这个区间只要有一朵花就要结束，重新枚举下一个区间 
                }
            }
        }
    }
    std::cout<<res;
}
//by nightwatch_ryan