题目链接:249. 蒲公英 算法分析 进阶指南上算法描述已经很清晰了。这里是用vector维护的每个数在序列中出现的下标。假设总共T块,预处理出每两个块之间的最小众数,需要时间O(nT)。m个查询小块内每个数的出现次数为O(mn/T*logn),总体时间复杂度为两者之和。 根据均值不等式,如果时间复杂度最低,应满足 n T = m n / T l o g n nT=mn/Tlogn nT=m
比赛链接:http://codeforces.com/contest/435 A. Queue on Bus Stop time limit per test:1 second memory limit per test:256 megabytes It's that time of the year when the Russians flood