做好网站建设静态化,wordpress页面原文件下载,张家港网站关键词优化,邢台123招聘信息今天1. 题目描述#xff1a; 多多开了一家自助餐厅#xff0c;为了更好地管理库存#xff0c;多多君每天需要对之前的课流量数据进行分析#xff0c;并根据客流量的平均数和中位数来制定合理的备货策略。 2. 输入输出描述#xff1a;
输入描述#xff1a; 输入共两行#x…1. 题目描述 多多开了一家自助餐厅为了更好地管理库存多多君每天需要对之前的课流量数据进行分析并根据客流量的平均数和中位数来制定合理的备货策略。 2. 输入输出描述
输入描述 输入共两行 第一行一个整数N表示餐厅营业总天数(0 N200,000) 第二行共N个整数分别表示第i天的课流量Ri(0 Ri 1,000,000); 输出描述 输出共两行 第一行长度为N其中第i个值表示前i天客流量的平均值。 第二行长度为N其中第i个值表示前i天客流量的中位数。 示例1输入输出示例仅供调试后台判题数据一般不包含示例。
输入 5 1 2 3 4 10 输出 1 2 2 3 4 1 2 2 3 3 3. 题解
思想
1 求中位数的思路见力扣295题:数据流的中位数 a. 建立一个大根堆一个小根堆。大根堆存储小于当前中位数小根堆存储大于等于当前中位数。且小根堆的大小永远都比大根堆大1或相等。 b. 根据上述定义我们每次可以通过小根堆的堆顶或者两个堆的堆顶元素的平均数求出中位数。 c. 维护时如果新加入的元素大于等于当前的中位数则加入小根堆否则加入大根堆。然后如果发现两个堆的大小关系不满足上述要求则可以通过弹出一个堆的元素放到另一个堆中。 2求平均值是采用前缀和。
3) 有个坑是向上取整。如果分母没有1.0 或者2.0就会变成int型这时候你再用ceil也不会有向上取整的效果了。因为是先变成了整数再向上取整。
C代码
#include iostream
#include queue
#include cmath
using namespace std;int main() {int n;cin n;int R[n];for (int i 0; i n; i) {cin R[i];}// 求前缀和int prefixSum[n];prefixSum[0] R[0];for (int i 1; i n; i) {prefixSum[i] prefixSum[i - 1] R[i];}// 计算平均值和中位数double avg[n];int median[n];//用两个堆维持中位数的位置//down是一个大顶堆存储小于等于中位数的值。//up是一个小顶堆存储大于中位数的值。//down存储的数量最多比up多一个。人为规定。priority_queueint down;priority_queueint, vectorint, greaterint up;for(int i 0; i n; i) {if (down.empty() || R[i] down.top()) {down.push(R[i]);if (down.size() up.size() 1) {up.push(down.top());down.pop();}} else {up.push(R[i]);if (up.size() down.size()) {down.push(up.top());up.pop();}}if((down.size() up.size()) % 2){median[i] down.top();}else{median[i] ceil((down.top()up.top())/2.0);//向上取整}avg[i] ceil(prefixSum[i]/(i 1.0));//向上取整}// 输出结果for (int i 0; i n; i) {cout (int) avg[i] ;}cout endl;for (int i 0; i n; i) {cout median[i] ;}cout endl;return 0;
}Java代码ChatGPT转换的
import java.util.PriorityQueue;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();int[] R new int[n];for (int i 0; i n; i) {R[i] sc.nextInt();}// 求前缀和int[] prefixSum new int[n];prefixSum[0] R[0];for (int i 1; i n; i) {prefixSum[i] prefixSum[i - 1] R[i];}// 计算平均值和中位数double[] avg new double[n];int[] median new int[n];PriorityQueueInteger down new PriorityQueue((a, b) - b - a);PriorityQueueInteger up new PriorityQueue();for (int i 0; i n; i) {if (down.isEmpty() || R[i] down.peek()) {down.offer(R[i]);if (down.size() up.size() 1) {up.offer(down.poll());}} else {up.offer(R[i]);if (up.size() down.size()) {down.offer(up.poll());}}if ((down.size() up.size()) % 2 1) {median[i] down.peek();} else {median[i] (int) Math.ceil((down.peek() up.peek()) / 2.0);}avg[i] Math.ceil(prefixSum[i] / (i 1.0));}// 输出结果for (int i 0; i n; i) {System.out.print((int) avg[i] );}System.out.println();for (int i 0; i n; i) {System.out.print(median[i] );}System.out.println();}
}
