글 읽기 - 후,,,틀린이유 부탁드립니다!

ahdtld54 3년 전 0

저는 대각선으로 th-번째 대각선에 해당하는 수들 모두 (th-1)-번째 대각선에 해당하는 수들 보다 모두 크다는 점을 이용해서 문제를 해결하려고 하였으나 틀렸다고 뜨네요,,ㅠ 예제들은 모두 맞고 N이 4일 때의 경우를 모두 확인해 봤을 때도 이상한 점이 없었습니다... 도움부탁드립니다!

#include <iostream>
#include <algorithm>
using namespace std;

long N, k;
long arr[100001];

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> k;
	// 4 7
	if (N*(N + 1) / 2 >= k) {
		int th = 1;
		long sum = 1;
		while (sum < k) {
			th++;
			sum += th;
		}
		for (int i = 1; i <= th; i++) {
			arr[i] = i*(th-(i-1));
		}
		stable_sort(arr+1, arr + th + 1);
		long num = k - (th - 1)*(th) / 2;
		/*
		cout << th << '\n';
		for (int i = 1; i <= th; i++)
			cout << arr[i] << ' ';
		cout << '\n';
		cout << num;
		*/
		cout << arr[num];
	}
	else {
		int th = N;
		long sum = N * (N + 1) / 2;
		
		while (sum < k) {
			th++;
			sum += 2 * N - th;
		}
		
		for (int i = 1; i <= 2*N - th; i++) {
			arr[i] = (i + (th - N)) * ((th + 1) - (i + (th - N)));
		}
		stable_sort(arr + 1, arr + 2 * N - th + 1);
		long num = k - (sum - 2*N + th) ;
		
		cout << arr[num];
		
	}
}

sweetlulu486 3년 전 0

최소힙을 쓰면 k번만에 k 번째 수를 구할 수 있을 거 같습니다.

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

문제

문제

출처

ICPC

후,,,틀린이유 부탁드립니다!

ahdtld54 3년 전 0

sweetlulu486 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말