阿里笔试赛后思路。。。
养鸡场这题显然需要避免更新鸡场鸡数量，实际上每个鸡场都会每天增加K只鸡，那就相当于没有增加，只要最后的总数加上n*m*k就行了。
用优先队列维护鸡数最大值，队列里只存放原鸡场的鸡，那么第i天鸡场的鸡是队列中的加上i*k，每天取原鸡场最大值出来，减去这个鸡场鸡总数的一半然后放回队列，表示这个鸡场剩下原鸡的数量，max = max - (max+ i*k)/2。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int main()
{
int n, m, k;
cin >> n >> m >> k;
long long chick;
priority_queue<long long> que;
for (int i = 0; i < n; i++){
cin >> chick;
que.push(chick);
}
for (int i = 1; i <= m; i++){
long long now = que.top();
que.pop();
now -= (now+i*k)/2;
que.push(now);
}
long long sum = 0;
while (!que.empty())
{
sum += que.top();
que.pop();
}
cout << sum + n*m*k << endl;
return 0;
} 序列求期望的，我的思路是求出以当前值num[i]为最大值的左右边界，例如 4 1 2 3 2 1 4，那么以3为最大值的左边界为i-3，右边界为i+3，那么序列应该有3 * 3 = 9个，分别是 123， 1232， 12321， 23，232，2321，3，32，321 然后sum += num[i]*L*R
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main()
{
int n; cin >> n;
long long num[n+1];
for (int i = 0; i < n; i++) cin>>num[i];
long long sum = 0;
for (int i = 0; i < n; i++){
int L = 1, R = 1;
while (i-L >= 0 && num[i-L] <= num[i]) L++;
while (i+R < n && num[i+R] <= num[i]) R++;
sum += num[i]*L*R;
}
long long m = n*(n+1)/2;
cout << 1.0*sum/m << endl;
return 0;
}
但是存在一些问题，比如 3 1 3，在计算第一个3的时候会用到313序列，第二个也会用到，重复计算了。
我觉得如果只在左边界去等应该可以避免重复，但是没法验证了。也就是
while (i-L >= 0 && num[i-L] <= num[i]) L++;
while (i+R < n && num[i+R] < num[i]) R++;
不足之处麻烦大家指正，谢谢！ 
腾讯成长空间 5958人发布
投递快手等公司10个岗位
