链接:https://ac.nowcoder.com/acm/contest/297/C

来源:牛客网

时间限制:C/C++ 1秒,其他语言2秒

空间限制:C/C++ 262144K,其他语言524288K

64bit IO Format: %lld

题目描述

小w有m条线段,编号为1到m。

用这些线段覆盖数轴上的n个点,编号为1到n。

第i条线段覆盖数轴上的区间是L[i],R[i]。

覆盖的区间可能会有重叠,而且不保证m条线段一定能覆盖所有n个点。

现在小w不小心丢失了一条线段,请问丢失哪条线段,使数轴上没被覆盖到的点的个数尽可能少,请输出丢失的线段的编号和没被覆盖到的点的个数。如果有多条线段符合要求,请输出编号最大线段的编号(编号为1到m)。

输入描述:

第一行包括两个正整数n,m(1≤n,m≤10^5)。
接下来m行,每行包括两个正整数L[i],R[i](1≤L[i]≤R[i]≤n)。

输出描述:

输出一行,包括两个整数a b。
a表示丢失的线段的编号。
b表示丢失了第a条线段后,没被覆盖到的点的个数。

示例1

输入

5 3
1 3
4 5
3 4

输出

3 0

说明

若丢失第1条线段,1和2没被线段覆盖到。
若丢失第2条线段,5没被线段覆盖到。
若丢失第3条线段,所有点都被线段覆盖到了。

示例2

输入

6 2
1 2
4 5

输出

2 4

说明

若丢失第1条线段,1,2,3,6没被线段覆盖到。
若丢失第2条线段,3,4,5,6没被线段覆盖到。

题解:利用差分数组更新区间覆盖问题

AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream> using namespace std; int d[100005]= {0};
int L[100005]= {0},R[100005]= {0};
int sum[100005]= {0}; int main() {
int n,m;
cin>>n>>m;
memset(d,0,sizeof(d));
for(int t=1; t<=m; t++) {
scanf("%d%d",&L[t],&R[t]);
d[L[t]]++;
d[R[t]+1]--;
}
int cnt=0;
for(int t=1; t<=n; t++) {
d[t]+=d[t-1];
if(d[t]==0) {
cnt++;
}
if(d[t]==1) {
sum[t]=1;
}
sum[t]+=sum[t-1];
}
int minn=0x3f3f3f3f;
int k=-1;
for(int t=1; t<=m; t++) {
int ans=sum[R[t]]-sum[L[t]-1];
if(ans<=minn) {
minn=ans;
k=t;
}
}
printf("%d %d\n",k,cnt+minn); return 0;
}
05-11 18:11
查看更多