글 읽기 - 2258번 정육점 어디가 틀린 건지 모르겠어요 ㅠㅠ

xornrbboy 9년 전 1

음 생각나는 테스트케이스들을 넣어봐도 다 맞는거 같고... 잘 짠거 같은데 어디가 틀린지 모르겠네요 ㅠㅠ

제 코드가 어디가 틀렸는지에 대해 도와주시면 정말 감사하겠습니다 ㅠㅠ

#include <cstdio>
#include <algorithm>

using namespace std;

class meat
{
public:
	int price;
	int kg;

	meat(){}
	meat(int kg, int price):kg(kg), price(price){}
	
	bool operator<(const meat& m) const
	{
		int kg1 = this->kg;
		int kg2 = m.kg;
		int price1 = this->price;
		int price2 = m.price;

		if(kg1<kg2) return true;
		else if(kg1>kg2) return false;
		else {
			if(price1<price2) return true;
			else return false;
		}
	}
};

int main(void)
{
	int N,M;
	meat m[100000];

	scanf("%d%d",&N,&M);
	for(int i=0;i<N;i++)
	{
		scanf("%d%d",&m[i].kg,&m[i].price);
	}
	sort(m,m+N);     //가볍고 싼 순서로 정렬.

	int best_kg=-1;
	int sum_kg=0;
	int sum_price=0;
	int all_kg=0;

	for(int i=0;i<N;i++)
	{
		int kg = m[i].kg;
		int price = m[i].price;
		all_kg+=kg;
		if(best_kg==kg){
			if(sum_kg<M){
				sum_kg+=kg;
				sum_price+=price;
			}
		}
		else{ //best_kg<kg
			best_kg=kg;
			if(sum_price>=price || sum_kg<M){
				sum_price=price;
				sum_kg=all_kg;
			}
		}
	}
	if(sum_kg<M) sum_price=-1;
	printf("%d\n",sum_price);

	return 0;
}

WeissBlume 9년 전 0

과연 단순히 가볍고 싼 순서대로 정렬하는게 최적일까 다시 생각해보세요 ㅎㅎ

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

문제

문제

출처

ICPC

2258번 정육점 어디가 틀린 건지 모르겠어요 ㅠㅠ

xornrbboy 9년 전 1

WeissBlume 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말