NC21753. little w and Segment Coverage
描述
小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
输入:
6 2 1 2 4 5
输出:
2 4
说明:
若丢失第1条线段，1，2，3，6没被线段覆盖到。C++14(g++5.4) 解法, 执行用时: 30ms, 内存消耗: 1640K, 提交时间: 2019-04-20 20:22:24
#include<cstdio>
const int N=1000118;
int sum[N]={0},l[N],r[N];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&l[i],&r[i]);
sum[l[i]]++;
sum[r[i]+1]--;
}
int num=0,no=0;
for(int i=1;i<=n;i++)
{
num+=sum[i];
sum[i]=num;
if(sum[i]==0)
no++;
if(sum[i]!=1)
sum[i]=0;
sum[i]+=sum[i-1];
}
int id=1,len=n+1;
for(int i=1;i<=m;i++)
{
int dis=sum[r[i]]-sum[l[i]-1];
if(dis<=len)
id=i,len=dis;
}
printf("%d %d\n",id,len+no);
return 0;
}
Python3(3.5.2) 解法, 执行用时: 844ms, 内存消耗: 26688K, 提交时间: 2018-12-24 18:19:27
n, m = map(int, input().split())
dp = [0] * (n+2) # 因为有dp[r+1]，为了不溢出
q = []
for _ in range(m):
l,r = map(int, input().split())
dp[l] += 1
dp[r+1] -= 1
q.append([l,r])
for i in range(1, n+1):
dp[i] += dp[i-1]
c = [0] * (n+1) # c[i]表示dp中前i个数有多少个1
for i in range(1, n+1):
c[i] = c[i-1] + int(dp[i] == 1)
index, cnt = -1, n
for i in range(m):
l,r = q[i]
count = c[r] - c[l-1]
if count <= cnt:
index, cnt = i+1, count
print(index, cnt + dp[1:n+1].count(0))
C++11(clang++ 3.9) 解法, 执行用时: 35ms, 内存消耗: 2004K, 提交时间: 2018-12-14 19:15:23
#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
using namespace std;
const int N=1e5+5;
int n,m,a[N],id,mi,l[N],r[N],sum[N],all;
int main(){
scanf("%d%d",&n,&m);
rep (i,1,m) scanf("%d%d",l+i,r+i),a[l[i]]++,a[r[i]+1]--;
rep (i,1,n){
a[i]+=a[i-1],sum[i]=sum[i-1]+(a[i]==1);
all+=!a[i];
}
mi=n+1;
for (int i=m;i;i--) if (sum[r[i]]-sum[l[i]-1]<mi) mi=sum[r[i]]-sum[l[i]-1],id=i;
printf("%d %d\n",id,all+mi);
return 0;
}