LeetCode周赛334，我还以为是状态恢复了，没想到是题变简单了……

class Solution {
public:
    vector<int> leftRigthDifference(vector<int>& nums) {
        int n = nums.size();
        int lef[n+1], rig[n+1];
        memset(lef, 0, sizeof lef);
        memset(rig, 0, sizeof rig);
        
        lef[0] = nums[0];
        for (int i = 1; i < n; i++) {
            lef[i] = lef[i-1] + nums[i];
        }
        
        rig[n-1] = nums[n-1];
        for (int i = n-2; i > -1; i--) {
            rig[i] = rig[i+1] + nums[i];
        }
        
        vector<int> ret;
        for (int i = 0; i < n; i++) {
            ret.push_back(abs(lef[i] - rig[i]));
        }
        return ret;
    }
};

class Solution {
public:
    vector<int> divisibilityArray(string word, int m) {
        vector<int> ret;
        
        int n = word.length();
        long long md = 0;
            
        for (int i = 0; i < n; i++) {
            // word[i] - '0'，即将字符数字转成int
            // 加入一个新的数字，即md * 10再加上末尾数字
            md = (md * 10 + word[i] - '0') % m;
            ret.push_back(md % m == 0);
        }
        return ret;
    }
};

class Solution {
public:
    int maxNumOfMarkedIndices(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        
        int l = 0, r = n/2 + 1;
        while (l+1 < r) {
            int m = (l + r) >> 1;
            bool flag = true;
            for (int i = 0; i < m; i++) {
                if (2 * nums[i] > nums[n-m+i]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                l = m;
            }else {
                r = m;
            }
        } 
        return l * 2;
    }
};

class Solution {
public:
    int minimumTime(vector<vector<int>>& grid) {
        // 定义缩写
        typedef pair<int, int> pii;
        typedef pair<int, pair<int, int>> piii;
        
        priority_queue<piii> que;
        que.push({0, {0, 0}});
        
        // 方向数组
        int dr[4][2]{{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
        int n = grid.size()-1, m = grid[0].size()-1;
        
        // 判断无解的情况
        if (grid[0][1] > 1 && grid[1][0] > 1) return -1;
        
        // 记录每个点到达的最小时间
        vector<vector<int>> dis(n+3, vector<int>(m+3, -1));
        
        dis[0][0] = 0;
        
        
        while (!que.empty()) {
            piii f = que.top();
            que.pop();
            // 由于优先队列默认是优先级高的在前，所以要取反，这样就成了距离短的在前了，也可以定义优先队列的优先级，不过稍微麻烦一些，直接取反比较简单
            int tt = -f.first;
            int xx = f.second.first;
            int yy = f.second.second;

            for (int i = 0; i < 4; i++) {
                int x = xx + dr[i][0];
                int y = yy + dr[i][1];
                int t = tt + 1;
                
                // 如果越界或者已经访问过了，则跳过
                if (x < 0 || x > n || y < 0 || y > m || dis[x][y] >= 0) continue;
                
                // 根据奇偶性计算到达的最小时间
                int nxt;
                if (t > grid[x][y]) nxt = t;
                else nxt = grid[x][y] + (grid[x][y] + t) % 2;
                
                // 记录，入队列
                dis[x][y] = nxt;
                que.push({-nxt, {x, y}});
            }
        }
        
        return dis[n][m];
    }
};