首页 > ACM题库 > 九度OJ > 九度-1463-招聘会[解题代码]
2013
12-13

九度-1463-招聘会[解题代码]

题目来源:算法之美(面试算法每日一题系列)

题目描述:

又到毕业季,很多大公司来学校招聘,招聘会分散在不同时间段,小明想知道自己最多能完整的参加多少个招聘会(参加一个招聘会的时候不能中断或离开)。

输入:

第一行n,有n个招聘会,接下来n行每行两个整数表示起止时间,由从招聘会第一天0点开始的小时数表示。
n <= 1000 。

输出:

最多参加的招聘会个数。

样例输入:
3
9 10
10 20
8 15
样例输出:
2

cpp 代码如下:
#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
int n;
struct Node {
	int s, e;
} nodes[1001];
bool cmp(const Node & n1, const Node & n2) {
	return n1.e < n2.e;
}
int opt[1001];
int main() {
	while(cin >> n) {
		for(int i=0; i<n; i++) {
			cin >> nodes[i].s >> nodes[i].e;
			opt[i] = 0;
		}
		sort(nodes, nodes+n, cmp);
		opt[0] = 1;
		for(int i=1; i<n; i++) {
			for(int j=i-1; j>=0; j--) {
				if(nodes[i].s >= nodes[j].e) {
					opt[i] = opt[j]+1;
					break;
				}
			}
			if(opt[i] < opt[i-1]) {
				opt[i] = opt[i-1];
				nodes[i].e = nodes[i-1].e;
			}
		}
		cout << opt[n-1] << endl;
	}

	return 0;
}
/**************************************************************
	Problem: 1463
	User: coder
	Language: C++
	Result: Accepted
	Time:10 ms
	Memory:1532 kb
****************************************************************/


  1. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  3. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

  4. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

  5. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.