为什么最后一个测试点过不了
1119 胖达与盆盆奶
分数 20
作者 陈越
单位 浙江大学
panda.jpg
大熊猫，俗称“胖达”，会排队吃盆盆奶。它们能和谐吃奶的前提，是它们认为盆盆奶的分配是“公平”的，即：更胖的胖达能吃到更多的奶，等胖的胖达得吃到一样多的奶。另一方面，因为它们是排好队的，所以每只胖达只能看到身边胖达的奶有多少，如果觉得不公平就会抢旁边小伙伴的奶吃。
已知一只胖达每次最少要吃 200 毫升的奶，当另一份盆盆奶多出至少 100 毫升的时候，它们才能感觉到是“更多”了，否则没感觉。
现在给定一排胖达的体重，请你帮饲养员计算一下，在保持给定队形的前提下，至少应该准备多少毫升的盆盆奶？
输入格式：
输入首先在第一行给出正整数 n（≤10
4
），为胖达的个数。随后一行给出 n 个正整数，表示 n 只胖达的体重（公斤）。每个数值是不超过 200 的正整数，数字间以空格分隔。
输出格式：
在一行中输出至少应该准备多少毫升的盆盆奶。
输入样例：
10
180 160 100 150 145 142 138 138 138 140
输出样例：
3000
样例解释：
盆盆奶的分配量顺序为：
400 300 200 500 400 300 200 200 200 300
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,sum=0;
cin>>n;
int temp[n],f[n];
for(int i=0;i<n;i++)
cin>>temp[i];
memset(f,0,sizeof f);
f[0]=200;
for(int i=0;i<n-1;i++){
if(temp[i+1]==temp[i]) f[i+1]=f[i];
else if(temp[i+1]<temp[i]) f[i+1]=f[i]-100;
else f[i+1]=f[i]+100;
if(f[i+1]<200){
int start;
for(int j=i+1;;j--){
if(j==0||temp[j-1]<temp[j]){
start=j;
break;
}
}
for(int k=start;k<=i+1;k++)
f[k]+=100;
}
}
for(int i=0;i<n;i++)
sum+=f[i];
cout<<sum;
return 0;
}
【以下回答由 GPT 生成】
def calculate_milk(n, weights):
# 将胖达体重从大到小排序
weights.sort(reverse=True)
# 初始化总盆盆奶的毫升数为0
total_milk = 0
# 初始化每只胖达所需盆盆奶的毫升数的列表
milk_per_cat = []
# 计算每只胖达所需盆盆奶的毫升数
for i in range(n):
# 每只胖达的盆盆奶的毫升数等于它的体重 * 5，每只胖达至少需要5毫升盆盆奶
milk = weights[i] * 5
milk_per_cat.append(milk)
# 累加每只胖达所需的盆盆奶的毫升数到总盆盆奶的毫升数
total_milk += milk
return total_milk
# 输入胖达的个数n
n = int(input())
# 输入每只胖达的体重
weights = list(map(int, input().split()))
# 调用函数计算至少需要准备的盆盆奶的毫升数
result = calculate_milk(n, weights)
# 输出结果
print(result)
时间复杂度分析：
首先，将胖达的体重排序的时间复杂度为O(nlogn)。然后，计算每只胖达所需盆盆奶的毫升数需要遍历n只胖达，因此时间复杂度为O(n)。所以，总的时间复杂度为O(nlogn)。空间复杂度为O(n)。
【相关推荐】