阿里实习笔试题

第二题是单调栈。。。。

#include<bits/stdc++.h> using namespace std; typedef long long ll; int main(){     int n, m, k, tmp;     cin>>n>>m>>k;     ll base(0), sum(0);     priority_queue<int> q;     for(int i=0;i<n;i++){         cin>>tmp;         q.emplace(tmp);         sum+=tmp;     }        for(int i=0;i<m;i++){         base+=k;         int t=q.top()+base;         q.pop();         int s=floor(t/2);         q.emplace(t-s-base);         sum-=s;     }     cout<<sum+base*n<<endl;     system("pause"); } 大佬看看，这样做对吗

第2道题，这样应该能解（i=0,1...n-1，A(n,n)可以化简）。 PS:我是蚂蚁的算法，我招人(推荐&NLP&CV）哦，我不太care 0不0分的，今年的算法题出的不太好。

我也是两题觉得不太难 都是0通过哈哈哈

第一题我没来得及交，你可以参考一下，感觉是对的，就是先把m*k加上去。 然后维护一个大顶堆，然后每次从堆里面弹出一个数，减去（index*k）后除以2再加上index*k后加入堆。index第一天是m-1,第二天是m-2。

第一题。。。我直接给定了鸡场的鸡和每个鸡场的个数。。。用于测试，用python写得

private static double ExpectionNum(int[] arr) { int min = getMin(arr); int max = getMax(arr); int[] dp1 = new int[max - min + 1]; //当前数字对应出现的次数 int n = arr.length; int[] dp2 = new int[n]; //当前字符结尾的序列长度; dp1[arr[0] - min] = 1; for(int i = 1;i < n;i++) { if(arr[i] >= arr[i-1]) { dp2[i] += dp2[i-1]; dp1[arr[i] - min] += dp2[i] + 1; }else { dp2[i] = 1; dp1[arr[i] - min] += dp2[i]; } } int count = 0; double res = 0; for(int i = 0;i < dp1.length;i++) { res += (i + min) * dp1[i]; count += dp1[i]; } return Math.round(res/count * 1000000) * 0.000001d; } 计数排序做第二题

没考试，刚试了一下，大佬们看看这样能不能过： 1， import heapq tasks = [] L = [1, 4, 2, 10, 100, 50, 600, 32, 42, 200, 100000, 3225] k = 2 m = 100000 for item in L:     heapq.heappush(tasks, -item)      for i in range(m):     tasks_2 = tasks[::]     tasks = [item - k for item in tasks]     x = heapq.heappop(tasks)     heapq.heappush(tasks, x // 2)     if sorted(tasks) == sorted(tasks_2):         break print(-sum(tasks)) 2， L = list(range(1000)) n = len(L) ans = [0 for i in range(n)] ans[0] = L[0] for i in range(1, n):     ans[i] = ans[i - 1]     M = L[i]          for j in range(i, -1, -1):         M = max(M, L[j])         ans[i] += M print(ans[-1] / (n * (n + 1) / 2))

第一题，我也是暴力超时，我在想用树状数组可以做出来么？但是每次都要找最大值，也许会超时？ 第二题，我开始审题错误，最后五分钟想到了一个解法，然鹅没什么卵用，说出来大家看看对不对： 第一遍从头到尾遍历一次，记录元素i之前比它大的最小的一个数的位置dp1[i]（有点绕233），如果之前都比他小，则记录它自己的位置，比较的时候需要比较：它自己a[i]，它前一个数所记录的dp1[i-1]，和它前一个数a[i-1]: if(a[i-1]>a[i]) dp1[i] = i-1; else if(a[i]>a[dp1[i-1]]) dp1[i] = i;（这里我觉得需要严格大于，如果等于的话，应该记录dp[i-1],覆盖范围更广） else dp1[i] = dp[i-1]; 同理，在从尾到头遍历一次，记录元素i后面比它大的最小的一个数的位置dp2[i] 这样的话，通过dp1[i]和dp2[i]能确定以i元素为最大的集合能有多少个，最后再从头到尾遍历一遍计算期望，这样的复杂度是O(3n)？

刚试了一下，第一题的解好像是收敛的，不一定迭代到m天

两题都不会啊，只会暴力，暴力都是各过30

快快快，来个大佬分享一波，这个东西，阿里一面会问你有没有下去看看，这个怎么做

第二题，考完才写出来，不知道对不对，我想的是用两个数组dp1[i]表示以第i个数字结尾且第一个数字最大的子序列个数，然后从右往左再来个dp2。那么最大值为i的子序列个数为2*(dp1[i] + dp2[i])，就是当前往左的序列个数dp1[i]加上当前往右的序列个数dp2[i]，然后左边的所有数字组成的序列可逐个往右扩展dp2[i]个，右边往左扩展dp1[i]个，两者重复一个，但是少算了一个数字本身，所以抵消了。但是当其中一个为0的时候，则只保留另一个数组的值+1(数字本身)。 dp1 = [0]*n dp2 = [0]*n for i in range(1, n): if nums[i]>nums[i-1]: dp1[i] = dp1[i-1]+1 for i in range(n-2, -1, -1): if nums[i]>nums[i+1]: dp2[i] = dp2[i+1] + 1 sums = sum(range(n+1)) res = 0 for i in range(len(dp1)): if dp1[i] == 0&nbs***bsp;dp2[i] == 0: res += (nums[i] * (dp1[i] + dp2[i] + 1)) / sums else: res += (nums[i]*(2*(dp1[i] + dp2[i])))/sums print(round(res, 6))

第二题题目说了是有序序列吧。。然后取子序列

我也是0分，第一题一个是数组记录的值永远是实际鸡数-天数*每天新鸡，这样一次只要改一个数字，建堆这样每次该数字复杂度log2n，我没有建堆，想试试能通过几例，然后看到自己是0分就放弃了 第二题我没弄明白自己为什么错，肯定不是复杂度高了，我的思路是最大为A[i]（实际上的i-1）的连续子集有i个,这样一共 (n + 1)* n / 2个，然后拿A[i]*i/( (n + 1)* n / 2)求和就行，不知道哪里错了……等大佬给我解答     int n;     cin >> n;     vector<int> list(n);     for (int i = 0; i < n; i++) {         cin >> list[i];     }     int totalcount = (n + 1)* n / 2;     double result = 0;     for (int i = 0; i < n; i++) {         result += (i + 1.0) / totalcount * list[i];     }     cout << setiosflags(ios::fixed);     cout << setprecision(6) << result;

第一题我用一个优先队列存储每个养鸡场第i天鸡的数目减去i*k（这样就不用每天+k了），然后每天找出最大值加上i*k计算这个养鸡场鸡的数目，再计算卖出的数目。 最后返回初始鸡的数目+总的鸡增长的数目-总的卖出的数目。 我感觉是对的啊，他给的测试例也能通过，但一直是0%，求指点。。。 第二题没什么时间了，用dp记录了一下每个区间的最大值，通过了30%，后面的超时了。 主要是第一题一直在找问题也没找到，浪费太多时间了。。。

粘一下我AC 0%的代码，不要学习，欢迎纠错 第一题，暴力 import java.util.Arrays; import java.util.Scanner; public class Main {     public static void main( String[] args )     {         Scanner sc = new Scanner(System.in);         int n = sc.nextInt();         int m = sc.nextInt();         int k = sc.nextInt();         int a[] = new int[n];         int ans = 0;         for( int i = 0; i < n; i++ )         {             a[i] = sc.nextInt();         }         ans = mdaysNum( a, n, m, k );         System.out.println( ans );     }     public static int mdaysNum( int[] a, int n, int m, int k )     {         int sum = 0;         for( int j = 0; j < m; j++ )         {             for( int i = 0; i < n; i++ )             {                 a[i] += k;             }             Arrays.sort( a );             a[ n-1 ] = a[ n-1 ]/2;         }         for( int  i = 0; i < n; i++ )         {             sum += a[i];         }         return sum;     } }