当前位置:网站首页>1324:【例6.6】整数区间
1324:【例6.6】整数区间
2022-07-07 08:14:00 【暴揍键盘的程序猿】
1324:【例6.6】整数区间
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 10710 通过数: 6431
【题目描述】
请编程完成以下任务:
1.读取闭区间的个数及它们的描述;
2.找到一个含元素个数最少的集合,使得对于每一个区间,都至少有一个整数属于该集合,输出该集合的元素个数。
【输入】
首行包括区间的数目nn,1≤n≤100001≤n≤10000,接下来的nn行,每行包括两个整数a,ba,b,被一空格隔开,0≤a≤b≤100000≤a≤b≤10000,它们是某一个区间的开始值和结束值。
【输出】
第一行集合元素的个数,对于每一个区间都至少有一个整数属于该集合,且集合所包含元素数目最少。
【输入样例】
4
3 6
2 4
0 2
4 7
【输出样例】
2
【算法分析】
算法模型:给n个闭区间[ai,bi],在数轴上选尽量少的点,使每个区间内至少有一个点。
算法:首先按b1<=b2<=...<=bn排序。每次标记当前区间的右端点n,并右移当前区间指针,直到当前区间不包含n,再重复上述操作。
【AC代码】
#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)//多关键字快排
{
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++)//在初始化循环变量的同时,初始化j
{//令j=-1可以使第一个区间与其他区间的操作相同
if(j>=a[i])continue;//如果当前区间包含标记点,就跳过
ans++,j=b[i];//更新标记点
}
fwrite(ans);
return 0;
}
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 10710 通过数: 6431
【题目描述】
请编程完成以下任务:
1.读取闭区间的个数及它们的描述;
2.找到一个含元素个数最少的集合,使得对于每一个区间,都至少有一个整数属于该集合,输出该集合的元素个数。
【输入】
首行包括区间的数目nn,1≤n≤100001≤n≤10000,接下来的nn行,每行包括两个整数a,ba,b,被一空格隔开,0≤a≤b≤100000≤a≤b≤10000,它们是某一个区间的开始值和结束值。
【输出】
第一行集合元素的个数,对于每一个区间都至少有一个整数属于该集合,且集合所包含元素数目最少。
【输入样例】
4
3 6
2 4
0 2
4 7
【输出样例】
2
【算法分析】
算法模型:给n个闭区间[ai,bi],在数轴上选尽量少的点,使每个区间内至少有一个点。
算法:首先按b1<=b2<=...<=bn排序。每次标记当前区间的右端点n,并右移当前区间指针,直到当前区间不包含n,再重复上述操作。
【AC代码】
#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)//多关键字快排
{
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++)//在初始化循环变量的同时,初始化j
{//令j=-1可以使第一个区间与其他区间的操作相同
if(j>=a[i])continue;//如果当前区间包含标记点,就跳过
ans++,j=b[i];//更新标记点
}
fwrite(ans);
return 0;
}
边栏推荐
- Differences between MCU and MPU
- Wallys/IPQ6010 (IPQ6018 FAMILY) EMBEDDED BOARD WITH ON-BOARD WIFI DUAL BAND DUAL CONCURRENT
- 浅谈日志中的返回格式封装格式处理,异常处理
- LeetCode 练习——113. 路径总和 II
- ORM model -- creation and query of data records
- The landing practice of ByteDance kitex in SEMA e-commerce scene
- Advanced function learning in ES6
- 【华为机试真题详解】高矮个子排队
- 2022.7.5DAY597
- How to cancel automatic saving of changes in sqlyog database
猜你喜欢
[learning notes - Li Hongyi] Gan (generation of confrontation network) full series (I)
[second on] [jeecgboot] modify paging parameters
Web3.0 series distributed storage IPFs
Programming features of ISP, IAP, ICP, JTAG and SWD
LLVM之父Chris Lattner:為什麼我們要重建AI基礎設施軟件
Word自动生成目录的方法
Appx代碼簽名指南
The method of word automatically generating directory
Wallys/IPQ6010 (IPQ6018 FAMILY) EMBEDDED BOARD WITH ON-BOARD WIFI DUAL BAND DUAL CONCURRENT
Leetcode exercise - 113 Path sum II
随机推荐
Programming features of ISP, IAP, ICP, JTAG and SWD
Introduction to energy Router: Architecture and functions for energy Internet
Prototype object in ES6
Embedded background - chip
ORM model -- creation and query of data records
【acwing】786. 第k个数
[ORM framework]
Mongodb creates an implicit database as an exercise
【STM32】STM32烧录程序后SWD无法识别器件的问题解决方法
Kotlin实现微信界面切换(Fragment练习)
ISP、IAP、ICP、JTAG、SWD的编程特点
2022.7.4DAY596
ISP、IAP、ICP、JTAG、SWD的编程特点
EasyExcel读取写入简单使用
This article explains the complex relationship between MCU, arm, muc, DSP, FPGA and embedded system
MCU is the most popular science (ten thousand words summary, worth collecting)
A wave of open source notebooks is coming
Advanced function learning in ES6
【acwing】786. Number k
IPv4 socket address structure