글 읽기 - 2258 정육점 예외좀 알려주세요

cubalys 8년 전 0

제가 만든 테스트케이스는 다 나오는 것 같은데

어디서 문제인지를 모르겠습니다.

#include <iostream>
#include <algorithm>
using namespace std;
typedef struct meat{ 
    int weight;
    int money;
}MEAT;
bool compare_M(MEAT p, MEAT q){
	return p.money < q.money;
}
bool compare_W(MEAT p, MEAT q){
	return p.weight > q.weight;
}
MEAT gogi[100000];
int main(){
	//sum  - i번 고기와 i 번고기보다 싼 고기들을 모두 합한 양
	//sum2 - i번 고기와 값이 같고 i번 고기보다 무거운 고기들을 모두 합한 양
    unsigned int N, M, sum = 0, sum2 = 0, P, MIN = 3000000000;
    cin>>N>>M;
    for(int i=0; i<N; i++) 
        cin>>gogi[i].weight>>gogi[i].money;
    //싼순으로 정렬 값이 같다면 무거운 순으로 정렬
	sort(gogi, gogi+N, compare_W); 
    sort(gogi, gogi+N, compare_M);
    for(int i=0; i<N; i++){
		// 전 고기와 가격이 같은 경우
        if(i > 0 && gogi[i].money == gogi[i-1].money){ 
            sum2 += gogi[i-1].weight;
            sum -= gogi[i-1].weight;
            sum += gogi[i].weight;
        }
		//가격이 다른 경우
        else {
            sum += sum2 + gogi[i].weight;
            P = i;
            sum2 = 0;
        }
		// sum 이 M보다 크거나 같으면 i번 고기만 사면 원하는 양을 얻을 수 있음
		if(sum >= M && MIN > gogi[i].money) {MIN = gogi[i].money; break;}
        // sum2 + sum 이 M보다 크거나 같으면 i번까지 i번과 가격이 같은 고기를 전부 사면 원하는 양을 얻을 수 있음
		if(sum2 + sum >= M){
            int S = 0;
            for(int j = P; j <= i; j++)
                S += gogi[j].money;
            if(MIN > S) MIN = S;
        }
    }
	// MIN 에 변화가 없으면 -1 출력
    cout << ((MIN == 3000000000) ? -1 : MIN) <<endl;
}

movie_jo 8년 전 1

알고리즘엔 크게 문제가 없어 보이는데요

혹시 sort가 무게 순서로 먼저 섞고 가격 순서로 다시 섞으면 앞의 무게 순서가 유지되는게 확실한지...

cubalys 8년 전 0

아 그럴수도 있겠네요 ㅜ

나름 테스트케이스 좀 만들어서

정렬되는지 뽑아보고 한거긴한데

제대로 확인해 봐야 겠네요

cubalys 8년 전 0

ㅋㅋ compare 함수를 바꿔 봤는데 그래도 틀리네요

어디서 실수가 있는건지....

bool compare(MEAT p, MEAT q){
    if(p.money < q.money) return 1;
	else if(p.money > q.money) return 0;
	else return p.weight > q.weight;
}

cubalys 8년 전 0

해결했습니다 감사합니다

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

문제

문제

출처

ICPC

2258 정육점 예외좀 알려주세요

cubalys 8년 전 0

movie_jo 8년 전 1

cubalys 8년 전 0

cubalys 8년 전 0

cubalys 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말