글 읽기 - 반례를 도저히 못찾겠습니다.

sac7160 2년 전 0

반례를 도저히 못찾겠습니다ㅠ

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>


using namespace std;
class Compare{
public:
    bool operator() (int a,int b)
    {
        return abs(a) > abs(b);
    }
};

int main()
{
    int t,m;
    cin >> t;
    vector<int>* nums = new vector<int>[t];
    int num;
    
    for(int i=0; i<t; i++)
    {
        cin >> m;
        for(int j=0; j<m; j++)
        {
            cin >> num;
            nums[i].push_back(num);
        }
    }//입력
    
    int n;
    for(int i=0; i<t; i++)
    {
        n = (int)(nums[i].size())/2+1 ;
        cout << n << '\n';
        priority_queue<int, vector<int>, Compare> minHeap;
        priority_queue<int> maxHeap;
        int count =0;
        
        for(int j=0; j<nums[i].size(); j++)
        {
           
            maxHeap.push(nums[i][j]);    //일단 maxHeap에 넣고 maxHeap에서 가장 큰수를 다시 minHeap에 넣음
            minHeap.push(maxHeap.top());
            maxHeap.pop();
            
            if(minHeap.size()>=maxHeap.size()) {  //maxheap().size가 minHeap().size 보다 1 크게 유지 , maxHeap().top이 중간값
                maxHeap.push(minHeap.top());
                minHeap.pop();
            }

            if(j%2 ==0|| count ==0) {
                cout << maxHeap.top() << " " ;
                count++;
            }

            if((j+1)%20 == 0)
            {
                cout << '\n';
            }
        }
        
        for(int i =0; i<maxHeap.size(); i++)
        {
            maxHeap.pop();
        }
        for(int i =0; i<minHeap.size(); i++)
        {
            minHeap.pop();
        }
        
        cout << '\n';
    }
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 도저히 못찾겠습니다.

sac7160 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말