finished 1025 贪心+二分的方法

/* *
2、题目大意

有2n个城市，其中有n个富有的城市，n个贫穷的城市，其中富有的城市只在一种资源富有，且富有的城市之间富有的资源都不相同，贫穷的城市只有一种资源贫穷，且各不相同，现在给出一部分贫穷城市的需求，每个需求都是一个贫穷的向一个富有的城市要资源，且每个富有的城市都想向贫穷的城市输入自己富有的那部分资源，现在为了运输要建设多条路，但是路与路之间不允许有交叉，求满足贫穷城市的各种要求最多可以建设多少条路
3、解题思路：
将贫穷的城市按从小到大的顺序排列，然后求富有的城市序号的最大上升子序列LIS解决即可
* */
/*
动态规划求解思路分析：（O(n^2)）
经典的O(n^2)的动态规划算法，设A[i]表示序列中的第i个数，F[i]表示从1到i这一段中以i结尾的最长上升子序列的长度，初始时设F[i]
= 0(i = 1, 2, ..., len(A))。则有动态规划方程：F[i] = max{1, F[j] + 1} (j = 1, 2,
..., i - 1, 且A[j] < A[i])。

贪心+二分查找：（O(nlogn)）
开辟一个栈，每次取栈顶元素s和读到的元素a做比较，如果a>s，  则加入栈；如果a<s，则二分查找栈中的比a大的第1个数，并替换。
最后序列长度为栈的长度。
这也是很好理解的，对x和y，如果x<y且E[y]<E[x],用E[x]替换  E[y],此时的最长序列长度没有改变但序列Q的''潜力''增大。

举例：原序列为1，5，8，3，6，7
栈为1，5，8，此时读到3，则用3替换5，得到栈中元素为1，3，8，  再读6，用6替换8，得到1，3，6，再读7，得到最终栈为1，3，6，7
，最长递增子序列为长度4。

用贪心+二分的方法很容易模拟出来，需要注意的就是二分的写法，而且需要输出最长上升子序列时，直接输出栈中的元素就行了。
*
* */
int binsearch(int *a, int l, int r, int val)
{
int mid;
while (l <= r)
{
mid = (l + r) >> 1;
if (val < a[mid])
r = mid - 1;
else if (val > a[mid])
l = mid + 1;
else
return mid;
}
return l;
}
//处理部分
t = 1;                    //t标记数组最后一个元素的下一位置，起始为1
for (i = 1; i <= n; ++i)
{
val = a[i];
if (val > s[t-1])
s[t++] = val;
else
s[binsearch(s, 1, t - 1, val)] = val;
}