題干：
?

小w有m條線段，編號(hào)為1到m。

用這些線段覆蓋數(shù)軸上的n個(gè)點(diǎn)，編號(hào)為1到n。

第i條線段覆蓋數(shù)軸上的區(qū)間是L[i]，R[i]。

覆蓋的區(qū)間可能會(huì)有重疊，而且不保證m條線段一定能覆蓋所有n個(gè)點(diǎn)。

現(xiàn)在小w不小心丟失了一條線段，請(qǐng)問丟失哪條線段，使數(shù)軸上沒被覆蓋到的點(diǎn)的個(gè)數(shù)盡可能少，請(qǐng)輸出丟失的線段的編號(hào)和沒被覆蓋到的點(diǎn)的個(gè)數(shù)。如果有多條線段符合要求，請(qǐng)輸出編號(hào)最大線段的編號(hào)（編號(hào)為1到m）。

輸入描述:

第一行包括兩個(gè)正整數(shù)n，m(1≤n，m≤10^5)。 接下來m行，每行包括兩個(gè)正整數(shù)L[i]，R[i](1≤L[i]≤R[i]≤n)。

輸出描述:

輸出一行，包括兩個(gè)整數(shù)a b。 a表示丟失的線段的編號(hào)。 b表示丟失了第a條線段后，沒被覆蓋到的點(diǎn)的個(gè)數(shù)。

示例1

輸入

復(fù)制

5 3 1 3 4 5 3 4

輸出

復(fù)制

3 0

說明

若丟失第1條線段，1和2沒被線段覆蓋到。 若丟失第2條線段，5沒被線段覆蓋到。 若丟失第3條線段，所有點(diǎn)都被線段覆蓋到了。

示例2

輸入

復(fù)制

6 2 1 2 4 5

輸出

復(fù)制

2 4

說明

若丟失第1條線段，1，2，3，6沒被線段覆蓋到。 若丟失第2條線段，3，4，5，6沒被線段覆蓋到。

題目大意：

? ? ? 給你1..n長(zhǎng)度的總區(qū)間，外加m條線段(可能沒有覆蓋所有1~n的點(diǎn))。問去掉哪一條線段 使得總區(qū)間未被覆蓋的點(diǎn)最少。

? ? ? 輸出那一條線段的編號(hào)，并且輸出未被覆蓋的點(diǎn)的個(gè)數(shù)。

解題報(bào)告：

? ? 因?yàn)槭亲詈蟛樵?#xff0c;求個(gè)差分，，，就行了。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; int l[MAX],r[MAX]; int d[MAX]; int a[MAX]; int sum[MAX]; int main() {int n,m;cin>>n>>m;for(int i = 1; i<=m; i++) {scanf("%d %d",l+i,r+i);d[l[i]]++;d[r[i]+1]--;}int zeros=0;for(int i = 1; i<=n; i++) {a[i] = a[i-1] + d[i];if(a[i]==0) zeros++;}for(int i = 1; i<=n; i++) {sum[i] = sum[i-1] + (a[i]==1);}int minn = 0x3f3f3f3f,id;for(int i = m; i>=1; i--) {if(sum[r[i]]-sum[l[i]-1] < minn) {id = i;minn = sum[r[i]]-sum[l[i]-1];}}printf("%d %d\n",id,minn+zeros);return 0 ;}

?

總結(jié)

以上是生活随笔為你收集整理的【牛客 - 297C】little w and Segment Coverage（差分数组，区间差分，思维，卡线段树）☆的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。