丁丁的博客

MySQL所有数据库空间量计算： ``` select concat(truncate(sum(data_length)/1024/1024,2),' MB') as data_size from information_schema.tables; ``` 按照数据库分组计算： ``` select TABLE_NAME, concat(truncate(data_length/1024/1024,2),' MB') as data_size, concat(truncate(index_length/1024/1024,2),' MB') as index_size from information_schema.tables where TABLE_SCHEMA = 'TestDB' group by TABLE_NAME order by data_length desc; ```

Win10系统和Win8系统安装msi安装程序时，有时候会提示安装失败，报错： `The error code is 2503` 或者 `The error code is 2502` 这是由于权限不够的原因，可能是一个bug 解决这个问题的方式是用管理员进入CMD，并进入msi文件所在的目录，执行： ``` msiexec /package xxx.msi ``` 即可。

通过这道题，可以很好的学习和练习使用C++STL库中queue和pair的使用。
之前一直使用纯粹的C，有需要的地方就自己使用struct写链表等数据结构，因此排序、极值、哈希搜索等操作不仅写起来费事，而且效率不高，这一题彻底让我从之前纯粹使用C的方式转换成了使用C++和STL。
题目地址：http://codevs.cn/problem/5126/
关于优先队列priority_queue和pair，可以参考下面两篇比较全面的介绍：
优先队列priority_queue 详解
C++中pair的用法
值得注意的是，pair不光做好了泛型，还做了operator<的实现，因此可以默认通过priority_queue进行最大堆的操作，而不需要自己写比较函数。

解题思路：

构建数据结构，distance距离位置，和value疲劳值。
将所有数据分为两个序列，左部lq和右部rq，分割点就在当前推销员所在的坐标位置（一开始坐标点在0点处），动态维护其坐标的变化。左部序列是一个大顶堆的优先队列，初始时为空；右部元素不必单独开辟，直接使用左边界哨兵控制区域位置即可。

每次对左部和右部的最大值进行对比：

• 如果左部最大值大一些，则此时选择左部元素（推销员已走过的房间），将左部元素的value值输出，并弹出这个元素。
• 如果右部最大值大一些，则此时选择右部元素（推销员还没到过的坐标），将右部元素的(distance - nowDis) * 2 + value值输出，同时记录目标元素的distance值，并将右部元素中所有小于等于此distance值的节点全部压入左部队列，压入权值为每个元素的value值。

寻找最大值的方法：

• 左部元素寻找最大值的方法：直接使用优先队列的特性，lq的top元素。

• 右部元素寻找最大值的方法：在rq中依次遍历，寻找最大的(distance - nowDis) * 2 + value值

直到左部和右部序列全部为空，解题结束。

实际编码中，我并没有每次对比左部和右部的最大值，而是在开始时将右部元素全部整理压入左部队列，然后将左部队列依次输出即可。整理和压入的方法是：寻找到右部(distance - nowDis) * 2 + value最大值后，将目标元素以(distance - nowDis) * 2 + value权值入栈，其余distance小于等于目标元素distance的节点以value值入栈。这样程序显得简洁一点。

代码：

/**
  * NOIP2015 推销员
  * 学习使用pair泛型进行组合，而不需要自己写struct
  * 学习使用priority_queue优先队列（默认为最大堆）
  */
#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

int main()
{
    //freopen("C:\\Users\\Administrator\\Desktop\\salesman\\salesman4.in","r",stdin);
    //freopen("C:\\Users\\Administrator\\Desktop\\salesman\\salesman4-dd.out","w",stdout);
    int N;
    scanf("%d", &N);
    pair<int, int> nodes[N];
    for(int i = 0; i < N; i++){
        scanf("%d", &nodes[i].second);      //读入dis数据
    }
    for(int i = 0; i < N; i++){
        scanf("%d", &nodes[i].first);       //读入value数据
    }

    priority_queue< pair<int, int> > lq;    //左部优先队列

    int nowPos = 0, nowDis = 0, nowResult = 0, tempPos, tempMXPos, tempResult, tempMXResult;

    //将nowPos不断向N逼近，迫使右部数据全部进入左部队列，最后整体输出左部队列
    while(nowPos < N){
        //找到本次登记的最大result和最大dis
        tempMXResult = 0;
        for(tempPos = nowPos; tempPos < N; tempPos++){
            tempResult = (nodes[tempPos].second - nowDis) * 2 + nodes[tempPos].first;
            if( tempResult >= tempMXResult ){
                tempMXResult = tempResult;
                tempMXPos = tempPos;
            }
        }
        nowDis = nodes[tempMXPos].second;
        //tempMXPos的权值为tempMXResult，其余小于nowDis的右部元素权值为first，将这些元素全部压入优先队列lq中
        for(tempPos = nowPos; nodes[tempPos].second <= nowDis && tempPos < N; tempPos++){
            if(tempPos == tempMXPos){
                nodes[tempPos].first = tempMXResult;
            }
            lq.push(nodes[tempPos]);
        }
        nowPos = tempPos;
    }

    while(!lq.empty()){
        nowResult += lq.top().first;
        printf("%d\n", nowResult);
        lq.pop();
    }

    return 0;
}