当前位置:网站首页>1323: [example 6.5] activity selection
1323: [example 6.5] activity selection
2022-07-07 10:32:00 【A program ape who beats the keyboard violently】
1323:【 example 6.5】 Activity selection
The time limit : 1000 ms Memory limit : 65536 KB
Submission number : 15984 Passing number : 8866
【 Title Description 】
The school is open in recent days nn An activity , These activities need to use the school auditorium , At the same time , The auditorium can only be used by one activity . Because of the time conflict in some activities , School office staff had to let some activities abandon the use of the auditorium and use other classrooms .
Now give nn The starting time of using the auditorium for an activity beginibegini And end time endi(begini<endi)endi(begini<endi), Please help the office staff arrange some activities to use the auditorium , Ask to arrange as many activities as possible .
【 Input 】
The first line is an integer n(n≤1000)n(n≤1000);
Next nn That's ok , Two integers per line , first beginibegini, The second is endi(begini<endi≤32767)endi(begini<endi≤32767).
【 Output 】
Output the maximum number of activities that can be arranged .
【 sample input 】
11
3 5
1 4
12 14
8 12
0 6
8 11
6 10
5 7
3 8
5 9
2 13
【 sample output 】
4
【 Algorithm analysis 】
Algorithm model : to n An open interval (begini,endi), Choose as many intervals as possible , Make two not pay .
practice : First of all, in accordance with the end1<=end2<=...<=endn The order of , Consider each activity in turn , If there is no conflict with the selected activity , Just choose ; Otherwise, you don't choose .
correctness : If you don't choose end1, Suppose the first choice is endi, If endi and end1 If it doesn't intersect, choose one more end1 More cost effective ; If it crosses, turn endi Switch to end1 Does not affect subsequent choices .
【CE Code 】
#include<iostream>
using namespace std;
const int N=2e3;
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,begin[N],end[N];
void init()
{
n=fread();
for(int i=1;i<=n;i++)begin[i]=fread(),end[i]=fread();
}
void qsort(int m,int x)
{
int i=m,j=x,mid=end[m+x>>1];
while(i<=j)
{
while(end[i]<mid)i++;
while(end[j]>mid)j--;
if(i<=j)swap(end[i],end[j]),swap(begin[i],begin[j]),i++,j--;
}
if(m<j)qsort(m,j);
if(i<x)qsort(i,x);
}
void f()
{
int ans=0;
for(int i=1,j=-1;i<=n;i++)
if(begin[i]>=j)ans++,j=end[i];
fwrite(ans);
}
signed main()
{
init(),qsort(1,n),f();
return 0;
}
#include<stdio.h>
#include<iostream>
using namespace std;
const int N=2e3;
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,begin[N],end[N];
void init()
{
n=fread();
for(int i=1;i<=n;i++)begin[i]=fread(),end[i]=fread();
}
void qsort(int m,int x)
{
int i=m,j=x,mid=end[m+x>>1];
while(i<=j)
{
while(end[i]<mid)i++;
while(end[j]>mid)j--;
if(i<=j)swap(end[i],end[j]),swap(begin[i],begin[j]),i++,j--;
}
if(m<j)qsort(m,j);
if(i<x)qsort(i,x);
}
void f()
{
int ans=0;
for(int i=1,j=-1;i<=n;i++)
if(begin[i]>=j)ans++,j=end[i];
fwrite(ans);
}
signed main()
{
init(),qsort(1,n),f();
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=2e3;
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,begin[N],end[N];
void init()
{
n=fread();
for(int i=1;i<=n;i++)begin[i]=fread(),end[i]=fread();
}
void qsort(int m,int x)
{
int i=m,j=x,mid=end[m+x>>1];
while(i<=j)
{
while(end[i]<mid)i++;
while(end[j]>mid)j--;
if(i<=j)swap(end[i],end[j]),swap(begin[i],begin[j]),i++,j--;
}
if(m<j)qsort(m,j);
if(i<x)qsort(i,x);
}
void f()
{
int ans=0;
for(int i=1,j=-1;i<=n;i++)
if(begin[i]>=j)ans++,j=end[i];
fwrite(ans);
}
signed main()
{
init(),qsort(1,n),f();
return 0;
}
#include<iostream>
using namespace std;
int n,begin[1001],end[1001];
void init()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>begin[i]>>end[i];
}
void qsort(int x,int y)
{
int i,j,mid,t;
i=x;j=y;mid=end[(x+y)/2];
while(i<=j)
{
while(end[i]<mid)i++;
while(end[j]>mid)j--;
if(i<=j)
{
t=end[j];end[j]=end[i];end[i]=t;
t=begin[j];begin[j]=begin[i];begin[i]=t;
i++;j--;
}
}
if(x<j) qsort(x,j);
if(i<y) qsort(i,y);
}
void solve()
{
int ans=0;
for(int i=1,t=-1;i<=n;i++) // While initializing the loop variable , initialization t
if(begin[i]>=t) {ans++;t=end[i];}
// If the current activity does not conflict with the last activity before , Just accept the current activity
cout<<ans<<endl;
}
int main()
{
init();
qsort(1,n);
solve();
return 0;
}
【AC Code 】
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct meet{
int begin;
int end;
friend bool operator <(meet a,meet b){
return a.end<b.end;
}
}me[1005];
int main(int argc, char *argv[])
{
int n,sum=1;
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d %d",&me[i].begin,&me[i].end);
sort(me,me+n);
int l=me[0].begin,r=me[0].end;
for(int i=1;i<n;i++){
if(me[i].begin>=r){
l=me[i].begin;
r=me[i].end;
sum++;
}
}
printf("%d\n",sum);
return 0;
}
This question is all Fucking Toxic .
边栏推荐
- 对word2vec的一些浅层理解
- 对存储过程进行加密和解密(SQL 2008/SQL 2012)
- Learning records - high precision addition and multiplication
- Leetcode-303: region and retrieval - array immutable
- EasyExcel读取写入简单使用
- 成为优秀的TS体操高手 之 TS 类型体操前置知识储备
- Guide de signature du Code Appx
- Multisim--软件相关使用技巧
- 枪出惊龙,众“锁”周之
- Experience sharing of software designers preparing for exams
猜你喜欢
IIC Basics
Encrypt and decrypt stored procedures (SQL 2008/sql 2012)
IO model review
使用U2-Net深层网络实现——证件照生成程序
Several schemes of building hardware communication technology of Internet of things
浅谈日志中的返回格式封装格式处理,异常处理
路由器开发知识汇总
【acwing】786. Number k
Serial communication relay Modbus communication host computer debugging software tool project development case
PDF文档签名指南
随机推荐
Guid primary key
table宽度比tbody宽度大4px
移动端通过设置rem使页面内容及字体大小自动调整
基于HPC场景的集群任务调度系统LSF/SGE/Slurm/PBS
Easyexcel read write simple to use
How embedded engineers improve work efficiency
Pre knowledge reserve of TS type gymnastics to become an excellent TS gymnastics master
[email protected] can help us get the log object quickly
Using U2 net deep network to realize -- certificate photo generation program
施努卡:机器视觉定位技术 机器视觉定位原理
Remote meter reading, switching on and off operation command
浅谈日志中的返回格式封装格式处理,异常处理
A small problem of bit field and symbol expansion
The Hal library is configured with a general timer Tim to trigger ADC sampling, and then DMA is moved to the memory space.
Adb 实用命令(网络包、日志、调优相关)
【acwing】789. Range of numbers (binary basis)
Some superficial understanding of word2vec
串口通讯继电器-modbus通信上位机调试软件工具项目开发案例
Study summary of postgraduate entrance examination in July
C logging method