题目描述

把牛的体重看作一条数轴，斑点看作标记，给出n头牛的坐标，以及坐标的标记(有斑点记作true)。根据和n头牛的距离，考虑[A,B]中每个点的标记是什么。

算法

(按照题意枚举每个区间) $O(n)$

C++ 代码

#include <bits/stdc++.h>
using namespace std;

// 定义牛的结构体，包含体重和是否有斑点的标志
struct Cow {
    long long w;   // 体重
    bool d;        // true 表示有斑点 (S)，false 表示无斑点 (NS)
};

// 比较函数，用于根据体重对牛进行排序
bool cmp(const Cow &a, const Cow &b) {
    return a.w < b.w;
}

int main(){
    // 提高输入输出效率
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    long long N, A, B;
    cin >> N >> A >> B; // 读取牛的数量 N，以及新牛体重范围 [A, B]

    // 创建一个数组来存储牛的信息
    Cow cows[N];

    // 读取每头牛的状态和体重
    for(long long i = 0; i < N; i++){
        string s;
        long long w;
        cin >> s >> w; // 读取状态和体重
        cows[i].w = w;
        if(s == "S") {
            cows[i].d = true; // 有斑点
        }
        else{
            cows[i].d = false; // 无斑点
        }
    }

    // 根据体重对牛进行排序
    sort(cows, cows + N, cmp);

    long long total_S = 0; // 记录被分类为有斑点的新牛数量

    // 处理体重小于最轻牛的情况 [A, W1 -1]
    if(A <= cows[0].w - 1 && A <= B){
        long long low = A;
        long long high = min(B, cows[0].w - 1);
        if(low <= high && cows[0].d){
            total_S += (high - low + 1);
        }
    }

    // 处理体重等于现有牛体重的情况 x = W_i
    for(long long i = 0; i < N; i++){
        if(cows[i].w >= A && cows[i].w <= B && cows[i].d){
            total_S += 1;
        }
    }

    // 处理现有牛之间的区间
    for(long long i = 0; i < N -1; i++){
        long long W_i = cows[i].w;
        long long W_j = cows[i+1].w;
        long long sum_w = W_i + W_j;
        long long mid = sum_w / 2;

        // 检查 L + R 的奇偶性
        if( (sum_w) % 2 == 0 ){
            // 偶数，存在一个精确的中点 x = mid
            // 1. 处理最接近 W_i 的区间 [W_i +1, mid -1]
            long long L1 = W_i +1;
            long long R1 = mid -1;
            if(L1 <= R1){
                // 计算有效范围 [max(A, L1), min(B, R1)]
                long long eff_L = max(L1, A);
                long long eff_R = min(R1, B);
                if(eff_L <= eff_R && cows[i].d){
                    total_S += (eff_R - eff_L +1);
                }
            }

            // 2. 处理中点 x = mid
            if(mid >= A && mid <= B){
                if(cows[i].d || cows[i+1].d){
                    total_S +=1;
                }
            }

            // 3. 处理最接近 W_j 的区间 [mid +1, W_j -1]
            long long L2 = mid +1;
            long long R2 = W_j -1;
            if(L2 <= R2){
                // 计算有效范围 [max(A, L2), min(B, R2)]
                long long eff_L = max(L2, A);
                long long eff_R = min(R2, B);
                if(eff_L <= eff_R && cows[i+1].d){
                    total_S += (eff_R - eff_L +1);
                }
            }
        }
        else{
            // 奇数，没有精确的中点
            // 1. 处理最接近 W_i 的区间 [W_i +1, mid]
            long long L1 = W_i +1;
            long long R1 = mid;
            if(L1 <= R1){
                // 计算有效范围 [max(A, L1), min(B, R1)]
                long long eff_L = max(L1, A);
                long long eff_R = min(R1, B);
                if(eff_L <= eff_R && cows[i].d){
                    total_S += (eff_R - eff_L +1);
                }
            }

            // 2. 处理最接近 W_j 的区间 [mid +1, W_j -1]
            long long L2 = mid +1;
            long long R2 = W_j -1;
            if(L2 <= R2){
                // 计算有效范围 [max(A, L2), min(B, R2)]
                long long eff_L = max(L2, A);
                long long eff_R = min(R2, B);
                if(eff_L <= eff_R && cows[i+1].d){
                    total_S += (eff_R - eff_L +1);
                }
            }
        }
    }

    // 处理体重大于最重牛的情况 [Wn +1, B]
    if(B >= cows[N-1].w +1 && A <= B){
        long long low = max(A, cows[N-1].w +1);
        long long high = B;
        if(low <= high && cows[N-1].d){
            total_S += (high - low +1);
        }
    }

    // 输出结果
    cout << total_S << "\n";

    return 0;
}