阿里笔试（更新到3.30）附全5场笔试代码

/*
 第1题：模拟，采用优先队列来执行整个过程，时间复杂度O(mlogn)
 首先构造优先队列（大顶堆），维护M次即可。
 注意：每次我们只需要维护队头元素，而不需要对所有元素都在每次循环中都更新数据
 每次队头元素出队，值改为（当前值-当前是第几天*每天的增长量）/2（实际上这个更新是相对大小的更新）
 */

#include<iostream>
#include<queue>
using namespace std;

int resud(priority_queue<int, vector<int>, less<int> > pq, int n, int m, int k) {
    int i, tmp;
    int res = 0;
    for(i = 0; i < m; i++) {
        tmp = (pq.top() - (i+1)*k);
        if(tmp < 0 && tmp%2 != 0) {
            tmp = tmp/2 - 1;
        }
        else {
            tmp = tmp/2;
        }
        pq.pop();
        pq.push(tmp);
    }
    
    for(i = 0; i < n; i++) {
        res = res + pq.top();
        pq.pop();
    }
    return res + n*m*k;
}

int main() {
    int n,m,k;
    cin>>n>>m>>k;
    priority_queue<int, vector<int>, less<int> > pq;
    
    int i;
    int tmp;
    
    for(i = 0; i < n; i++) {
        cin>>tmp;
        pq.push(tmp);
    }
    cout<<resud(pq, n, m, k)<<endl;
    return 0;
}

/*
问题转化为计算每个连续子串中的最大值，用栈的方法，时间、空间均O(n)复杂度
dp[i]:标明所有以v[i]为串尾的子串的最大值的和 （简单可知，dp[i]是i+1个子串最大值的和）
用栈来记录情况如下：
   对于v[i]，我们让栈元素依次弹出，直到找到比v[i]大的元素：
   如果栈空了，证明v[i]为串尾的所有串的最大值都是v[i]，所以dp[i] = (i+1)*v[i]；
   如果栈没空，假设此时栈顶元素对应v[j]，则对串k~i，如果k<=j，则这些串的最大值的和和dp[j]一致；
   如果k>j，则这些串的最大值为v[i]，加起来即可
串总数是(1+n)*n/2，只要把所有dp加起来除以总数就可以了
*/

#include<iostream>
#include<iomanip>
#include<stack>
#include<vector>
using namespace std;

struct prs {
    int val;
    int ord;
};

double calE (vector<int> v) {
    if(v.empty()) {
        return 0;
    }
    
    stack<prs> s;
    prs ptmp;
    ptmp.val = v[0];
    ptmp.ord = 0;
    s.push(ptmp);
    
    double dp[v.size()];
    dp[0] = v[0];
    int i;
    double res = v[0];
    
    for(i = 1; i < v.size(); i++) {
        while(!s.empty() && v[i] >= s.top().val) {
            s.pop();
        }
        if(s.empty()) {
            dp[i] = (i+1)*v[i];
        }
        else {
            dp[i] = (i - s.top().ord)*v[i] + dp[s.top().ord];
        }
        res = res + dp[i];
        
        ptmp.val = v[i];
        ptmp.ord = i;
        s.push(ptmp);
    }
    return res/double((v.size()+1)*v.size()/2);
}

int main() {
    int n;
    cin>>n;
    vector<int> v;
    
    int i, tmp;
    for(i = 0; i < n; i++) {
        cin>>tmp;
        v.push_back(tmp);
    }
    
    cout.setf(ios::fixed);
    cout<<fixed<<setprecision(6)<<calE(v)<<endl;
    return 0;
}