5 条题解

  • 1
    @ 2025-4-19 22:02:28

    #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; }

    • 0
      @ 2025-7-30 13:11:37
      #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;
      }
      
      
      
      • 0
        @ 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; }

        • 0
          @ 2021-8-7 18:35:25

          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;
          }
          
          
          • -1
            @ 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;
            }
            
            
            • 1

            信息

            ID
            18
            时间
            1000ms
            内存
            128MiB
            难度
            3
            标签
            递交数
            235
            已通过
            123
            上传者