글 읽기 - 반례를 찾습니다.

adfsfsf 5년 전 0

sort 함수가 익숙하지 않아서 qsort를 썼습니다.

#include <iostream>
#include <cstdlib>
using namespace std;
class nums {
public:
	long int num, time;
};
class nums *ns;//c++에선 구조체 사용이 오류가 나길래 클래스의 형식을 빌렸습니다.
long int *s;//체크 배열
int com(const void *a, const void *b);
int main(void)
{
	long int n, i, sum, k = 0, j;
	cin >> n;
	ns = new class nums[n];
	s = new long int[n] {0};
	for (i = 0; i < n; i++)
		cin >> ns[i].time >> ns[i].num;
	qsort(ns, n, sizeof(class nums), com);
	sum = 0, j = 0;
	for (i = 0; i < n; i++)
	{
		for (j = ns[i].time; j < n; j++)
		{
			if (s[j] >= ns[i].time)//만약 현재 조사하는 문제를 풂으로써 미리 선택한 문제를 풀 수 없게 된다면
			{                      //예를 들어, 1일 거 1개 받은 상태에선 2일 거를 1개 이상 못 받는다는 점을 이용하는 겁니다.
				k = 1;
				break;
			}
		}
		if (k == 1)//받지 않기로 결론 났으면 넘어갑니다.
		{
			k = 0;
			continue;
		}
		sum += ns[i].num;//받으면 해당 문제에서 얻는 컵라면 수를 합에 더합니다.
        for (j = ns[i].time - 1; j < n; j++)//현재 데드라인 포함 이후의 날들에 인덱스 값을 1씩 증가시킵니다.
			s[j]++;
	}
	cout << sum<< endl;//합을 출력합니다.
	return 0;
}
int com(const void *a, const void *b)
{
	class nums m = *(class nums *)a, n = *(class nums *)b;
	if (m.num > n.num)
		return -1;
	if (m.num < n.num)
		return 1;
	else
	{
		if (m.time > n.time)
			return 1;
		if (m.time < n.time)
			return -1;
	}
	return 0;
}

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

문제

문제

출처

ICPC

반례를 찾습니다.

adfsfsf 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말