怎么开发网站,卡地亚官方网站制作需要多少钱,html代码大全初学者必备,淘宝卖家中心网页版今天刷题时发现了一道十分难简单的题。大家仔细看看题目。 题目 5. K11937 平均值
题目描述
在演讲比赛中#xff0c;当参赛者完成演讲时#xff0c;评委会对他的表演进行评分。工作人员会去掉一个最高分#xff0c;一个最低分#xff0c;然后计算其余的平均值作为参赛者… 今天刷题时发现了一道十分难简单的题。大家仔细看看题目。 题目 5. K11937 平均值
题目描述
在演讲比赛中当参赛者完成演讲时评委会对他的表演进行评分。工作人员会去掉一个最高分一个最低分然后计算其余的平均值作为参赛者的最终成绩。
现在给定n个正整数去掉最大的n1个数和最小的n2数然后计算其余的平均值
输入格式
输入包含多组测试数据每组数据包含两个两行第一行是三个整数n1 n2 n(1≤n1,n2≤10n1n2≤n≤5*10^6)
第二行是n个整数,每个整数的范围是1到10^8
当输入为一行“0 0 0”表示输入结束
输出格式
对于每组测试数据输出平均值结果保留6位小数
输入输出样例
输入样例1复制
1 2 5
1 2 3 4 5
4 2 10
2121187 902 485 531 843 582 652 926 220 155
0 0 0
输出样例1复制
3.500000
562.500000
【耗时限制】4000ms 【内存限制】10MB 注意 不知道大家有没有发现啊这一题的【耗时限制】和【内存限制】有些特别。
【耗时限制】4000ms 【内存限制】10MB
4000m很大但10MB......
我们来算算 10MB10240KB≈10^7bits 一个int类型的变量占4个字节
1≤n≤5*10^6 数组要开这么大5000000
10^7/42.5*10^6 只有2500000个int况且程序运行还要空间
不说算法开个数组就爆了好吗 这咋写啊 推算一下 先不说超空间来看看基本写法
#include bits/stdc.h
using namespace std;
typedef long long LL;
LL n1,n2,n,a[5000010];
int main()
{while(cinn1n2nn1n2n0){for(LL i1;in;i) scanf(%lld,a[i]);sort(a1,an1);LL sum0;for(LL in21;in-n1;i) suma[i];printf(%.6lf\n,sum*1.0/(n-n1-n2));}return 0;
}
如果你仍然啥也看不出来
#include bits/stdc.h
using namespace std;
typedef long long LL;
LL n1,n2,n,a[5000010];
int main()
{while(cinn1n2nn1n2n0){LL sum0;for(LL i1;in;i){scanf(%lld,a[i]);suma[i];}sort(a1,an1);for(LL i1;in2;i) sum-a[i];for(LL in-n11;in;i) sum-a[i];printf(%.6lf\n,sum*1.0/(n-n1-n2));}return 0;
}
诶suma[i]不需要排序就能直接加也就是说可以是这样
#include bits/stdc.h
using namespace std;
typedef long long LL;
LL n1,n2,n,a;
int main()
{while(cinn1n2nn1n2n0){LL sum0;for(LL i1;in;i){scanf(%lld,a);suma;}//去掉最大的n1个数//去掉最小的n2个数printf(%.6lf\n,sum*1.0/(n-n1-n2));}return 0;
}
现在的问题是怎么“去掉最大的n1个数”“去掉最小的n2个数” 开始正片Action 意料之外情理之中 怎样“去掉最大的n1个数”“去掉最小的n2个数”
答案是优先队列
先来回忆一下优先队列
-priority_queue是c提供的一个优先队列的实现使用二叉堆实现。-
-priority_queue默认是大根堆 堆顶元素即为序列中的最大-
-priority_queue默认为大根堆可以较方便的获取最大值想要获取最小值时可以将默认 的大根堆修改为小根堆。-
-二叉堆适用于在一个动态变化的序列中查找极大值或极小值-
-二叉堆一般应用在贪心和动态规划类问题中用于阶段性最优值的获取。-
欸这和“最大的n1个数”“最小的n2个数”有什么关系
其实优先队列不仅能查找极大值或极小值还可以维护一群最小值/最大的。
先翻到文章末尾来做个选择
---------------------------------------------------------如何实现---------------------------------------------------------
来一个更新一次
这是一个容器
————————
| 点赞 |
| 关注 |
————————
来了一个元素就放进去
如果元素数量比n1大了
就把最小的踢了
这样就实现了维护一群最大的
既然要“把最小的踢了”就该用小根堆
而维护一群最小值就该用大根堆 理一理 小根堆-(维护一群最大的/极小值) 大根堆-(维护一群最小值/极大值)
你学废了吗
这样这题就能这样写
#include bits/stdc.h
using namespace std;
typedef long long LL;
LL n1,n2,n,a;
priority_queueLL pq1;
priority_queueLL,vectorLL,greaterLL pq2;
int main()
{while(cinn1n2nn1n2n0){LL sum0;for(LL i1;in;i){scanf(%lld,a);pq1.push(a);pq2.push(a);suma;if(pq1.size()n2) pq1.pop();if(pq2.size()n1) pq2.pop();}//去掉最大的n1个数while(!pq1.empty()) sum-pq1.top(),pq1.pop();//去掉最小的n2个数while(!pq2.empty()) sum-pq2.top(),pq2.pop();printf(%.6lf\n,sum*1.0/(n-n1-n2));}return 0;
} 评测结果 大家可以试试“K阶恒星系”也是这样子滴
