落絮飞雁的个人网站

已知了最小费用流和最小割的性质，写写最大流的各种变体。 READ MORE →

最小传输费用问题

READ MORE →

题目描述：

有n项工作，每项工作分别在si时间开始，ti时间结束。对于每项工作，你都可以选择参加或不参加，但选择了参加某项工作就必须至始至终参加全程参与，即参与工作的时间段不能有重叠(即使开始的瞬间和结束的瞬间重叠也是不允许的)。

你的目标是参与尽可能多的工作，那么你最多能参与多少项工作呢？

限制条件：

1<=n<=100000

1<=si<=ti,=10^9

这个问题首先想到的就是贪心算法。但设计算法时容易出现错误。

比较容易想到的算法如：

• 在可选工作中，每次选取最先开始的工作
• 在可选工作中，每次选取用时最短的工作
• 在可选工作中，每次选取与最少可选工作有重叠的工作
• 在可选工作中，每次选取结束时间最早的工作

而很显然，前三项算法都不具有普适性（例如：一项开头早，持续时间长的工作和两项开头晚的工作）。

关于最后一种算法的解释：

结束时间早，对应的可选工作就越多。当然也可以用归纳法来证明。

代码实现：

#include 
#include 
#include 
#include 
using namespace std;

const int N = 5;
int s[N]={1,2,4,6,8};
int t[N]={3,5,7,9,10};

int solve()
{
pair itv[N];
for(int i = 0; i < N; i ++) {
itv[i].first = s[i];
itv[i].second = t[i];
}
sort(itv, itv + N);
int count = 0;
int t = 0;
for(int i = 0; i < N; i ++) {
if(t < itv[i].first) {
count ++;
t = itv[i].second;
}
}
return count;
}

int main() {
cout << solve() << endl;
return 0;
}

栈是支持push和pop的数据结构。

push是在栈的顶端放入一组数据；pop是在栈的顶端取出一组数据。

Last in first out(LIFO):最后进入栈的一组数据会被最先取出.

样例：

#include
#include
using namespace std;
int main()
{
	stack s;//声明int类型数据存储的栈
	s.push(1);//『』→『1』
	s.push(2);//『1』→『1,2』
	s.push(3);//『1,2』→『1,2,3』
	printf("%dn",s.top());//3
	s.pop();//栈顶移除3，下同
	printf("%dn",s.top());
	s.pop();
	printf("%dn",s.pop());
	s.pop();//『1』→『』
	return 0;
}

返回栈顶元素：

// test_stack.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include 
#include 
#include 
#include 

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	stack mystack;
	mystack.push(10);
	mystack.push(20);
	mystack.top()-=5;
	cout << "mystack.top() is now " << mystack.top() << endl;

	return 0;
}