18
2016-09
2016-09
HDU 5884 Sort (二分+队列)
题目链接:点我~~
题意:n个有序序列的归并排序.每次可以选择不超过k个序列进行合并,合并代价为这些序列的长度和.总的合并代价不能超过T, 问k最小是多少。
思路:先对所有数排序,另外一个队列维护合并后的值,取值时从两个序列前端取小的即可。如果(n−1)mod(k−1)≠0,要把最小的(n−1)%(k−1)+1个数先合并一下。剩下的恰好可以每次合并k个数
#...
09月18日
2,831
20
2016-07
2016-07
HDU 5726 GCD (RMQ+二分)
题目链接:点我~~
题意:给你n个数,m个询问,每次询问某个区间,求这段区间所有数的gcd,然后问1~n所有连续区间中gcd的值等于区间所有数gcd的个数~~
思路:对于求区间gcd可以用线段树维护,或者RMQ,因为后者的查询是O(1)~还是比较方便的。对于所有区间的gcd,考虑枚举左端点,二分区间进行预处理~例如12467,以1为左端点,1~5为右端点5个...
07月20日
2,265
20
2016-07
2016-07
HDU 5289 Assignment (RMQ+二分)
题意:求存在最大差值小于给定K值的区间段个数。
思路:利用RMQ求出区间最大最小值,再枚举右端点,二分区间找到满足要求的最大区间累加~~
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
t...
07月20日
2,245