可以用堆来实现,或者更简单一点的优先队列
优先队列:
#include
priority_queue,greater > q;
因为每次合并后,最小的两个值都会更新,所以可以很好的利用优先队列内元素有序的特点,减少因反复排序带来的时间复杂度;
一开始我用STL自带的排序sort,报了5个TLE,后来意识到sort的实现主要依赖于快速排序,而每次合并后,真正需要排序的元素只有一个,快速排序有点大材小用,所以这可能是爆时限的原因,但后来也没有尝试自己实现一个排序算法,改用优先队列实现,直接AC,很好的利用了优先队列中元素有序的特点。
下面是代码实现:
#include
#include
#includ服务器托管网e
#include
#include
using namespace std;
bool compare(long long int x,long long int y) {
return x ans;
priority_queue, greater >q;
int main(void) {
cin >> n;
ans.reserve(n);
for (i = 0; i > element;
q.emplace(element);
}
while (q.size()!=1) {
sum = q.top();
q.pop();
sum += q.top();//因为优先队列无法访问指定下标元素,所以我选择先加一个,再删掉后再加上去
ans.push_back(sum);//然后将答案存入数组中,作为一次合并数据
q.pop();
q.emplace(sum);//随后直接插入合并后的数据,利用优先队列的特点,再次排序
}
for (int i = 0; i
服务器托管,北京服务器托管,服务器租服务器托管网用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net
# char(10) 换行符 char(13) 回车符号 select * from view_nichtware_wms_inventory where DESCRIPTION like concat(‘%’,char(10),’%’) and SKU=’D…