题目链接:https://ac.nowcoder.com/acm/contest/297/C
对于刚开始的m条边我们可以直接用差分数组去写,然后for循环还原当前的每个点的覆盖数,我们要记录一下没有被m条线段覆盖的点的个数,再去对于每一个只被一条线段覆盖到的点,我们另外用一个数组去维护一个前缀和(只被1条线段覆盖的为1,其余为0),然后遍历每一条线段,我们就可以O(1)的查询出被这条边覆盖的点有多少个了,看呆码可能会更好理解一点。
AC代码:
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
struct Node{
int l, r;
}Edge[maxn];
int pre[maxn], a[maxn];
int n,m,pos,ans;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&Edge[i].l, &Edge[i].r);
a[Edge[i].l] += 1;
a[Edge[i].r + 1] -= 1;
}
pos = ans = 0;
for(int i=1;i<=n;i++){
a[i] += a[i-1]; // 还原覆盖情况
pre[i] += pre[i-1]; // 维护只被一条线段覆盖的前缀和
if(a[i] == 0) ans ++; // 记录没有被m条线段覆盖的点的个数
if(a[i] == 1) pre[i] ++; // 只被一条线段覆盖
}
int cnt = n;
for(int i=1;i<=m;i++){
int xx = pre[Edge[i].r] - pre[Edge[i].l - 1]; // 只被当前线段覆盖的点的个数
if(cnt >= xx){
cnt = xx;
pos = i;
}
}
printf("%d %d\n",pos, ans + cnt);
return 0;
}