5 条题解
-
1
#include <queue> #include <vector> using namespace std; // 定义比较函数，用于创建最小堆（因为priority_queue默认是最大堆） struct CompareMinHeap { bool operator()(int a, int b) { return a > b; // 小顶堆：如果a > b，则a的优先级更低，会被放到后面 } }; // 按格式打印中位数序列 void printMedians(const vector<int>& medians, int count) { int index = 0; // 当前输出的中位数索引 // 按每行10个的格式输出 while (index < count) { for (int i = 0; i < 10 && index < count; ++i, ++index) { cout << medians[index] << " "; // 输出当前中位数 } cout << endl; // 换行 } } int main() { int P; // 数据集个数 cin >> P; // 处理每个数据集 for (int p = 0; p < P; ++p) { int datasetNumber; // 数据集编号 int M; // 数据集中元素个数 // 读取数据集编号和元素个数 cin >> datasetNumber >> M; vector<int> numbers; // 存储当前数据集的所有数字 // 直接读取M个整数 for (int i = 0; i < M; ++i) { int num; cin >> num; numbers.push_back(num); } priority_queue<int> max_heap; // 最大堆（存储较小的一半元素） priority_queue<int, vector<int>, CompareMinHeap> min_heap; // 最小堆（存储较大的一半元素） vector<int> medians; // 存储中位数结果 // 遍历所有数字，动态维护中位数 for (int i = 0; i < numbers.size(); ++i) { int num = numbers[i]; // 当前处理的数字 // 将数字插入合适的堆中 if (max_heap.empty() || num <= max_heap.top()) { max_heap.push(num); // 插入最大堆（较小的一半） } else { min_heap.push(num); // 插入最小堆（较大的一半） } // 调整堆的大小，保持平衡 // 平衡条件：max_heap的大小最多比min_heap大1，或两者相等 if (max_heap.size() > min_heap.size() + 1) { // 如果max_heap太大，将堆顶元素移到min_heap min_heap.push(max_heap.top()); max_heap.pop(); } else if (min_heap.size() > max_heap.size()) { // 如果min_heap太大，将堆顶元素移到max_heap max_heap.push(min_heap.top()); min_heap.pop(); } // 当已处理的数字个数为奇数时，计算并存储中位数 if ((i + 1) % 2 == 1) { if (max_heap.size() > min_heap.size()) { medians.push_back(max_heap.top()); // 中位数在max_heap的堆顶 } else { medians.push_back(min_heap.top()); // 中位数在min_heap的堆顶 } } } // 输出结果 cout << datasetNumber << " " << medians.size() << endl; // 数据集编号和中位数个数 printMedians(medians, medians.size()); // 按格式打印中位数序列 } return 0; } -
1
#include #include #include #include using namespace std; priority_queuedgd;//大根堆 priority_queue<int,vector,greater >xgd;//小根堆 int main() { int p,m,count; scanf("%d",&p); while(p--) { while(dgd.size()) dgd.pop();//清空 while(xgd.size()) xgd.pop();//清空 int x,cnt=0; scanf("%d%d",&count,&m); printf("%d %d\n",count,m/2+1); for(int i=0;i<m;i++) {
scanf("%d",&x); if(xgd.empty()) xgd.push(x); else { if(x>xgd.top()) xgd.push(x); else dgd.push(x); while(xgd.size()<dgd.size()) { xgd.push(dgd.top()); dgd.pop(); } while(xgd.size()>dgd.size()+1) { dgd.push(xgd.top()); xgd.pop(); } } if((i+1)&1) { cnt++; printf("%d ",xgd.top()); if(!(cnt%10)) printf("\n"); } } printf("\n");} return 0; }
-
1
C++ :
#include<iostream> #include<cstdio> #include<queue> #include<vector> using namespace std; priority_queue<int>dgd;//大根堆 priority_queue<int,vector<int>,greater<int> >xgd;//小根堆 int main() { int p,m,count; scanf("%d",&p); while(p--) { while(dgd.size()) dgd.pop();//清空 while(xgd.size()) xgd.pop();//清空 int x,cnt=0; scanf("%d%d",&count,&m); printf("%d %d\n",count,m/2+1); for(int i=0;i<m;i++) { scanf("%d",&x); if(xgd.empty()) xgd.push(x); else { if(x>xgd.top()) xgd.push(x); else dgd.push(x); while(xgd.size()<dgd.size()) { xgd.push(dgd.top()); dgd.pop(); } while(xgd.size()>dgd.size()+1) { dgd.push(xgd.top()); xgd.pop(); } } if((i+1)&1) { cnt++; printf("%d ",xgd.top()); if(!(cnt%10)) printf("\n"); } } printf("\n"); } return 0; } -
0
jinhongxian LV 7 @ 2025-3-29 18:57:24
#include #include #include #include using namespace std; priority_queuedgd;//大根堆 priority_queue<int,vector,greater >xgd;//小根堆 int main() { int p,m,count; scanf("%d",&p); while(p--) { while(dgd.size()) dgd.pop();//清空 while(xgd.size()) xgd.pop();//清空 int x,cnt=0; scanf("%d%d",&count,&m); printf("%d %d\n",count,m/2+1); for(int i=0;i<m;i++) {
scanf("%d",&x); if(xgd.empty()) xgd.push(x); else { if(x>xgd.top()) xgd.push(x); else dgd.push(x); while(xgd.size()<dgd.size()) { xgd.push(dgd.top()); dgd.pop(); } while(xgd.size()>dgd.size()+1) { dgd.push(xgd.top()); xgd.pop(); } } if((i+1)&1) { cnt++; printf("%d ",xgd.top()); if(!(cnt%10)) printf("\n"); } } printf("\n");} return 0; }
-
-1
lutingxuan LV 10 @ 2022-10-15 19:43:41
#include<cstring> #include<algorithm> #define N 11000 using namespace std; struct fuck { int x,y; }a[N]; inline bool cmp(fuck x,fuck y){return x.x<y.x;} struct node { int l,r,x/*权值*/; }b[N]; void del(int x) { b[b[x].l].r=b[x].r; b[b[x].r].l=b[x].l; } int n,be[N]; int list[N],top; int main() { int T;scanf("%d",&T); while(T--) { top=0; int t;scanf("%d%d",&t,&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i].x); a[i].y=i; b[i].l=i-1;b[i].r=i+1; } sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++)be[a[i].y]=i,b[i].x=a[i].x;//确定其在链表中的位置 int ans=n/2+1,l=n/2/*左边有多少个数字*/,r=n/2/*右边有多少个数字*/; for(int i=n;i>=1;i--)//按顺序删除 { if(i%2==1) { if(l<r) { ans=b[ans].r;l++;r--; } else if(l>r) { ans=b[ans].l;l--,r++; } list[++top]=b[ans].x; } if(be[i]==ans)//刚好卡在中位数的位置 { if(l>r)ans=b[ans].l,l--,r++; else if(l<=r)ans=b[ans].r,l++,r--; } if(be[i]>ans)r--; else l--; del(be[i]); } //后面就是输出的问题了。 printf("%d %d\n",t,n/2+1); int now=0; for(int i=top;i>=1;i--) { now++; if(now>10) { now-=10; printf("\n"); } printf("%d",list[i]); if(now!=10)printf(" "); } printf("\n"); } return 0; }
lisiyan
LV 8
@ 2025-7-30 13:11:37
- 1