Description
n户人家住在一条直线上，从左往右依次编号为1，2，...，n。起初，有m户人家感染了COVID-19，而接下来的每天感染的人家都会感染他家左右两家的人，问t天后总共有多少人家会感染。
Input
第一行输入三个整数n(1 <= n <= 2e5)，m(0 <= m <= n)，t(1<= t <= 2e5)。
第二行m个整数ai(1 <= ai <= n)，代表最初感染的m户人家的编号。
Output
输出一个整数，代表最后会有多少人家感染。
Sample Input 1
10 3 2
1 3 4
Sample Output 1
6
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 7;
int a[maxn];
vector<pair<int,int> > v;
int main()
{
int n, m, t;
cin >> n >> m >> t;
for(int i = 1; i <= m; i++)
cin >> a[i];
sort(a + 1, a + 1 + m);
for(int i = 1; i <= m; i++)
{
int l = max(1, a[i] - t);
int r = min(n, a[i] + t);
v.push_back(make_pair(l, r));
}
int i = 0, res = 0;
while(i < m)
{
int j = i + 1;
while(j < m && v[j].first <= v[j - 1].second)
{
// printf("v[j].first = %d v[j - 1].second = %d\n",v[j].first,v[j-1].second);
j++;
// printf("j = %d\n",j);
}
res += v[j - 1].second - v[i].first + 1;
// printf("res = %d\n",res);
i = j;
}
cout << res << endl;
return 0;
}
Analysis:
This question is actually centered at 'm' point,generates 'm' line segments,the length of each generated line segments is '2m', then merge these line segments.
detail:
1.Sort each household.
2.The information of the m-th line segment can be expressed as
(max(1,a[i]-t),min(n,a[i]+t))
store them with 'pair'.
vector<pair<int,int> > v
3.Merge line segments.'j' increases with the number of overlapping line segments,subtract the head from the tail to get the length of the line segment,then assign the value 'j' to 'i',judge again.General speaking,calculate the length of each segments separately,if the merged line segments break from the middle.
