#define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; // 보석 도둑 , 틀렸습니다. void FindBag(pair now, int K, int* Bag, long long * Money, int * check) { // now.first : 무게, now.second : 금액 int L = 0; int R = K; int preMid = -1; int mid = (L + R) / 2; while (preMid != mid) { cout << "money : " << *Money << " L : " << L << " R : " << R << " mid : " << mid << "\n"; preMid = mid; // 이전의 mid if (mid == K) { // ㅈㄴ극단의 경우 break; } if (now.first <= Bag[mid]) { if (check[mid] != 1) { if (mid == 0) { *Money += now.second; Bag[mid] = -1; // 0 대입 check[mid] = 1; // 해당 위치를 사용함 break; } else if (Bag[mid - 1] < now.first) { *Money += now.second; Bag[mid] = Bag[mid - 1]; // 값 변경 후후 ~ check[mid] = 1; // 이미 사용함 // sort(Bag, Bag + K); // 이쒜끼 해결 break; } } R = mid; mid = (L + R) / 2; } else { L = mid; mid = (L + R) / 2; } } } // bool sort_second(pair a, pairb) { if (a.second > b.second) { return true; } if (a.second == b.second) { if (a.first <= b.first) { return true; } } return false; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); int N = 0; int K = 0; cin >> N; // 보석의 개수 cin >> K; // 가방의 개수 vector> Dia(N); // 보석의 무게 , 보석의 가격을 pair 로 선언 for (int i = 0; i < N; i++) { cin >> Dia[i].first; cin >> Dia[i].second; } sort(Dia.begin(), Dia.end(), sort_second); int* Bag = new int[K]; int* check = new int[K]; for (int i = 0; i < K; i++) { cin >> Bag[i]; check[i] = 0; // 가방의 상태를 0으로 초기화 } sort(Bag, Bag + K); // 오름차순 정렬 /* for (int i = 0; i < N; i++) { cout << Dia[i].first << " "; cout << Dia[i].second << endl; } for (int i = 0; i < K; i++) { cout << Bag[i] << endl; } */ long long Money = 0; for (int i = 0; i < N; i++) { FindBag(Dia[i], K, Bag, & Money, check); } cout << Money << "\n"; }

제출 #38118

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: