Table of Contents
- model 1
-
- Model description
- example
-
- Problem Description
- input format
- output format
- sample input
- sample output
- hint
- train of thought
- reference program
- model 2
-
- Model description
- example
-
- Problem Description
- input format
- output format
- Sample input 1
- Sample output 1
- Sample input 2
- Sample output 2
- hint
- train of thought
- reference program
- model three
-
- Model description
- example
-
- Problem Description
- input format
- output format
- Sample input 1
- Sample output 1
- Sample input 2
- Sample output 2
- hint
- train of thought
- reference program
Model 1
Model description
There are several intervals, ask how many points are required to satisfy at least one point in each interval.
A model like this, we call it a camera 1 model.
Example
Example: NKOJ P5220 camera 1 (the example is hidden by the teacher, the link may not be opened)
Description of the problem
There is a monitoring project: install several cameras on a straight road with a length of L to monitor traffic conditions. We can think of this road as the number line [0,L].
Boss He contracted this project, but the traffic control department put forward n requirements for the placement of cameras, and each requirement is in the form of [x, y], which means that at least one camera must be installed in the interval [x, y].
Boss He wants to complete this project with as little cost as possible, so he wants to know how many cameras need to be installed at least?
Input format
The first line, an integer n, indicates that there are n requirements to be met.
The next n lines, each with two integers x and y, represent a requirement, that is, at least one camera is required in the interval [x, y].
Output format
One line, an integer, indicates the minimum number of cameras required.
Sample input
4 3 6 twenty four 0 2 4 7
Sample output
2
Hint
1
≤
no
≤
100000
1\le n\le 100000
1≤n≤100000
0
≤
x
≤
the y
≤
L
≤
1000000000
0\le x\le y\le L\le 1000000000
0≤x≤y≤L≤1000000000
Thoughts
Each interval has a left endpoint l and a right endpoint r.
struct camera{
int l,r;
}c[100005];
We sort by the right endpoint from smallest to largest:
bool cmp(camera a,camera b){
return a.r < b.r;
}
Next is the important point:
We first define a variable first, which represents the bottom interval (as shown in the figure):
Next, use the for loop to judge, when c[first].r < c[i].l, it means that the range is consistent with c[first] The code> intervals no longer overlap. At this time, a camera should be installed and first should be updated.
Note: The number of cameras should be initialized to 1.
for(int i = 0; i < n; i ++ ){
scanf("%d%d", &c[i].l, &c[i].r);
}
sort(c,c + n,cmp);
for(int i = 1; i < n; i ++ ){
if(c[first].r < c[i].l){
ans + + ;
first = i;
}
}
Reference procedure
#includeusing namespace std; struct camera{ int l,r; }c[100005]; bool cmp(camera a, camera b){ return a.r < b.r; } int main(){ int n, first = 0, ans = 1; scanf("%d", &n); for(int i = 0; i < n; i ++ ){ scanf("%d%d", &c[i].l, &c[i].r); } sort(c,c + n,cmp); for(int i = 1; i < n; i ++ ){ if(c[first].r < c[i].l){ ans + + ; first = i; } } printf("%d",ans); return 0; }
Model 2
Model description
There are several small intervals, how many small intervals can be selected at least to completely cover the large interval?
A model like this, we call it a camera 2 model.
Example
Example: NKOJ P5221 Camera 2 (the example is hidden by the teacher, the link may not be opened)
Description of the problem
There is a straight road with a length of L in NK Middle School. Students can regard this road as a number axis. The coordinates of one section of the road are 0, and the coordinates of one section are L, which means the interval [0,L]
There are n cameras installed on this road, and each camera has a certain shooting interval. The interval covered by the i-th camera is [Xi, Yi]
With the attitude of saving electricity, Boss He wants to know, can the entire road be put under video surveillance by turning on at least a few cameras? Please help him answer.
Input format
The first line, two integers n and L
The next n lines, each with two integers x and y, represent the area captured by a camera, that is, the interval [x, y] is covered by the camera.
Output format
An integer, indicating the minimum number of cameras that need to be turned on
If there is no solution, output -1
Sample input 1
4 6 3 6 twenty four 0 2 4 7
Sample output 1
3
Sample input 2
10 28 5 24 8 27 9 19 3 17 13 18 9 25 19 29 12 15 25 29 0 6
Sample output 2
3
Hint
1
≤
no
≤
100000
1\le n\le 100000
1≤n≤100000
1
≤
L
≤
1000000000
1\le L\le 1000000000
1≤L≤1000000000
0
≤
x
≤
the y
≤
1000000000
0\le x\le y\le 1000000000
0≤x≤y≤1000000000
Example description: The selected cameras cover the following intervals respectively
[0,2] [2,4] [3,6]
Thoughts
Sort the line segments by Left endpoints from small to large, if the left endpoints are the same, sort by Right endpoints from large to small.
Discuss each line segment in turn from left to right, and select the line segment with the largest right endpoint first.
- Record the farthest distance
nowfarthat can be covered among the currently selected line segments. - Discuss all line segments whose left endpoint <=
nowfarand are not discussed, and record the maximum valuemaxrightof the right endpoint. - If
maxright>nowfar, thennowfar = maxright. Otherwise there is no solution.
Reference procedure
#include <bits/stdc++.h>
using namespace std;
int n,l;
struct camera{
int l,r;
}c[100005];
bool cmp(camera a, camera b){
if(a.l == b.l){
return a.r > b.r;
}else{
return a.l < b.l;
}
}
int solve(){
if(c[1].l > 0){
return -1;
}
int ans = 1;
int nowfar = c[1].r;
int maxright = c[1].r;
if(nowfar >= l){
return ans;
}
int i = 2;
while(true){
for(; (i <= n & amp; & amp; c[i].l <= nowfar); i ++ ){
maxright = max(maxright,c[i].r);
}
if(maxright <= nowfar){
return -1;
}
ans + + ;
nowfar = maxright;
if(nowfar >= l){
return ans;
}
}
return -1;
}
int main(){
int tp;
scanf("%d%d", &n, &l);
for(int i = 1; i <= n; i ++ ){
scanf("%d%d", &c[i].l, &c[i].r);
}
sort(c+1,c+n+1,cmp);
tp = solve();
printf("%d",tp);
return 0;
}
Model Three
Model description
There are several intervals, how many intervals can be selected at most so that they do not overlap?
A model like this, we call it a camera 3 model.
Example
Example: NKOJ P5227 Camera 3 (the example is hidden by the teacher, the link may not be opened)
Description of the problem
There is a straight road with a length of L in NK Middle School. Students can regard this road as a number axis. The coordinates of one section of the road are 0, and the coordinates of one section are L, which means the interval [0,L]
There are n cameras installed on this road, and each camera has a certain shooting interval. The interval covered by the i-th camera is
Boss He wants to turn on k cameras so that the shooting intervals of these k cameras do not overlap each other. What is the maximum value of k?
Input format
The first row is a positive integer
no
no
n;
In the following
no
no
In n lines, each line has
2
2
2 numbers
a
i
,
b
i
a_i, b_i
ai?,bi?, describe each line segment.
Output format
output an integer, for
k
k
The maximum value of k.
Sample input 1
10 7 8 1 7 0 3 4 9 0 6 5 7 0 3 7 8 7 10 4 7
Sample output 1
3
Sample input 2
10 0 3 1 4 15 19 1 2 1 3 2 5 4 7 twenty four 3 8 7 12
Sample output 2
5
Hint
for
20
%
20\%
20% of the data,
no
≤
10
n\le 10
n≤10;
for
50
%
50\%
50% of the data,
no
≤
1
0
3
n\le 10^3
n≤103;
for
70
%
70\%
70% of the data,
no
≤
1
0
5
n\le 10^5
n≤105;
for
100
%
100\%
100% data,
no
≤
1
0
6
,
0
≤
a
i
<
b
i
≤
1
0
6
n\le 10^6,0\le a_i < b_i\le 10^6
n≤106, 0≤ai?
Thoughts
- Sort the right endpoints of all line segments from smallest to largest.
- Discuss each line segment from left to right, and select the line segment whose left endpoint is larger than the right endpoint of the last selected line segment and whose right endpoint is smaller.
Reference procedure
#include <bits/stdc++.h>
using namespace std;
struct camera{
int l,r;
}c[1000005];
bool cmp(camera a, camera b){
return a.r < b.r;
}
int main(){
int n,ans = 1,lastr;
scanf("%d", &n);
for(int i = 0; i < n; i ++ ){
scanf("%d%d", &c[i].l, &c[i].r);
}
sort(c,c + n,cmp);
lastr = c[0].r;
for(int i = 1; i < n; i ++ ){
if(c[i].l >= lastr){
ans + + ;
lastr = c[i].r;
}
}
printf("%d",ans);
return 0;
}