CodeForces - 847B Preparing for Merge Sort 二分
http://codeforces.com/problemset/problem/847/B
题意：给你n个数（n<2e5)把它们分成若干组升序的子序列，一行输出一组。分的方法相当于不断找最长递增子序列，将它们删除，然后继续找，直到删光整个初始数列。
题解：第一直觉是开一个vector<int> n[maxn].每读取一个数x,if(x>v[i].back())v[i]。push_back(x);else v[++cnt].push_back(x).交了一发TLE了。然后分析一下，这样做保证了所有v[i].back()是个递减数列（否则那个不符和的可以push back到前面的vector后面。）本来的算法时间复杂度最坏O（n*n)。若用二分找到可以插入的vector，就能变成nlogn.然后就AC了。
二分查找用了pos=lower_bound(a+1,a+1+n,x)-a;这一步会找到a数组（所有vector的最后元素组成的数组）中第一个大于等于x的位置，pos--让pos变成最后一个小于x的位置，也就是应该插入的地方。
如果x比所有数都大（比如第一个元素），pos 就会先指到n+1,- - 后指到a数组的n位置,也就代表着第一个开始push_back的vector（所以输出时要反着输出）。
#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<string> #include<string.h> #include<stdio.h> #include<algorithm> #include<vector> using namespace std; const int maxn = 2e5 + 5; int a[maxn]; vector<int> v[maxn]; int main() { int n; int cnt = 0; cin >> n; for (int i = 1; i <= n; i++) { int x; scanf("%d", &x); int pos = lower_bound(a + 1, a + 1 + n, x)-a; pos--; a[pos] = x; v[pos].push_back(x); } for (int i = n; i>=1; i--) { for (int j = 0; j < v[i].size(); j++)printf("%d ",v[i][j]); cout << endl; } }
1、[USACO18DEC]Balance Beam
2、Leetcode 668.乘法表中第k小的数
3、大数据调度工具oozie详细介绍
4、html input 按钮
5、python自定义pi函数的代码