XUPT_ACM week2 Greedy+dp+STL

贪心

定义

贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

平时购物找零钱时，为使找回的零钱的硬币数最少，不要求找零钱的所有方案，而是从最大面值的币种开始，按递减的顺序考虑各面额，先尽量用大面值的面额，当不足大面值时才去考虑下一个较小面值，这就是贪心算法

使用条件

  • 贪心选择性质
    一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次的选择可以依赖以前作出的选择，但 不依赖于后面要作出的选择 。这就是贪心选择性质。
  • 最优子结构性质
    当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。在实际应用中，至于什么问题具有什么样的贪心选择性质是不确定的，需要具体问题具体分析。

解题过程

解题的一般步骤是：

  1. 建立数学模型来描述问题；
  2. 把求解的问题分成若干个子问题；
  3. 对每一子问题求解，得到子问题的局部最优解；
  4. 把子问题的局部最优解合成原来问题的一个解。

缺点

  1. 不能保证解是最佳的。因为贪心算法总是从局部出发，并没从整体考虑；
  2. 贪心算法一般用来解决求最大或最小解。

例题

  • 新生赛：Time management（小植哥哥南京站打比赛做多能做几个题）

    已知主办方一共出了N道题，多人运动队计划每道题在 S i S_i Si​时刻开始做，在 E i E_i Ei​时刻做完，一次只能同时做一道题。比赛结束后，他们最多能过多少题呢？

  • 原题：[USACO09DEC]Selfish Grazing S

    Each of Farmer John’s N ( 1 ≤ N ≤ 50 , 000 ) N (1 \leq N \leq 50,000) N(1≤N≤50,000) cows likes to graze in a certain part of the pasture, which can be thought of as a large one-dimeensional number line. Cow i’s favorite grazing range starts at location S_i and ends at location E i ( 1 ≤ S i < E i ; S i < E i ≤ 100 , 000 , 000 ) E_i (1 \leq S_i < E_i; S_i < E_i \leq 100,000,000) Ei​(1≤Si​<Ei​;Si​<Ei​≤100,000,000).
    Most folks know the cows are quite selfish; no cow wants to share any of its grazing area with another. Thus, two cows i and j can only graze at the same time if either S i ≥ E j S_i \geq E_j Si​≥Ej​ or E i ≤ S j E_i \leq S_j Ei​≤Sj​. FJ would like to know the maximum number of cows that can graze at the same time for a given set of cows and their preferences.
    Consider a set of 5 cows with ranges shown below:

    These ranges represent (2, 4), (1, 12), (4, 5), (7, 10), and (7, 8), respectively.
    For a solution, the first, third, and fourth (or fifth) cows can all graze at the same time. If the second cow grazed, no other cows could graze. Also, the fourth and fifth cows cannot graze together, so it is impossible for four or more cows to graze.
    约翰有 N ( 1 ≤ N ≤ 50000 ) N(1≤N≤50000) N(1≤N≤50000)头牛，约翰的草地可以认为是一条直线．每只牛只喜欢在某个特定的范围内吃草．第i头牛喜欢在区间 ( S i ， E i ) (S_i，E_i) (Si​，Ei​)吃草， 1 ≤ S i < E i ≤ 1 , 000 , 000 , 00 1≤S_i<E_i≤1,000,000,00 1≤Si​<Ei​≤1,000,000,00.
    奶牛们都很自私，他们不喜欢和其他奶牛共享自己喜欢吃草的领域，因此约翰要保证任意
    两头牛都不会共享他们喜欢吃草昀领域．如果奶牛i和奶牛J想要同时吃草，那么要满足： S i ≥ E j S_i\geq E_j Si​≥Ej​或者 E i ≤ S j E_i\leq S_j Ei​≤Sj​．约翰想知道在同一时刻，最多可以有多少头奶牛同时吃草？

这道题在《算法导论》里叫做活动选择问题。

  • 活动选择问题
    问题是调度竞争共享资源的多个活动，目标是选出一个最大的互相兼容的活动集合。
    假定有 n n n个活动的集合 S = { a 1 , a 2 , . . . , a n } S=\{a_1,a_2,...,a_n\} S={a1​,a2​,...,an​}。这些活动使用同一资源，并且在同一时刻只能供一个活动使用。每个活动 a i a_i ai​都会有一个开始时间 s i s_i si​ 和一个结束时间 f i f_i fi​ ，其中 0 ≤ s i ≤ < f i < ∞ 0\leq s_i\leq<f_i<\infty 0≤si​≤<fi​<∞。选中某活动，该活动发生在 [ s i , f i ) [s_i,f_i) [si​,fi​)若有两个活动无重叠时间段，则称他们为兼容的。我们希望选出一个最大兼容活动集

这个问题还可以再变：

一个数轴上有n条线段，选取其中a条线段使得这a条线段都不重合，求最大的a

解题思路：按照右端点排个序（只有右端点才会对后续时间有影响），然后依次贪心往进放就可。

#include<iostream>
#include<algorithm>
using namespace std;
struct moo
{
	int x,y;
}cow[500005];
bool comp(moo a,moo b)
{
	return a.y<b.y;
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>cow[i].x>>cow[i].y;
	sort(cow+1,cow+n+1,comp);
	int r=0,ans=0;
	for(int i=1;i<=n;i++)
		if(cow[i].x>=r)
		{
			ans++;
			r=cow[i].y;
		}
	cout<<ans;
	return 0;
}

动态规划

基本思想

全局最优解如果可以由子问题的最优解推导得到，则可以先求解子问题的最优解，再构造原问题的最优解；若子问题有较多的重复出现，则可以自底向上从最终子问题向原问题逐步求解。

分类

从一道题认识动态规划：数字三角形

给出一个数字三角形，从顶部到底部有很多路径，求路径最大和。
输入：
第一行一个n，表示共有几行
后面n行，数字三角形。
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出：一个整数答案
30

dfs

从起点开始，向下进行递归求当前点最大值，每一步只能走(x+1,y+1)或(x+1,y)，终止条件为递归到第n行。

#include<stdio.h>
int n;
int a[10][10];
int MAX(int x,int y)
{
	return x>y?x:y;
}
int dfs(int x,int y)//<algorithm>
{
	if(x==n)return a[x][y];
	return a[x][y]+MAX(dfs(x+1,y+1),dfs(x+1,y));
}
int main()
{
	freopen("in.txt","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++)
			scanf("%d",&a[i][j]);
	printf("%d",dfs(1,1));
	return 0;
}

记忆化dfs

在朴素的递归中有大量重复的运算，把重复运算的结果记录下来，能够有效提高效率

#include<stdio.h>
int n;
int a[10][10];
int b[10][10];//存中间重复计算值 
int MAX(int x,int y)
{
	return x>y?x:y;
}
int dfs(int x,int y)//max -> <algorithm>
{
	if(x==n)return a[x][y];
	if(b[x][y])return b[x][y];
	return b[x][y]=a[x][y]+MAX(dfs(x+1,y+1),dfs(x+1,y));
}
int main()
{
	freopen("in.txt","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++)
			scanf("%d",&a[i][j]);
	printf("%d",dfs(1,1));
	return 0;
}

dp

实际上每一次递归都是改变现有题目规格，使规模不断变小，分而治之。分析递归实际的过程会发现本质上其实程序在执行一个从下到上递推的过程。利用数组来描述这个递推的过程，也就是所谓动态规划。中间用来计算递推状态的公式就叫做状态转移方程。

#include<stdio.h>
int n;
int a[10][10];
int f[10][10];
int MAX(int x,int y)
{
	return x>y?x:y;
}
int main()
{
	freopen("in.txt","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++)
			scanf("%d",&a[i][j]);
	
	for(int i=n;i;i--)
		for(int j=1;j<=i;j++)
			f[i][j]=MAX(f[i+1][j+1],f[i+1][j])+a[i][j];
	printf("%d",f[1][1]);
	return 0;
}

做题思路

  1. 分解成若干子问题；
  2. 确定状态转移方程，考虑怎么样从上一个状态变换成下一个状态
  3. 确定边界条件

题目特点

  • 问题具有最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质。
  • 无后效性
    每个状态都是过去历史的一个完整总结。它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。

背包问题

一种组合优化的NP完全问题（多项式复杂程度的非确定性问题）。

P：多项式时间内能解决的判定问题。
NP：所有的非确定性多项式时间可解的判定问题
NPC：NP完全问题。这些问题中任何一个如果存在多项式时间的算法,那么所有NP问题都是多项式时间可解的.这些问题被称为NP-完全问题(TSP)

给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。
也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？
它是在1978年由Merkle和Hellman提出的。
背包问题深入研究强烈安利《背包九讲》（马：6666）。
b站acwing yxc讲背包九讲

01背包

  • 题面

    有 N N N 件物品和一个容量为 V V V 的背包。放入第 i i i 件物品耗费的费用是 C i C_i Ci​，得到的价值是 W i W_i Wi​。求解将哪些物品装入背包可使价值总和最大。

  • 特点
    每个物品只有一件，放或者不放
  • 状态转移方程： f [ i , v ] f[i,v] f[i,v]表示 i i i 个物品， v v v 个容量 的最大价值是 f f f。
    f [ i , v ] = m a x {   f [ i − 1 , v ]   ,   f [ i − 1 , v − C i ] + W i   } f[i,v] = max\{~f[i-1, v]~,~ f[i-1, v-C_i] + W_i~\} f[i,v]=max{ f[i−1,v] , f[i−1,v−Ci​]+Wi​ }

基本上所有跟背包相关的问题的方程都是由它衍生出来的。

  • 若只考虑第 i i i 件物品的策略（放或不放），那么就可以转化为一个只和前 i − 1 i-1 i−1 件物品相关的问题。
  • 如果不放第 i i i 件物品，那么问题就转化为“前 i − 1 i-1 i−1 件物品放入容量为 v v v 的背包中”，价值为 F [ i − 1 , v ] F[i-1, v] F[i−1,v]
  • 如果放第 i i i 件物品，那么问题就转化为“前 i − 1 i-1 i−1 件物品放入容量为 v − C i v-C_i v−Ci​ 的背包中”，此时能获得的最大价值就是 F [ i − 1 , v − C i ] F[i-1, v-C_i] F[i−1,v−Ci​] 再加上通过放入第 i i i 件物品获得的价值 W i W_i Wi​。
  • 优化：时空复杂度为 O ( V N ) O(VN) O(VN)，稍加优化可以将空间复杂度降到 O ( V ) O(V) O(V)

补充：关于时间复杂

常见的的复杂度比较： O ( 1 ) < O ( log ⁡ n ) < O ( n ) < O ( n l o g n ) < O ( n 2 ) < O ( n 3 ) < O ( 2 n ) < O ( 3 n ) < O ( n ! ) O(1) < O(\log n) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(3^n) < O(n!) O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(3n)<O(n!)

例题：[NOIP2005 普及组] 采药

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

代码：纯裸的01背包问题

#include<iostream>
using namespace std;
int A[120][22000],T[120],V[120];
int main()
{
	int t,m;
	cin>>t>>m;
	for(int i=1;i<=m;i++)
		scanf("%d%d",&T[i],&V[i]);
	for(int i=1;i<=m;i++)
		for(int j=1;j<=t;j++)
			if(j>=T[i])
				A[i][j]=max(A[i-1][j],A[i-1][j-T[i]]+V[i]);
			else
				A[i][j]=A[i-1][j];
	cout<<A[m][t];
	return 0;
}

从C到C++

对于像ACM这种对时间要求高的编程竞赛，相对于其他语言来说，更适合用c++去写程序。c++相比较来说有着丰富的函数库。封装了大量现成的模板，算法。有可以拿来直接用的STL。并且不论是实现时间还是运行时间都要比现场手写的效果好。

输入输出

与c的scanf和printf不同，c++使用iosteam来进行输入输出。

#include<iostream>
using namespace std;
int main()
{
	int n;
	cin>>n;
	cout<<n<<endl;
	return 0;
}

c++使用一个全面的标准库来提供IO机制。cin,cout操作就包含在iostream头文件里，在预处理部分首先引用iostream库，该库包含了两个基础类型istream和ostream，分别表示输入流和输出流。“流”表示从IO设备读出或写入的字符序列。
标准库定义了4种IO对象，另外的两个为cerr和clog，通常用cerr输出警告和错误信息，用clog输出程序运行时信息。混合使用cout,cerr,clog时，程序会将他们写在同一个窗口里。
注意，c++头文件不带.h后缀。在c++里使用c的头文件时，前面加c后面去掉.h，具体如下：

#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>

endl是个操纵符(manipulator)，效果就像\n结束当前行，并将与设备关联的缓冲区(buffer)刷新到设备中。刷新缓冲可以保证当前所有的输出真正写到输出流中，而不是在设备中等待写入流。
>>，<<分别为输入和输出运算符。可以利用输入输出运算符进行连续输出和输入，比如这样：

#include<iostream>
using namespace std;
int main()
{
	int n,m;
	cin>>n>>m;
	cout<<n+m<<' '<<n-m<<endl;
	return 0;
}

可以进行根据变量类型自动匹配，比如这样：

#include<iostream> 
using namespace std;
int main()
{
	int n;
	double m;
	cin>>n>>m;
	cout<<n<<' '<<m<<endl;
	return 0;
}

可以加常量字符串，比如这样：

#include<iostream> 
using namespace std;
int main()
{
	int n;
	double m;
	cin>>n>>m;
	cout<<"刚刚输入的整数是"<<n<<"，刚刚输入的浮点数是"<<m<<endl;
	return 0;
}

是不是肥肠滴银杏。
同时cin,cout是被定义在std命名空间里的。如果不加using会是这个样子

#include<iostream>
int main()
{
	int n;
	std::cin>>n;
	std::cout<<n<<std::endl;
	return 0;
}

其中::为作用域操作符，编译器从他左侧的作用域中找右边的名字。如果使用using声明可以在引用名空间成员时不必使用名空间限定符::。
但是其实精通C++后都不建议写using namespace std;这句话。完整一点说应该是“尽量不扩大using namespace xxx所影响到的域”，也就是说不要在头文件里用这句话。《c++ primer》里作者在第三章3.1命名空间的using声明p75页提到：

头文件的内容会拷贝到所有引用他的文件中去……对于某些程序来说，由于不经意间包含了一些名字，反而可能产生始料未及的名字冲突。

《C++ Primer Plus》在第九章:内存模型和名称空间 第329页提到

一般说来，使用using命令比使用using编译命令更安全，这是由于它只导入了制定的名称。如果该名称与局部名称发生冲突，编译器将发出指示。using编译命令导入所有的名称，包括可能并不需要的名称。如果与局部名称发生冲突，则局部名称将覆盖名称空间版本，而编译器并不会发出警告。另外，名称空间的开放性意味着名称空间的名称可能分散在多个地方，这使得难以准确知道添加了哪些名称。

目前如果只是些算法竞赛的话就什么都不管把这句话每次都写上就可以，不会出现什么问题。

输入输出速度分析

众所周知cin比scanf慢的不是一点，原因是cin与stdin总是保持同步的，也就是说这两种方法可以混用，同时cout和stdout也一样，两者混用不会输出顺序错乱。正因为这个兼容性的特性，导致cin有许多额外的开销，实际上可以用sync_with_stdio(false);关闭同步流（但有的时候还是会玄学速度）。
但是还有选手对这样的速度还是不满意，所以他们直接用快读来输入输出，原理就是先一直读入字符直到出现数字，再一直读入数字同时累乘直到读入的不是数字。优化核心在于getchar的速度很快。

inline int redn() {
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}

输出优化同理，但是单纯的输出优化还没printf快，就不用骚操作了。
还有选手用fread优化，fread直接快到飞起啊。原理就是让fread一次性读入大量数据，再让getchar直接调用内存，如果刚开始读的不够多那就再调用fread读入数据，直到文件的末尾。
附一个luogu神仙用iostream底层的streambuf操作的基于streambuf的IO优化
实际上，正常的比赛好好的灵活运用cin,cout,scanf,printf就够了。。。

内联函数

内联函数(inline)可以避免函数调用的开销。并且只是向编译器发出一个请求，编译器可以自己选择是否忽略掉这个请求。
一般内联用于优化规模小的，流程直接，频繁调用的函数。并且很多编译器都不支持内联用于递归。

STL标准模板库

标准模板库（Standard Template Library）是惠普实验室开发的一系列软件的统称。被容纳于C++标准程序库（C++ Standard Library）中是标准库的核心，是一个泛型(generic)程序库。STL的代码从广义上讲分为三类：algorithm（算法）、container（容器）和iterator（迭代器），几乎所有的代码都采用了模板类和模板函数的方式。

概述

在C++标准中，STL被组织为下面的13个头文件：

#include<algorithm>
#include<deque>
#include<functional>
#include<iterator>
#include<vector>
#include<list>
#include<map>
#include<memory>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<utility>

[这段看不懂就算了，想看懂了到时候深入研究一下c++吧]STL的一个重要特点是数据结构和算法的分离。这种分离确实使得STL变得非常通用。例如，由于STL的sort()函数是完全通用的，你可以用它来操作几乎任何数据集合，包括链表，容器和数组；另一个重要特性是它不是面向对象的。为了具有足够通用性，STL主要依赖于模板，在STL中找不到任何明显的类继承关系，这使得STL的组件具有广泛通用性的底层特征。另外，由于STL是基于模板，内联函数的使用使得生成的代码短小高效。从逻辑层次来看，在STL中体现了泛型化程序设计的思想，引入了诸多新的名词，比如像需求（requirements），概念（concept），模型（model），容器（container），算法（algorithmn），迭代子（iterator）等。与OOP（object-oriented programming）中的多态（polymorphism）一样，泛型也是一种软件的复用技术；从实现层次看，整个STL是以一种类型参数化的方式实现的。

容器

容器用来管理某类对象。简单的理解容器，它就是一些模板类的集合，但和普通模板类不同的是，容器中封装的是组织数据的方法（也就是数据结构）。说白了容器就是存放数据的东西，再傻瓜点的理解就是容器就像数组一样。
STL提供了关联式，顺序式和特殊容器，容器适配器。容器适配器是容器配接，也就是利用请其实现出来的结构叫容器适配器。

字符串

string是可变长字符序列（就是字符串…），定义如下：

namespace std
{
	template<class T,//字符所属型别,ASCII,Unicode...
		class traits=char_traits<charT>,//traits class，提供字符串核心操作，
		 class Allocator=allocator<charT> >//内存模型
	class basic_string;
	typedef basic_string<char> string;
	typedef basic_string<wchar_t> wstring;//宽字符，像Unicode
}

string支持用下标访问。
string可以用length()或者size()来返回string::size_type类型的大小。
关于string的更多见我的另一篇关于string的总结

  • 例题
动态数组

vector是一个能够存放任意类型的动态数组。在<vector>定义如下：

namespace std
{
	template <class T,//元素型别
			  class Allocator=allocator<T> >//内存的模型，默认使用allocator
	class vector;
}

初始化方法：

vector<T> v1;//定义了一个能装T类型(ElementType)的空v1
vector<T> v2(v1)；//v2是v1副本
vector<T> v2=v1;//同上
vector<T> v3(n,val);//v3里有n个val
vector<T> v4(n);//v4有n个空位置
vector<T> v5{a,b,c};//赋初值a,b,c
vector<T> v5={a,b,c};//同上

vector支持随机存取，并且支持类似数组操作，所以可以在常数时间内存取任意元素。：

array[i]=num;
array.at(i)=num;

以上两句话等效，并且后者还会在数组越界时抛出异常。但是只能对已知确定存在的元素进行访问操作！不能对空容器操作，不能用下标形式添加元素！通过下标访问不存在元素会产生缓冲区溢出(buffer overflow)。
vector在末端操作时非常快，但是在中间或者前面就慢了，是因为前面或中间操作的话，后面的元素都要随着动，每次一动都要调assignment(赋值)操作符。
vector可以通过size()返回目前有多少元素，可以用capacity()返回当前容器容量。当容器容量等于元素数量，也就是size()==capacity()，即容器已满时，vector会进行扩容。扩容并非简单的在容器尾部申请空间然后存储新的元素，而是会申请一个新的空间，然后把原有的元素拷贝过去，再释放掉原有的空间。容器整体搬家了！ 所以在扩容后之前的所有迭代器都失效了。
一般vector扩容会申请比原来容量多一倍的空间，devcpp就是如此，但vs2019增加了4。2倍扩容时间复杂度更优，可以保证时间复杂度 O ( n ) O(n) O(n) ，而1.5倍扩容时，空间可重用，各有利弊。

  • 例题
栈

先手写一个栈实现三个功能：入栈，查询栈顶，出栈。

#include<iostream>
#define STACK_SIZE 5
using namespace std;
int s[STACK_SIZE];
int top;
inline void s_push(int val)
{
	if(top<STACK_SIZE-1)s[++top]=val;
	else cerr<<"stack over flow"<<endl;
}
inline int s_top()
{
	return s[top];
}
inline void s_pop()
{
	if(top)top--;
	else cerr<<"stack under flow"<<endl;
}
inline int s_size()
{
	return top;
}
inline bool s_empty()
{
	return top==0;
}
int main()
{
	int n;//n个操作 
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int op,num;
		cin>>op;
		if(op==1)//入栈
		{
			cin>>num;
			s_push(num);
		}
		if(op==2)cout<<"top: "<<s_top()<<endl;//查询栈顶 
		if(op==3)s_pop();//出栈
		if(op==4)cout<<"size: "<<s_size()<<endl;
		if(op==5)cout<<"empty:"<<(s_empty()?"true":"false")<<endl;
	} 
	return 0;
}

STL提供了栈的容器适配器，核心接口是三个成员函数push(),top(),pop()，还有size()和empty()两个常用接口;

在头文件<stack>中，class stack定义如下：

namespace std
{
	template <class T,//元素型别
			  class Container=deque<T> >//所使用的容器，缺省采用deque，不选用vector是因为deque移除元素后会释放内存
	class stack;
}

声明这么写：

std::stack<int>st;//用了using就不用写std作用域

如果要换个序列式容器来实现stack，就可以这么整，比如说vector：

stack<int,vector<int> >st;

把刚刚手写的栈用STL重新实现：

#include<iostream>
#include<stack>
using namespace std;
stack<int>s;
int main()
{
	int n;
	cin>>n;
	while(n--)
	{
		int op,num;
		cin>>op;
		if(op==1)
		{
			cin>>num;
			s.push(num);
		}
		if(op==2)cout<<"top: "<<s.top()<<endl;
		if(op==3)s.pop();
		if(op==4)cout<<"size: "<<s.size()<<endl;
		if(op==5)cout<<"empty:"<<(s.empty()?"true":"false")<<endl;
	}
	return 0;
}
队列

先手写一个队列

#include<iostream>
#define QUEUE_SIZE 100005
using namespace std;
int q[QUEUE_SIZE];
int front,back;
inline void q_push(int val)
{
	if((front+1)%QUEUE_SIZE!=back)
	{
		front=(front+1)%QUEUE_SIZE;
		q[front]=val;
	}
	else cerr<<"queue over flow"<<endl;
}
inline bool q_empty()
{
	return back==front?true:false;
}
inline void q_pop()
{
	if(!q_empty())back=(back+1)%QUEUE_SIZE;
	else cerr<<"queue under flow"<<endl;
}
inline int q_front()
{
	return q[front];
}
inline int q_back()
{
	return q[(back+1)%QUEUE_SIZE];
}
inline int q_size()
{
	return (front-back+QUEUE_SIZE)%QUEUE_SIZE;
}
int main()
{
	int n;
	cin>>n;
	while(n--)
	{
		int op,num;
		cin>>op;
		if(op==1)
		{
			cin>>num;
			q_push(num);
		}
		if(op==2)cout<<"back: "<<q_back()<<endl;
		if(op==3)cout<<"front: "<<q_front()<<endl;
		if(op==4)q_pop();
		if(op==5)cout<<"size: "<<q_size()<<endl;
		if(op==6)cout<<"empty: "<<(q_empty()?"true":"false")<<endl;
	}
	return 0;
}

STL提供了队列的容器适配器，与这里手写的不同的是，STL将后入队列元素放到了back，先出从front。

在头文件<queue>中，class queue定义如下：

namespace std
{
	template <class T,//元素型别
		  class Container=deque<T> >//所使用的容器，缺省采用deque
	class queue;
}

声明这么写：

queue<string>q;

同样如果要换个序列式容器来实现queue，就可以这么整，比如说list：

stack<int,list<int> >st;

把刚刚手写的队列用STL重新实现：

#include<iostream>
#include<queue>
using namespace std;
queue<int>q;
int main()
{
	int n;
	cin>>n;
	while(n--)
	{
		int op,num;
		cin>>op;
		if(op==1)
		{
			cin>>num;
			q.push(num);
		}
		if(op==2)cout<<"back: "<<q.back()<<endl;
		if(op==3)cout<<"front: "<<q.front()<<endl;
		if(op==4)q.pop();
		if(op==5)cout<<"size: "<<q.size()<<endl;
		if(op==6)cout<<"empty: "<<(q.empty()?"true":"false")<<endl;
	}
	return 0;
}
优先队列

普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest out）的行为特征。通常采用堆数据结构来实现。
堆是一颗完全二叉树，堆中的某个父结点的值总是大于等于（最大堆）或小于等于（最小堆）其孩子结点的值，每个结点的子树都是堆树，一般操作进行一次的时间复杂度在O(1)~O(logn)之间。常见的堆有二叉堆、斐波那契堆等。
堆中核心操作在于上浮和下沉：

  • 在堆中插入新元素时，将新元素放在尾部，然后向上逐步上浮；
  • 在堆中弹出优先级最高的根结点元素时，让根节点元素和尾节点进行交换，然后让现在的根元素下沉就可以了。

安利博客：基本数据结构――堆的基本概念及其操作
啊哈算法中有堆的模拟的代码

#include <stdio.h>
int h[ 101];//用来存放堆的数组
int n;//用来存储堆中元素的个数，也就是堆的大小


//交换函数，用来交换堆中的两个元素的值
void swap(int x,int y)
{
    int t;
    t=h[ x];
    h[ x]=h[ y];
    h[ y]=t;
}


//向下调整函数
void siftdown(int i) //传入一个需要向下调整的结点编号i，这里传入1，即从堆的顶点开始向下调整
{
    int t,flag=0;//flag用来标记是否需要继续向下调整
    //当i结点有儿子的时候（其实是至少有左儿子的情况下）并且有需要继续调整的时候循环窒执行
    while( i*2<=n && flag==0 )
    {        
        //首先判断他和他左儿子的关系，并用t记录值较小的结点编号
        if( h[ i] > h[ i*2] )
            t=i*2;
        else
            t=i;
        //如果他有右儿子的情况下，再对右儿子进行讨论
        if(i*2+1 <= n)
        {
            //如果右儿子的值更小，更新较小的结点编号  
            if(h[ t] > h[ i*2+1])
                t=i*2+1;
        }
        //如果发现最小的结点编号不是自己，说明子结点中有比父结点更小的  
        if(t!=i)
        {
            swap(t,i);//交换它们，注意swap函数需要自己来写
            i=t;//更新i为刚才与它交换的儿子结点的编号，便于接下来继续向下调整
        }
        else
            flag=1;//则否说明当前的父结点已经比两个子结点都要小了，不需要在进行调整了
    }
}


//建立堆的函数
void creat()
{
    int i;
    //从最后一个非叶结点到第1个结点依次进行向上调整
    for(i=n/2;i>=1;i--)
    {
        siftdown(i);
    }  
}


//删除最大的元素
int deletemax()
{
    int t;
    t=h[ 1];//用一个临时变量记录堆顶点的值
    h[ 1]=h[ n];//将堆得最后一个点赋值到堆顶
    n--;//堆的元素减少1
    siftdown(1);//向下调整
    return t;//返回之前记录的堆得顶点的最大值
}


int main()
{
    int i,num;
    //读入数的个数
    scanf("%d",&num);


    for(i=1;i<=num;i++)
        scanf("%d",&h[ i]);
    n=num;   

    //建堆
    creat();

    //删除顶部元素，连续删除n次，其实夜就是从大到小把数输出来
    for(i=1;i<=num;i++)
        printf("%d ",deletemax());

    getchar();
    getchar();
    return 0;
}

  • 例：TJOI2010 中位数

    给定一个由N个元素组成的整数序列，现在有两种操作：
    1 add a
    在该序列的最后添加一个整数a，组成长度为N + 1的整数序列
    2 mid 输出当前序列的中位数
    例1：1 2 13 14 15 16 中位数为13
    例2：1 3 5 7 10 11 17 中位数为7
    例3：1 1 1 2 3 中位数为1

    有人用主席树，堆，线段树，splay，fhq treap，tarjan 的Zip tree，还有暴力。这道题也可以用两个堆来维护中位数。
    将所有数先放到大根堆里去，然后取一半再放到小根堆。这样就是有序的两部分。add时取小根堆顶和add数比较大于堆顶加入小根堆，否则加入大根堆（维护有序）
    mid时为了保证大根堆顶就是答案，就应该控制让大根堆里的元素为(all+1)>>1，从小根堆那里多退少补，最后直接输出大根堆顶就行。
    代码如下：

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
priority_q<int,vector<int>,greater<int> >q1;//xiao
priority_q<int,vector<int>,less<int> >q2;//da
string s;
int cnt1,cnt2;
int main()
{
	int n,m;
	cin>>n;
	for(int i=1; i<=n; i++)
	{
		int a;
		cin>>a;
		q2.push(a);
		cnt2++;
	}
	for(int i=1; i<=n/2; i++)
	{
		int x=q2.top();
		q2.pop();
		cnt2--;
		q1.push(x);
		cnt1++;
	}
	cin>>m;
	for(int i=1; i<=m; i++)
	{
		cin>>s;
		if(s[0]=='a')
		{
			int x;
			cin>>x;
			n++;
			int l=q2.top();
			if(x>l)q1.push(x),cnt1++;
			else q2.push(x),cnt2++;
		}
		else
		{
			while(cnt2<((n+1)>>1))
			{
				int x=q1.top();
				q1.pop();
				cnt1--;
				q2.push(x);
				cnt2++;
			}
			while(cnt2>((n+1)>>1))
			{
				int x=q2.top();
				q2.pop();
				cnt2--;
				q1.push(x);
				cnt1++;
			}
			if(cnt2==((n+1)>>1))
				cout<<q2.top()<<endl;
		}
	}
	return 0;
}

迭代器

类似于指针，迭代器也提供了对象的间接访问。使用迭代器可以访问某元素，也能从一个元素移动到另一个元素。和指针一样，迭代器也分为有效和无效之分。
和指针的区别在于，获取迭代器不是使用的取地址，有迭代器的类型同时拥有返回迭代器的成员。

算法


标准库定义了一组泛型算法，称之为“泛型”是因为：实现了经典算法的公共接口，不光标准库类型，甚至数组之类的都可以用。
大多算法定义在<algorithm>里，其中也包含了许多辅助函数：max(),min(),swap()等等，是不是肥肠滴银杏。

排序

对于排序来说，时间效率是最重要的，所以STL提供了多个排序算法，最常用的就是sort()
sort内部采用快排的思想，保证了平均性能，复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)，但最差情况也有可能降到 O ( n 2 ) O(n^2) O(n2)。准确来书它实际采用Introspective Sorting(内省式排序)，数据量大时用快排，一旦分段后的数据量小于某个门坎，为避免快排的递归调用带来过大的额外负荷，就改用插排。如果递归层次过深，还会改用堆排。所以手写快排时，哪怕是尾递归式的快排也不会有它快。（意思就是绝对比你自己手写的快排要快，如果你写的比sort还要快，那你就可以当新的STL了(doge)）。
sort的写法有两种形式：

//sort(beg,end):
int a[100]={0,5,4,2,3,8,6,9,7,8,6};
sort(a+1,a+10+1);
/
//sort(beg,end,comp:
bool comp(int a,int b)
{
	return a>b;//从大到小顺序排列
}
int main()
{
int a[100]={0,5,4,2,3,8,6,9,7,8,6};
sort(a+1,a+10+1,comp;
}
# 算法
Logo
向您推荐>>Eolink开发者社区

权威｜前沿｜技术｜干货｜国内首个API全生命周期开发者社区

更多推荐

沃云统一开发平台介绍

沃云集成平台研发平台介绍1.平台优势2.平台原理3.研发平台使用方法4.遇到的问题5.现阶段实现的功能6.后续需要补充的功能和优化内容研发平台介绍1.平台优势解决孤岛式应用，实现能力共享；现有系统框架过于复杂，跨系统业务处理成本居高不下，协同服务共享，降低运维成本；提高项目应用资源监控能力，改善资源利用率；业务微服务化，快速发布、快速部署，快速响应业务需求变化；沃云平台不仅提供了自动化的、可快速部

avatar 云原生

(20200916 Solved)docker-compose up创建容器自动退出

问题描述如题，创建容器后自动退出了。并且docker start container无效解决方案原因是缺失了控制终端的配置，需要在docker-compose.yml中增加tty:true ，有时候这样也不行，需要再增加一个command:/bin/bash，命令不一定是这个，需要是一个不会退出的命令，然后用-d后台启动容器。Referencesdocker-compose启动容器后自动退出...

avatar 云原生

基于docker的test-containers环境百宝箱

笔者语录： 我开了个公众号【Java你我他】，欢迎大家关注。  在很多时候，程序猿们更关注代码本身，而不愿意把时间花费在环境搭建上，这也是Docker变得越来越受欢迎的原因之一。test-containe是Docker生态圈中的一颗新星，其 主要针对测试领域、背靠Docker实现环境百宝箱功能。  test-containers： 你要的环境，我都有~  假设我们现在需要一个redis-clust

avatar 云原生