阿里笔试3.30题目（只有两道编程题）

• 1，小强有n个养鸡场，弟i个养鸡场初始有a[i]只小鸡。与其他养鸡场不同的是，他的养鸡场每天增加k只小鸡，小强每天结束都会在数量最多的养鸡场里卖掉一半的小鸡，假如一个养鸡场有x只鸡，则卖出后只剩下x/2(向下取整)只鸡。问m天后小强的n个养鸡场一共多少只小鸡？

  • 输入

    第一行输入三个int类型n,m,k（1 <= n,m,k <= 10^6）

    第二行输入n个正整数，表示n个养鸡场初始鸡的个数

  • 输出

    输出一个整数表示鸡的总数

  • 示例

    输入：

    3 3 100

    100 200 400

    输出：

    925

  • 思路：优先队列，时间复杂度O(mlogn)

  • 代码

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    int main(){
        int n,m,k,t;
        ll base(0),sum(0);
        scanf("%d%d%d",&n,&m,&k);
        priority_queue<int> heap;//默认大根堆
        for(int i = 0; i < n; i++){
            scanf("%d", &t);
            heap.emplace(t);
            sum += t;
        }
        for(int i = 0;i < m; i++){
            base += k;
            t = heap.top() + base;
            int d = (t + 1) / 2;
            heap.pop();
            heap.emplace(t - d - base);
            sum -= d;
        }
        printf("%lld\n",base * n + sum);
    }

• 2，小强得到了长度为n的序列，但他只对非常大的数字感兴趣，因此随机选择这个序列的一个连续子序列，并求这个序列的最大值，请告诉他这个最大值的期望是多少?

  • 输入

    第一行n表示序列长度接下来一行n个数描述这个序列，n大于等于1小于等于1000000，数字保证是正整数且不超过100000

    第二行n个数字表示序列的值

  • 输出

    保留6位小数

  • 样例

    输入：

    3

    1 2 3

    输出：

    2.333333

    解释：

    {1},{2},{3},{1,2},{2,3},{1,2,3}为所有子序列，1最大的概率1/6，2最大的概率为2/6，3最大概率3/6，期望14/6

  • 思路：单调栈 + 动态规划，时间复杂度O(n)

    在序列x中，长度为1的子序列有n个，长度为2的子序列有n-1个...长度为n-1的子序列有2个，长度为n的子序列有1个，总的序列数：c = n+(n-1)+...+2+1 = n*(n+1)/2 个，每个出现的概率相同;

    考虑以x[i]为结尾的子序列，这些子序列中有两种情况，一种是最大值为x[i]，两一种是最大值不为x[i]；最大值不为x[i]的相当于x[i]没有加入，可以借助之前的状态求解；最大值为x[i]的情况只需记录有多少个。

    用单调栈的思路，从大到小存放出现的元素，并记录值对应的index值。

  • 代码

    #include<bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> PII;
    const int N = 1000006;
    double dp[N];//dp[i]表示前i个数中的最大值期望
    int main(){
        int n,t;
        scanf("%d",&n);
        ll c = (ll)n * (n + 1) / 2;
        dp[0] = 0;//无意义
        stack<PII> m;
        double res = 0;
        for(int i = 0;i < n; i++){
            scanf("%d",&t);
            while(!m.empty() && m.top().first <= t){
                m.pop();
            }
            int d = m.empty()?i + 1 : i-m.top().second;
            dp[i + 1] = 1.0 * t *d / c + dp[i + 1 - d];
            res += dp[i + 1];
            m.emplace(t,i);
        }
        printf("%.6f\n",res);
    }