Summary
今天的题目也不算很难，唯一一道没做出来的题目是以前做过的，太不应该了。
Problem
T1 油滴扩展
题目大意
给你一堆点，你准备要在这么多的点当中滴油。你可以自己安排顺序，每次滴油，呈圆形扩散，知道碰到别的油或者边框。
想法
因为点的数目很小，可以直接暴力枚举顺序。可以用两点距离减去已有半径得出现有半径。
T2 数列
题目大意
给你一堆数，你可以删去其中某些数，使得下标和数相同的数最多。
想法
显然可以用DP
设f[i,j]表示当前选到了i这个数，前面删去了j个数
那么可以考虑删除当前的数
f[i,j]=f[i-1,j]
也可以考虑不删除当前的数
f[i,j]=f[i-1,j-1]+p
其中p表示当前数是否符合题目条件，是的话为1，反之为0
T3 软件开发
题目大意
有两个软件，每个软件分成m个模块，有n个工人，给出他们完成第一个软件，第二个软件的各个模块的天数，问最少多少天可以弄完。
想法
显然暴力可以设f[i,j,k]表示选到第i个，完成A，B软件模块个数分别为i,j。显然可以O(nm4)暴力来做
显然超时
我们可以二分天数，再用这个DP去判断，那么你只要枚举当前这个选A软件模块个数即可，选B的模块个数可以通过总天数减去A软件花费的天数。
也有更好的方法。
如果用一个数组去表示状态，显然浪费
我们设f[i,j]表示选到i个，完成A软件模块个数为j，其B软件能完成的最多个数。
显然，我们枚举一个当前选A软件模块个数，那么B软件模块个数同样求得出来。转移即可，方程如下
f[i,j]=f[i-1,j-k]+p
p是B软件能完成的个数，通过计算得出。
T4 黑匣子
题目大意
每次插入一个数到一个有序的序列中，让你求第k大
想法
可以维护两个堆，一个大根堆和一个小根堆
GET：i加1，然后输出Blackhox中第i小的数”
如果GET操作不是按顺序询问，而是随机询问，那么平衡树自然是首选。但是GET操作是按顺序询问的，平衡树未免有点大材小用…….
所以，我们建立两个堆，一个小根堆hmin，一个大根堆hmax。一开始读入数据时，将数据加入hmin。进行GET操作时，输出hmin的堆顶，并将其移入hmax。
这样，hmax中存有的，就是当前黑箱中最小的i个数。当最新读入的数x比hmax的堆顶y要小时，说明x在新黑箱最小的i个数之中，相当于y的位置就被x挤掉了。那么就将y移回hmin。若x比y要大，则将x加入hmin。
这种双堆的技巧，也适用于求多个连续区间的中位数。
同样可以用线段树和权值线段树来做，先全部排序，模拟插入过程，根据个数来判断第k大即可。