题解：P9426 [蓝桥杯 2023 国 B] 抓娃娃

xu_zhihao · 2024-03-17 21:28:08 · 题解

说明：

• 本题题目样例有些奇怪，个人认为样例第二问因输出 3，如下图所示。

题目理解：

• 这道题目居然没给测试点与时间限制，只能先把它当成暴力题来做了。每次输入一个爪子的左区间与右区间，即 L_i 与 R_i。都要枚举 n 个可能能被这个爪子抓到的区间，再统计此爪子能抓到此区间的范围，判断是否大于等于此区间长度的一半，即 k \ge \lceil (r_i-l_i) \div 2\rceil，其中 k 为抓到此区间的长度。最后输出符合条件的个数即可。

code：

#include<bits/stdc++.h>
using namespace std;
int mid[1000010];
double l[1000010];
double r[1000010];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>l[i]>>r[i];
        mid[i]=ceil((r[i]-l[i]+1)/2);
    }
    for(int i=0;i<m;i++)
    {
        int ret=0;
        int L,R;
        cin>>L>>R;
        for(int j=0;j<n;j++)
        {
            int cnt=0;
            for(int k=L;k<=r[j] && k<=R;k++)
            {
                if(k>=L)cnt++;
            }
            if(cnt>=mid[j])
            {
                ret++;
            }
        }
        cout<<ret<<endl;
    }
}