LYK有n个小伙伴。每个小伙伴有一个身高hi。
这个游戏是这样的，LYK生活的环境是以身高为美的环境，因此在这里的每个人都羡慕比自己身高高的人，而每个人都有一个属性ai表示它对身高的羡慕值。
这n个小伙伴站成一列，我们用hi来表示它的身高，用ai来表示它的财富。
每个人向它的两边望去，在左边找到一个最近的比自己高的人，然后将ai朵玫瑰给那个人，在右边也找到一个最近的比自己高的人，再将ai朵玫瑰给那个人。当然如果没有比自己身高高的人就不需要赠送别人玫瑰了。也就是说一个人会给0,1,2个人玫瑰（这取决于两边是否有比自己高的人）。
每个人都会得到若干朵玫瑰（可能是0朵），LYK想知道得了最多的玫瑰的那个人得了多少玫瑰。(然后嫁给他>3<)
输入格式(treasure.in)
第一行一个数n表示有n个人。
接下来n行，每行两个数hi,ai。
输出格式(treasure.out)
一个数表示答案。
输入样例
3
47
35
610
输出样例
12
样例解释
第一个人会收到5朵玫瑰，第二个没人送他玫瑰，第三个人会收到12朵玫瑰。
数据范围
对于50%的数据n<=1000,hi<=1000000000。
对于另外20%的数据n<=50000，hi<=10。
对于100%的数据1<=n<=50000,1<=hi<=1000000000。1<=ai<=10000。
这道题从某种程度上来说是道一眼题。因为一眼就能看出O(n^2)的做法。但作为一个有追求的人，我还是认真的思考了一下有没有O(n)的办法，毕竟O(n^2)估计不能A。但后来也没想出来，所以就……嗯。
我的代码（没想到竟然拿满了，大概是数据有点弱）：
1#include
1#include 正方形(square) 在一个10000*10000的二维平面上，有n颗糖果。 LYK喜欢吃糖果！并且它给自己立了规定，一定要吃其中的至少C颗糖果！ 事与愿违，LYK只被允许圈出一个正方形，它只能吃在正方形里面的糖果。并且它需要支付正方形边长的价钱。 LYK为了满足自己的求食欲，它不得不花钱来圈一个正方形，但它想花的钱尽可能少，你能帮帮它吗？ 输入格式(square.in) 第一行两个数C和n。 接下来n行，每行两个数xi,yi表示糖果的坐标。 输出格式(square.out) 34 21 41 52 4 选择左上角在(1,1)，右下角在(4,4)的正方形，边长为4。 对于30%的数据n<=10。 对于50%的数据n<=50。 对于80%的数据n<=300。 对于100%的数据n<=1000。1<=xi,yi<=10000。 我就是两两的枚举端点，然后用这两个端点扩出一个最小的正方形，之后搜一遍里面有多少点。如果点数够了，就与当前的ans比较，保留小的。但是只过了两个点，其他的都结果错误。可能是因为我默认正方形的左上角（或右上角）有一颗糖框住，但其实不一定。 我的代码： 1.正方形的上、下、左、右一定有和糖果贴在一起的。不然会浪费。 因此我们可以枚举上下左，之后找一个合适的右边。最后再把这个长方形扩成正方形。 ------------------------------插播：离散化--------------------------- 1Structnode{intx,y;}t[10005];2Incmp(nodeI,nodej){i.y 离散前：3315 离散后：2213 由此可见，离散化的作用是缩小空间。正好适用于这道题（由原来的10000*10000变为n*n的大小，二维空间大大缩小） --------------------------------插播结束-------------------------------- 算法改进：枚举上边和下边。左边为1的情况下，右边是什么随着左边向右移动，右边也一定向右移动。 左边至多移动n次，右边也至多移动n次，总共2n次 O（n^3） 继续改进： 我们发现，本题答案是连续的。即，如果边长为x可行，边长为x+1也可行（至少覆盖C个糖果）；假如x不可行，x-1也不可行。 由此可知，我们可以二分答案。 L,r判断mid是否可行--->正常的二分 之后， 枚举上边在哪里，下边的位置是固定的。哪些糖果被夹在这段区间中O(n) 再之后 左边为1的情况下，右边是什么 随着左边向右移动，右边也一定向右移动。 左边至多移动n次，右边也至多移动n次，总共2n次O(n) P.s:也可以用前缀和来做 标程： 1#include 追逐(chase) 这次，LYK以一个上帝视角在看豹子赛跑。 在一条无线长的跑道上，有n只豹子站在原点。第i只豹子将在第ti个时刻开始奔跑，它的速度是vi/时刻。 因此在不同的时刻，这n只豹子可能在不同的位置，并且它们两两之间的距离也将发生变化。 LYK觉得眼光八方太累了，因此它想找这么一个时刻，使得最远的两只豹子的距离尽可能近，当然这不能是第0时刻或者第0.01时刻。它想知道的是最迟出发的豹子出发的那一刻开始，离得最远的两只豹子在距离最小的时候这个距离是多少。 当然这个时刻不仅仅可能发生在整数时刻，也就是说可能在1.2345时刻这个距离最小。 输入格式(chase.in) 第一行一个数n。 接下来n行，每行两个数分别是ti和vi。 输出格式(chase.out) 输出一个数表示答案，你只需保留小数点后两位有效数字就可以了。 14 25 37 0.33 在第5+2/3这个时刻，第一只豹子在18+2/3这个位置，第二只豹子在18+1/3这个位置，第三只豹子在18+2/3这个位置，最远的两只豹子相距1/3的距离，因此答案是0.33。 对于20%的数据n=2。 对于20%的数据n=3 对于60%的数据n<=100。 对于80%的数据n<=1000。 对于100%的数据n<=100000，1<=vi,ti<=100000。 这道题本来是弃了，后来发现20%还是很好写的。然后就写了一下。结果迷之运行时错误。（所以代码就不放了） 正解思路： 假如一条直线代表一只豹砸 可以分别描出每一时刻离原点最近和最远的豹砸 绿色部分就是他们的差，题目要求找的就是最短的绿线。 60分算法:求出所有交点，然后再求每只豹砸 排除掉跑得慢又跑的晚的豹子后，我们发现斜率大的豹子占据右边一段 用单调栈实现 如图，三条斜率不同的线段最后的上凸壳是紫色部分。也就是说，在这种情况下，每遇到一个交点上凸壳方向就会改变。 下凸壳同理：对于两只豹子，一只跑得慢且后跑，一只跑得快一开始就跑。我们保留前面那只。 上凸壳流程： 标程（可以说是很可怕了）： 图论 ——算法简单，难点在于构图 l竞赛图：任意两个人（点）打一场比赛，由赢的向输的连一条边。 l邻接表的实现： cin>>u>>v;(u->v) f[u][++f[u][0]]=v; f[u][0]表示u连出去能到几个点 f[u][i]表示u连出去第i个点是啥 l邻接表的好处：在遍历一个点能连向哪些点时，复杂度是出度，而不是O(n) l邻接矩阵的好处：判断一条边是否存在，查询一条边的权值，复杂度是O(1) l边表（前向星）： cin>>u>>v; o++; e[o]=v;(u->v)之前u还指向过一些点head[u]来表示起点为u的边编号最大的那个编号是多少 next[o]=head[o]当u处理完连向v的这条边之后，下一次处理的边编号是多少 head[u]=o; 便利u为起点，能连向哪些点 For(inti=head[u];i!=0;) l拓扑排序 给定一张拓扑图，求1号点走到n号点的方案总数 令dp[i]表示从1号点走到i号点的方案总数 有dp[i]=xigma(dp[j])(j->i) 枚举i时，按照拓扑序进行枚举 Dp[n]就是答案 l最短路 （1）令dis[i]表示当前u到i的最短路是多少。 （2）将dis[u]=0,dis[i]=inf(i!=u)。 （3）寻找最小的dis[x]且x曾经没被找到过。 （4）若x=v，输出答案并退出。 （5）枚举x的所有边，用dis[x]去更新其余dis[]，回到步骤②。 使用范围：不存在负权边。 2.SPFA（poj1502） l并查集 一行并查集(实现了路径压缩)： Intgetf(intx){returnf[x]=xf[x]:f[x]=getf(f[x]);}//不断找father l最小生成树 1.Prim：一开始随便找一个点当做集合中点，每次找一条最短的边，要求这条边链接的两个点，一个在集合中，一个不在集合中。把连接的另一个点和这条边加入到集合中。 2.kruskal：对边权进行排序，每次加入后判断是否存在环，若不存在环，则加入（并查集实现） l二分图（不存在奇环，即有奇数个点的环） 二分图染色：（col[i]=1->i这个点染成黑色col[i]=2->i这个点染成白色col[i]=0->i这个点还未被染色） Vector Voiddfs(intx,inty) { Col[x]=y; For(inti=0;i If(!col[v[x][i]])dfs(v[x][i],3-y); If(col[v[x][i]]==col[x])FLAG=true;//如果一条边连接的两个点是同一种颜色，这是不被允许的（判定方法1） } For(inti=1;i<=n;i++)col[i]=0; For(inti=1;i<=n;i++)if(!col[i])dfs(i,1); if(FLAG)cout<<’no’;elsecout<<’yes’; 二分图判定方法2： [图例解释]标记完成后，若发现2与2`连通了，则不是二分图（奇环） 可通过染色来理解，会出现矛盾 For(inti=1;i<=n;i++)p[i][0]=++cnt,p[i][1]=++cnt; For(inti=2;i<=cnt;i++)f[i]=I; For(inti=1;i<=m;i++) u-v f[getf(p[u][0])]=getf(p[v][1]); f[getf(p[u][1])=getf(p[v][0]); if(getf(p[u][0])==getf(p[u][1])||getf(p[v][0])==getf(p[v][1]))FLAG=true;