51nod1428活动安排问题

关键词：

51Nod   1428  活动安排问题

Link： http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1428

有若干个活动，第i个开始时间和结束时间是[Si,fi)，同一个教室安排的活动之间不能交叠，求要安排所有活动，最少需要几个教室？ 

第一行一个正整数n (n <= 10000)代表活动的个数。
第二行到第(n + 1)行包含n个开始时间和结束时间。
开始时间严格小于结束时间，并且时间都是非负整数，小于1000000000

一行包含一个整数表示最少教室的个数。

3
1 2
3 4
2 9

2

题解：

简单的题目， 排序之后， 放进优先队列中，进行模拟，解决！

#include <iostream> 
#include <cstdio> 
#include <cstring> 
#include <queue> 
using namespace std; 
const int maxn =  100000 + 5; 

struct Node{
	int r, l; 
}nd[maxn]; 
int n; 

int cmp(const void *a, const void *b){
	Node *aa = (Node *)a; 
	Node *bb = (Node *)b; 
	return aa->l - bb->l; 
}

int main(){
///	freopen("in.txt", "r", stdin); 

	int x, y, p, ans, cur; 
	while(scanf("%d", &n) != EOF){
		for(int i=0; i<n; ++i){
			scanf("%d %d", &nd[i].l, &nd[i].r); 
		}
		qsort(nd, n, sizeof(nd[0]), cmp); 

		ans = 1; 
		priority_queue<int, vector<int>, greater<int>> qt; 
		qt.push(nd[0].r); 
		for(int i=1; i<n; ++i){
			if(!qt.empty()){
				cur = qt.top(); 
				if(nd[i].l >= cur){
					qt.pop();  
				}else{
					++ans; 
				}
				qt.push(nd[i].r); 
			}else{
				qt.push(nd[i].r); 
			}
		}
		printf("%d
", ans);
	}
	return 0; 
}

活动安排问题（贪心）

题目：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1428先按开始时间排序，可以想象有一些教室（vector），然后有新活动举行，遍历vector看是否有教室活动结束，该教室活动结束就在这个教室举行活动，没有就新开教室举行活... 查看详情

51nod1243排船的问题（二分）

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1243题意： 思路：二分来做，每次贪心的把船安排到能安排的最左边即可。1#include<iostream>2#include<algorithm>3#include<cstring>4#include<cstdio> 查看详情

51nod1640mst+二分

...;51nod魔法学校近日开展了主题为“天气晴朗”的魔法交流活动。 N名魔法师按阵法站好 查看详情

51nod1299监狱逃离

...。在各个交点中有M个点住着犯人(M<=N+1)，剩下的点可以安排警卫，有警卫把守的地方犯人无法通过。给出整个监狱的道路情况，以及犯人所在的位置，问至少需要安排多少个警卫，才能保证没有1个犯人能够逃到出口，如果总 查看详情

51nod1640天气晴朗的魔法

...法学校近日开展了主题为“天气晴朗”的魔法交流活动。 N名魔法师按阵法站好，之后选取N-1条魔法链将所有魔法师的魔力连接起来，形成一个魔法阵。  查看详情

51nod1299监狱逃离

...。在各个交点中有M个点住着犯人(M<=N+1)，剩下的点可以安排警卫，有警卫把守的地方犯人无法通过。给出整个监狱的道路情况 查看详情

贪心入门——活动安排问题

贪心入门的几个例题来自51nod问题描述　　有若干个活动，第i个开始时间和结束时间是[Si,fi)，只有一个教室，活动之间不能交叠，求最多安排多少个活动？输入第1行：1个数N，线段的数量(2<=N<=10000)第2-N+1行：每行2个数，线... 查看详情

51nod1002数塔取数问题

 Input示例458 43 6 97 2 9 5Output示例28  查看详情

51nod1640天气晴朗的魔法（最小生成树）

...法学校近日开展了主题为“天气晴朗”的魔法交流活动。 N名魔法师按阵法站好，之后选取N-1条魔法链将所有魔法师的魔力连接起来，形成一个魔法阵。 魔法链是 查看详情

活动安排问题

 1428 活动安排问题基准时间限制：1 秒空间限制：131072 KB分值: 10 难度：2级算法题 收藏 关注有若干个活动，第i个开始时间和结束时间是[Si,fi)，同一个教室安排的活动之间不能交叠，求要安排所有... 查看详情

51nod-01085背包问题

【算法】背包DP【题解】f[j]=(f[j-w[i]]+v[i])记得倒序(一个物品只能取一次)#include<cstdio>#include<algorithm>#include<cstring>usingnamespacestd;constintmaxn=10010;intn,W,w[maxn],v[maxn],f[maxn];intmain(){scan 查看详情

51nod1394差和问题

我只会用线段树写。。。不喜欢树状数组。。其实跑的也不算慢？然后各种*的时候忘了longlong一直WA。。。药丸！而且我不怎么会用map离散化。。。那么就sort+unique#include<cstdio>#include<cstring>#include<cctype>#include<algorit... 查看详情

[51nod1597]有限背包计数问题

[51nod1597]有限背包计数问题试题描述你有一个大小为n的背包，你有n种物品，第i种物品的大小为i，且有i个，求装满这个背包的方案数有多少两种方案不同当且仅当存在至少一个数i满足第i种物品使用的数量不同输入第一行一个正... 查看详情

51nod1086背包问题v2

我都快不会写二进制优化多重背包了。。。卡了一下常数从rank100+到20+。。。#include<cstdio>#include<cstring>#include<cctype>#include<algorithm>usingnamespacestd;#definerep(i,s,t)for(inti=s;i<=t;i++)#definedw 查看详情

51nod1100(计算几何)

...文题啦～ 思路：算斜率不用多说吧？本题唯一一个小问题是数据量是1e4，Ｏ(n^2)可能超时，我们可以用个小技巧来解决这个问题；对这些点用x坐标排序，斜率最大的点一定是排序后相邻的两个点。上述结论的正确性我们不难... 查看详情

51nod1002数塔取数问题

1#include<cstdio>2#include<algorithm>3#defineMAXN5104usingnamespacestd;5intf[MAXN][MAXN],dp[MAXN][MAXN];//数字塔数组和dp数组6intmain(){7intn;8scanf("%d",&n);9for(inti=1;i<=n;i++){//循环输入数字塔1 查看详情

51nod1158单调栈　个人的想法以及分析

...度，但是使用姿势难以想到。在51nod1158中描述了这样一个问题：　给定一个0-1矩阵，　求这个矩阵最大的全1子矩阵的面积。问题十分好理解。　现在，我们将这个问题拆分成一些子问题来逐个击破。首先，为了保证程序操作的... 查看详情

51nod1083矩阵取数问题|动态规划

   #include"bits/stdc++.h"usingnamespacestd;#defineLLlonglong#defineINF0x3f3f3f3f3f#definePIacos(-1)#defineN510#defineMOD10usingnamespacestd;intarr[N+1][N+1],dp[N+1][N+1];intmain(){intn 查看详情