题解：AT_abc408_c [ABC408C] Not All Covered

ikun_god · 2025-06-01 09:00:53 · 题解

差分板子题。
如果没有学过差分请自行oi-wiki。
根据贪心思想，本题的答案就是 n 个点中被炮塔覆盖最少的点，即我们需要统计每个炮塔具体覆盖到了哪些点，使用差分就可以了。
代码：

#include<bits/stdc++.h>
using namespace std;
int d[10110],n,m;
int main()
{
    cin>>n>>m;
    while (m--){
        int l,r;
        cin>>l>>r;
        d[l]+=1;
        d[r+1]-=1;
    }
    for (int i=1;i<=n;++i){
        d[i]+=d[i-1];
    }
    int ans=1e9;
    for (int i=1;i<=n;++i){
        ans=min(ans,d[i]);
    }
    cout<<ans<<endl;
    return 0;
}

不会这都有人抄吧 qwq