글 읽기 - 시간 초과가 나옵니다 O(nlogn)

kkweon 4년 전 1

O(nlogn)으로 시간초과가 나옵니다 질문을 검색해봐도 비슷한 아이디어로 O(nlogn)으로 통과가 되는 것 같은데

제 아이디어는 어디에서 잘못됬는지 못찾겠습니다

구조체 "볼 { 인덱스, 크기, 색 }" 선언
크기 오름 차순 정렬 (카운팅 정렬도 사용해봤었습니다 O(2000 * N) 로도 시간초과가 나왔습니다)
누적합을 구할 변수 선언 (int tot = 0;)
(색: 총 누적합) 해시맵 선언 unordered_map<int, int> color2size;

그래서 크기가 작은 볼부터

vector<int> answer(N);

for (auto& ball : balls) {
  answer[ball.idx] = tot - color2size[ball.color]
  tot += balls.size;
  color2size[ball.color] += balls.size;
}

해 나가는 전략입니다

#include <bits/stdc++.h>
using namespace std;

int N;

struct Ball {
  int idx;
  int color;
  int size;
  bool operator<(const Ball& b) const {
    if (size == b.size) return color < b.color;
    return size < b.size;
  }
};

int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  cin >> N;
  vector<Ball> balls;

  for (int i = 0; i < N; ++i) {
    int c, s;
    cin >> c >> s;
    balls.push_back({i, c, s});
  }

  sort(balls.begin(), balls.end());

  unordered_map<int, int> color2size;
  int tot = 0;

  vector<int> ans(N);

  for (auto& b : balls) {
    ans[b.idx] += tot - color2size[b.color];
    tot += b.size;
    color2size[b.color] += b.size;
  }

  for (auto& a : ans) cout << a << endl;

  return 0;
}

djm03178 4년 전 3

endl은 버퍼를 flush하는 역할을 겸하기 때문에 매우 매우 느립니다. '\n'을 대신 사용하세요.

kkweon 4년 전 0

와 자꾸 알고리즘만 생각하다 미쳐 생각을 못했네요 감사합니다

jungyr24 4년 전 0

감사합니다 덕분에 저도 해결했어요 ~!!

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

문제

문제

출처

ICPC

시간 초과가 나옵니다 O(nlogn)

kkweon 4년 전 1

djm03178 4년 전 3

kkweon 4년 전 0

jungyr24 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말