当前位置:网站首页>1324: [example 6.6] integer interval
1324: [example 6.6] integer interval
2022-07-07 10:32:00 【A program ape who beats the keyboard violently】
1324:【 example 6.6】 Integer interval
The time limit : 1000 ms Memory limit : 65536 KB
Submission number : 10710 Passing number : 6431
【 Title Description 】
Please program to complete the following tasks :
1. Read the number of closed intervals and their descriptions ;
2. Find a set with the least number of elements , So that for each interval , At least one integer belongs to the set , Output the number of elements of the collection .
【 Input 】
The first line contains the number of intervals nn,1≤n≤100001≤n≤10000, Next nn That's ok , Each line contains two integers a,ba,b, Separated by a space ,0≤a≤b≤100000≤a≤b≤10000, They are the start and end values of an interval .
【 Output 】
The number of set elements in the first line , For each interval, at least one integer belongs to the set , And the set contains the least number of elements .
【 sample input 】
4
3 6
2 4
0 2
4 7
【 sample output 】
2
【 Algorithm analysis 】
Algorithm model : to n Closed interval [ai,bi], Choose as few points as possible on the number axis , Make at least one point in each interval .
Algorithm : First click b1<=b2<=...<=bn Sort . Mark the right end of the current interval every time n, And move the current interval pointer to the right , Until the current interval does not contain n, Repeat the above operation .
【AC Code 】
#include<algorithm>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<string>
#include<vector>
using namespace std;
const int N=1e4+10;
inline int fread()
{
char ch=getchar();
int n=0,m=1;
while(ch<'0' or ch>'9')
{
if(ch=='-')m=-1;
ch=getchar();
}
while(ch>='0' and ch<='9')n=(n<<3)+(n<<1)+ch-48,ch=getchar();
return n*m;
}
void fwrite(int n)
{
if(n>9)fwrite(n/10);
putchar(n%10+'0');
}
int n,a[N],b[N],ans,m;
void qsort(int n,int m)// Multi keyword quick sorting
{
int i=n,j=m,mid=b[n+m>>1],mid1=a[n+m>>1];
while(i<=j)
{
while(b[i]<mid or(b[i]==mid and a[i]<mid1))i++;
while(b[j]>mid or(b[j]==mid and a[j]>mid1))j--;
if(i<=j)swap(b[i],b[j]),swap(a[i],a[j]),i++,j--;
}
if(n<j)qsort(n,j);
if(i<m)qsort(i,m);
}
signed main()
{
n=fread();
for(int i=1;i<=n;i++)a[i]=fread(),b[i]=fread();
qsort(1,n);
for(int i=1,j=-1;i<=n;i++)// While initializing the loop variable , initialization j
{// Make j=-1 You can make the operation of the first interval the same as that of other intervals
if(j>=a[i])continue;// If the current interval contains marked points , Just skip.
ans++,j=b[i];// Update marked points
}
fwrite(ans);
return 0;
}
The time limit : 1000 ms Memory limit : 65536 KB
Submission number : 10710 Passing number : 6431
【 Title Description 】
Please program to complete the following tasks :
1. Read the number of closed intervals and their descriptions ;
2. Find a set with the least number of elements , So that for each interval , At least one integer belongs to the set , Output the number of elements of the collection .
【 Input 】
The first line contains the number of intervals nn,1≤n≤100001≤n≤10000, Next nn That's ok , Each line contains two integers a,ba,b, Separated by a space ,0≤a≤b≤100000≤a≤b≤10000, They are the start and end values of an interval .
【 Output 】
The number of set elements in the first line , For each interval, at least one integer belongs to the set , And the set contains the least number of elements .
【 sample input 】
4
3 6
2 4
0 2
4 7
【 sample output 】
2
【 Algorithm analysis 】
Algorithm model : to n Closed interval [ai,bi], Choose as few points as possible on the number axis , Make at least one point in each interval .
Algorithm : First click b1<=b2<=...<=bn Sort . Mark the right end of the current interval every time n, And move the current interval pointer to the right , Until the current interval does not contain n, Repeat the above operation .
【AC Code 】
#include<algorithm>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<string>
#include<vector>
using namespace std;
const int N=1e4+10;
inline int fread()
{
char ch=getchar();
int n=0,m=1;
while(ch<'0' or ch>'9')
{
if(ch=='-')m=-1;
ch=getchar();
}
while(ch>='0' and ch<='9')n=(n<<3)+(n<<1)+ch-48,ch=getchar();
return n*m;
}
void fwrite(int n)
{
if(n>9)fwrite(n/10);
putchar(n%10+'0');
}
int n,a[N],b[N],ans,m;
void qsort(int n,int m)// Multi keyword quick sorting
{
int i=n,j=m,mid=b[n+m>>1],mid1=a[n+m>>1];
while(i<=j)
{
while(b[i]<mid or(b[i]==mid and a[i]<mid1))i++;
while(b[j]>mid or(b[j]==mid and a[j]>mid1))j--;
if(i<=j)swap(b[i],b[j]),swap(a[i],a[j]),i++,j--;
}
if(n<j)qsort(n,j);
if(i<m)qsort(i,m);
}
signed main()
{
n=fread();
for(int i=1;i<=n;i++)a[i]=fread(),b[i]=fread();
qsort(1,n);
for(int i=1,j=-1;i<=n;i++)// While initializing the loop variable , initialization j
{// Make j=-1 You can make the operation of the first interval the same as that of other intervals
if(j>=a[i])continue;// If the current interval contains marked points , Just skip.
ans++,j=b[i];// Update marked points
}
fwrite(ans);
return 0;
}
边栏推荐
- [dai6] mirror image of JZ27 binary tree
- 2022.7.5DAY597
- STM32 ADC and DMA
- Study summary of postgraduate entrance examination in August
- ArrayList线程不安全和解决方案
- Multisim -- software related skills
- 使用Tansformer分割三维腹部多器官--UNETR实战
- About hzero resource error (groovy.lang.missingpropertyexception: no such property: weight for class)
- Socket通信原理和实践
- 对存储过程进行加密和解密(SQL 2008/SQL 2012)
猜你喜欢
【STM32】STM32烧录程序后SWD无法识别器件的问题解决方法
Mendeley--免费的文献管理工具,给论文自动插入参考文献
1323:【例6.5】活动选择
对word2vec的一些浅层理解
Several schemes of building hardware communication technology of Internet of things
浅谈日志中的返回格式封装格式处理,异常处理
Experience sharing of software designers preparing for exams
Trajectory planning for multi robot systems: methods and Applications Overview reading notes
The Hal library is configured with a general timer Tim to trigger ADC sampling, and then DMA is moved to the memory space.
IIC基本知识
随机推荐
PDF文档签名指南
使用 load_decathlon_datalist (MONAI)快速加载JSON数据
Appx代碼簽名指南
[detailed explanation of Huawei machine test] tall and short people queue up
Trajectory planning for multi robot systems: methods and Applications Overview reading notes
反射效率为什么低?
[homework] 2022.7.6 write your own cal function
Using U2 net deep network to realize -- certificate photo generation program
When there are pointer variable members in the custom type, the return value and parameters of the assignment operator overload must be reference types
Use the fetch statement to obtain the repetition of the last row of cursor data
Inno Setup 打包及签名指南
[second on] [jeecgboot] modify paging parameters
Deeply analyze the main contents of erc-4907 agreement and think about the significance of this agreement to NFT market liquidity!
宁愿把简单的问题说一百遍,也不把复杂的问题做一遍
Leetcode-304: two dimensional area and retrieval - matrix immutable
Review of the losers in the postgraduate entrance examination
【HigherHRNet】 HigherHRNet 详解之 HigherHRNet的热图回归代码
BigDecimal数值比较
leetcode-560:和为 K 的子数组
php \n 换行无法输出