1323：【例6.5】活动选择

 

1323：【例6.5】活动选择

时间限制: 1000 ms         内存限制: 65536 KB
提交数: 15984     通过数: 8866

【题目描述】

学校在最近几天有nn个活动，这些活动都需要使用学校的大礼堂，在同一时间，礼堂只能被一个活动使用。由于有些活动时间上有冲突，学校办公室人员只好让一些活动放弃使用礼堂而使用其他教室。

现在给出nn个活动使用礼堂的起始时间beginibegini和结束时间endi(begini<endi)endi(begini<endi)，请你帮助办公室人员安排一些活动来使用礼堂，要求安排的活动尽量多。

【输入】

第一行一个整数n(n≤1000)n(n≤1000)；

接下来的nn行，每行两个整数，第一个beginibegini，第二个是endi(begini<endi≤32767)endi(begini<endi≤32767)。

【输出】

输出最多能安排的活动个数。

【输入样例】

11
3 5
1 4
12 14
8 12
0 6
8 11
6 10
5 7
3 8
5 9
2 13

【输出样例】

4

【算法分析】

算法模型：给n个开区间（begini，endi），选择尽量多的区间，使得两两不交。

做法：首先按照end1<=end2<=...<=endn的顺序排序，依次考虑各个活动，如果没有和已经选择的活动冲突，就选；否则就不选。

正确性：如果不选end1，假设第一个选择的是endi，则如果endi和end1不交叉则多选一个end1更划算；如果交叉则把endi换成end1不影响后续选择。

【CE代码】

#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++)		//在初始化循环变量的同时，初始化 t
	 if(begin[i]>=t) {ans++;t=end[i];} 
	 				//如果当前活动与之前最后结束的活动不冲突，就接受当前活动
	cout<<ans<<endl; 
}
int main()
{
	init();
	qsort(1,n);
	solve();
	return 0;
}

给个关注吧

【AC代码】

#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;
}

 这一题一题的都他妈有毒。

给个关注吧