阿里笔试3.30题目(只有两道编程题)

感谢作者:布里斯班狮不吼

整理:Jerry

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;
intmain(){
    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位小数

样例 输入:

输出:

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个数中的最大值期望
intmain(){
    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);
}

我来评几句
登录后评论

已发表评论数()

相关站点

热门文章