工作安排价值最大、判断凸边形、二叉树的括号表示法

    //选择工作安排使得收益最大化问题
    /
    类似 任务调度的题 ，例如 P2949 [USACO09OPEN]Work Scheduling G
    首先所有项目按照时间排序，使用堆（优先队列）管理已选的项目，把获利最小的项目放在堆顶，然后如果已选的项目数量
    （也可以当作已经消耗的时间）和当前比较的项目的时间更短，证明可以直接选择项目（加入堆），否则判断当前项目和堆顶
    项目谁的获利更大，更大的就加入其中。
    /

    1. struct Job {
    2.         int t;
    3.         int w;
    4.         Job(int tt, int tw) : t(tt), w(tw) {};
    5.         bool operator<(const Job& other) const {//小顶堆
    6.             return w > other.w;
    7.         }
    8.     };
    10.     bool t_cmp(const Job& g1, const Job& g2) {
    11.         return g1.t < g2.t;// 按ddl排序
    12.     }
    14.     LL max_value_Jobs(const vector<Job>& all) {
    15.         LL ret = 0;
    16.         priority_queue<Job> take;
    17.         for(int i = 0; i < all.size(); i++) {
    18.             if(all[i].t <= take.size()) {
    19.                 if(take.top().w < all[i].w) {
    20.                     ret = ret - take.top().w * 2 + all[i].w;//这里不选择是减分，所以是减去双倍的分值
    21.                     take.pop();
    22.                     take.push(all[i]);
    23.                 }
    24.             } else {
    25.                 ret += all[i].w;
    26.                 take.push(all[i]);
    27.             }
    28.         }
    29.         return ret;
    30.     }

    / 判断是不是一个凸多边形
    tip: 对于边AB BC 如果C在边的同一侧 则这个点满足凸多边形，即沿着边绕多边形一圈，总是往一个方向拐弯的是多边形。
    /

    1.     struct Point {
    2.         double x, y;
    3.         Point(double tx, double ty) : x(tx), y(ty) {};
    4.     };
    6.     double get_side(Point* p1, Point* p2, Point* p3) {
    7.         double x1, x2, y1, y2;
    8.         x1 = p3->x - p1->x;
    9.         x2 = p2->x - p1->x;
    10.         y1 = p3->y - p1->y;
    11.         y2 = p2->y - p1->y;
    12.         return (x1 * y2 - x2 * y1);
    13.     }
    15.     bool is_porly(const vector<Point*>& ps) {
    16.         for(int i = 0; i < ps.size(); i++) {
    17.             double res = 0;
    18.             int count = 0;
    19.             Point* pi = ps[i], *pj;
    20.             int j;
    21.             if(i == ps.size() - 1) {
    22.                 pj = ps[0];
    23.                 j = 0;
    24.             } else {
    25.                 pj = ps[i + 1];
    26.                 j = i + 1;
    27.             }
    28.             for(int k = 0; k < ps.size(); k++) {
    29.                 if(k == i || k == j) continue;
    30.                 Point* pk = ps[k];
    31.                 double side = get_side(pi, pj, pk);
    32.                 if(count == 0) {
    33.                     res = side;
    34.                 } else if(res * side < 0) {
    35.                     return false;
    36.                 }
    37.                 count++;
    38.             }
    39.         }
    40.         return true;
    41.     }

    //给一个由先序遍历序列化的 二叉树（字符串）,由它反序列重建二叉树，比如“A(B(D,),C(,E))”
    /
    主要思路是 ‘（ ‘ 前面的就是根节点，之后的话，使用栈来处理’（’ ‘）’符号，当栈里面只有一个 ‘（’ 并且当前字符是 ‘ ,’，
    就可以拆分成左右两个子树，然后递归处理即可，记得处理好叶子节点的情况，叶子节点没有’(‘和’)’
    /

    TreeNode* rebuildTree(const string& s, int left, int right){
       if(left>right) return nullptr;
       stack<char> stk;
       string val;
       while(left<=right&&s[left]!='('){
           val+=s[left];left++;
       }
       TreeNode* root=new TreeNode(val);
        for(int i=left;i<=right;++i){
            if(s[i]=='('){
                stk.push(s[i]);
            }else if(s[i]==')'&&stk.size()>1){
                stk.pop();
            }else if(s[i]==','&&stk.size()==1){
                root->left=rebuildTree(s,left+1,i-1);
                root->right=rebuildTree(s,i+1,right-1);
            }
        }
        return root;
   }