数据结构 - xIao_wU 思维磁场 - Just Run And Never Forget I Have A Dream

TOJ -- 1788. Raising Modulo Numbers

阅读全文

PKU 1990 -- MooFest 树状数组

    题目要求在一个横轴上,求出每个点和相对距离 * max( 声音1 , 声音2) ,直接模拟着做的话,复杂度为O(n ^ 2) ,必定超时。

    二元集的题目可使用排序来进行有序化操作,由于两个集合的操作是取最大的声音,故可以对v进行升序操作。for(int i=0; i < n;  i++)的时候,去声音值为v[i]即可。

    而现在主要解决在轴的位置上。对一个点进行操作的时候,可分为坐标前的点和坐标后的点,若坐标前点的个数为 n1 , 总和为 sum1 , 坐标后的点的个数为 n2 , 总和为 sum2 ,则 相对距离和 = (该点的坐标值 *  n1) - sum1 + sum2 - (该点坐标值 * n2)。 对坐标总和和位置前后的坐标总数,都可以适用树状数组在O(lgn)的时间来进行动态统计。每次加入点,更新树状数组即可。

继续阅读




Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee