http://acm.hdu.edu.cn/showproblem.php?pid=1025
很难说清楚,自己模拟几下就会慢慢明白,模板题
求的是最长递增子序列的长度
#include <iostream>
#include <algorithm>
#include <string>
//#include <map>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
//#include <ctime>
#include <ctype.h>
using namespace std;
#define LL __int64
#define inf 0x3fffffff
#define M 500005
int v[M];
int main()
{
int n, i, tv, x, cc = 1, top;
while (~scanf ("%d", &n))
{
memset (v, 0, sizeof(v));
for (i = 0; i < n; i++)
{
scanf ("%d%d", &x, &tv);
v[x-1] = tv;
}
/********************模板********************/
top = 0;
for (i = 0; i < n; i++)
{
int *p = lower_bound (v, v+top, v[i]);
if (p - v == top)
++top;
*p = v[i];
}
/********************模板********************/
printf ("Case %d:\n", cc++);
if (top <= 1)
printf ("My king, at most %d road can be built.\n\n", top);
else
printf ("My king, at most %d roads can be built.\n\n", top);
}
return 0;
}
分享到:
相关推荐
输入序列,求最长上升子序列的长度,算法复杂度nlgn
最长单调递增子序列,运行时间为O(nlgn),为算法导论上的算法
电路布线问题求解的改进算法 O(nlgN)的算法 内有3个pdf 都是对同一问题的不同方面的描述及推广
解法1—O(N^2)解法 解法2—O(NlgN)解法 解法3—O(N)解法 可以直接在记事本运行
归并排序并不像快速排序那样最坏情况时间复杂度变成On2,归并排序最坏情况仍然是Onlgn,大家可以看看
算法导论第30章多项式乘法 FFT算法 复杂度O(nlgn)
快速排序是实际运用中用的最多的算法,虽然它在最坏的情况下会达到n^2,但它的平均性能非常好,期望时间复杂度为nlgn,而且隐含的常数因子非常小,并且是原址排序。 快速排序原理:从一组数中任意选出一个数,将...
结论:归并排序和堆排序维持O(nlgn)的复杂度,速率差不多,表现优异。固定基准的快排表现很是优秀。而通过使用一个循环完成按增量分组后的直接插入的希尔排序,测试效果显著。 冒泡,选择,直接插入都很慢,而冒泡...
(3)若n较大,则应采用时间复杂度为O(nlgn)的排序方法:快速排序、堆排序或归并排序。 快速排序是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短; 堆排序所...
基于比较的排序算法: 下界是 nlgn 1.1 SelectionSort:每次选出最下的元素,放在当前循环最左边的位置。 1.2 BubbleSort:每次比较相邻的两个数,使得最大的数像气泡一样冒到最右边。 1. 3 InsertionSort:每次拿起...
使用分治法在O(nlgn)复杂度内求出最近点对
算法课本的题目,要求复杂度是(nlgn)。
数据结构和算法 Repo 托管用于学习数据结构和算法的代码 数据结构 动态规划 [问题] [排序:易到难] :fire: :fire: :fire: :fire: :fire: :fire: :fire: :fire: :fire: :fire: 排序算法 - O (nlgn) - Θ (nlgn) - O ...
该资源是课程作业,其中包含程序和报告...从图二中我们可以看到,一组有序列的数组分别采用三种算法在运行时间上的差别出现了;最省时间的是随机基准快速排序算法,其次是随机化输入快速排序算法,最后是确定型算法;
使用C++编写的寻找最近点对算法,是基于机械工业出版社出版的《离散数学及其应用》中的叙述给出的实现,nlgn复杂度下求解最近的点对
摘要:在无向图上,对于任意源点一目的点点对,给出了一个新的k最短路算法.这一算法按长度递增给出k最短路路径 .算法的复 杂度 为 0 ( m+ nlgn+ ml
* 排序算法的分类如下: * 1.插入排序(直接插入排序、折半插入排序、希尔排序); * 2.交换排序(冒泡泡排序、快速排序)... * (3)若n较大,则应采用时间复杂度为O(nlgn)的排序方法:快速排序、堆排序或归并排序。
import java.util.Random; /** * 排序测试类 * * 排序算法的分类如下: * 1.... * 2.... * 3.... * 4.... * 5.... * (3)若n较大,则应采用时间复杂度为O(nlgn)的排序方法:快速排序、堆排序或归并排序。
快速排序是基于分治思想的原地排序的排序算法,将长度为N的数组排序所需时间和NlgN成正比,而且内循环比大多数排序算法都要短小和简单,因此一般情况比其他排序算法效率高。它的缺点是非常脆弱,某些情况可能导致它...
时间复杂度从O(n2)降低到了O(nlgn) 利用快速傅里叶变换FFT实现了大整数乘法。时间复杂度从O(n2)降低到了O(nlgn) 利用快速傅里叶变换FFT实现了大整数乘法。时间复杂度从O(n2)降低到了O(nlgn) 利用快速傅里叶...