牛客练习赛34的C题题解

#include <iostream>
#include <cstring>
using namespace std;
const int N = 100001;
int main(){
    int L[N], R[N];
    int b[N], s[N];
    memset(b, 0, sizeof(b));
    memset(s, 0, sizeof(s));
    int n, m, cnt = 0;
    cin >> n >> m;
    for(int i = 1; i <= m; i++){  //这个循环和“b[i] += b[i - 1];”用于修改区间的值
        cin >> L[i] >> R[i];
        b[L[i]]++;
        b[R[i] + 1]--;
    }
    for(int i = 1; i <= n; i++){
        b[i] += b[i - 1];
        s[i] = s[i - 1] + (b[i] == 1);//s[i]用于统计从0到i总共有多少b[i]==1的点
        cnt += (b[i] == 0);//cnt用于统计没被覆盖的点
    }
    int now = 0, min = 1000000, ans = 1;
    for(int i = 1; i <= m; i++){
        now = s[R[i]] - s[L[i] - 1]; //now用于储存每条线段覆盖值为1的点的个数
        if(now <= min){
            min = now;
            ans = i;
        }
    }
    cout << ans << " " << min + cnt << endl;
    return 0;
}#include <iostream>
#include <cstring>
using