글 읽기 - 반례 부탁드려요ㅠㅠ

toto6599 5년 전 0

큐를 사용하지 않고 배열을 정렬해서 문제를 풀었는데 반례를 모르겠어요ㅠㅠ

반례 부탁드려요ㅠㅠㅠㅠ

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
int n, N, M, a, b,i,j,copy1,copy2,cnt, pos, flag;
int main(){
  std::cin>>n;
  for (i=0;i<n;i++){
    std::cin>>N>>M;
    std::vector<int> _v(N), _v2(N);
    cnt =0;
    for (j=0;j<N;j++){
      std::cin>>a;
      _v[j] = a;
    }
    b = _v[M];
    copy2 = 0;
    flag = 0;
    copy1=0;

    for (j=M+1; j<N;j++){
        if (_v[j] == b) {
          copy2++;
        }
        else if (_v[j] > b) {
          copy2 =0;
          flag = 1;
        }
    }
    if (flag){
        for (j=0;j<M;j++){
          if (_v[j]==b) copy1++;
        }
    }
    else {
        for (j=0;j<M;j++){
          if (_v[j]==b) copy1++;
          else if (_v[j]>b) copy1 =0;
        }
    }
    _v2 = _v;
    sort(_v2.begin(), _v2.end());
    for (j=N-1;j>-1;j--){
      if (_v2[j]==b)
        break;
    }

    if (flag) pos = N-j+copy1+copy2;
    else pos = N-j+copy1;

    std::cout<<pos<<'\n';
  }
  return 0;
}

chogahui05 5년 전 0

문제 조건은 다음과 같아요.

(1) 중요도를 확인한다.

(2) 앞에 있어야 한다.

sort 함수는 stable sort로 정렬하진 않아요.

toto님은 1차 정렬 조건만 가지고 정렬하시지 않으셨어요?

당연하게도, 1차 정렬 조건만을 가지고 정렬하면 뒤죽박죽 되겠네요. 2차 정렬 조건을 명시해서, 정렬을 하시거나.

stable sort를 이용해서 정렬하세요. 왠만하면 전자 추천 드립니다. 천천히 구현해 보세요.

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

문제

문제

출처

ICPC

반례 부탁드려요ㅠㅠ

toto6599 5년 전 0

chogahui05 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말