リンク

リンクテキスト

質問する

恩恵は肉屋で肉を買いたい.一般的に、肉屋は自分の欲しい量といえば肉をいくら売っても、恩恵が訪れる肉屋は割引しているので、N枚の肉はもう切って売っています.
どれも一定の重さと価格があり、どれも買うと、それより安い肉が無料でもらえます(追加料金はかかりません).また、肉の部位ごとに異なる場合があるため、費用と重量の関係は比例しない可能性があります.恩恵はこの点を考慮せず,任意の部位が自分の欲しい量だけ購入すればよいと仮定した.また、価格がもっと安ければ、恩恵を必要とする量ではなく、より多くの肉を買うかもしれません.
各ブロックの情報を取得する場合は、恩恵購入に必要な肉の最低コストを計算するプログラムを作成します.

入力

第1行は2つの整数N(1≦N≦100000),M(1≦M≦2147483647)を与える.Nは塊の個数を表し、Mは恩恵を必要とする肉の量である.次のN行は、各肉の重量と価格を表す2つの整数を与える.重量の合計と価格の合計はそれぞれ2147483647を超えない.

しゅつりょく

最初の行に答えを印刷します.不可能な場合は-1を出力します.

に答える

問題を理解するのに1日くらいかかったようです.
だから週末は必ず復習し直します!!
リファレンスリンク

肉重、価格を入力して

に並べ替えます

(価格、重量)、価格は昇順、重量は降順=>前からナビゲートし、価格が低く重量の大きい肉

を選択する.

肉の重量を増加し、以前に探索した肉の価格と一致するかどうかを確認する=>この問題の核心例外例

以前の肉の価格と一致する場合、同じ変数に

を加える.

これまで、肉の重量がMを超えると、結果値(ans)

が更新する.

これまで閲覧した肉に同じ価格の肉がある場合は、該当する値(同じ)を追加してください.

これまで肉の重さはMを超え、最低価格で更新されていました

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class practice {
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		int n=Integer.parseInt(st.nextToken()); //덩어리의 개수
		int m=Integer.parseInt(st.nextToken()); //필요한 고기의 양
		int arr[][]=new int[n][2];
		int answer=Integer.MAX_VALUE;
		
		
		for(int i=0; i<n; i++)
		{
			StringTokenizer st1=new StringTokenizer(br.readLine());
			int weight=Integer.parseInt(st1.nextToken());
			int price=Integer.parseInt(st1.nextToken());
			arr[i][0]=weight;
			arr[i][1]=price;
		}
		
		
		
		//0이 무게, 1이 가격
		//무게 내림차순, 가격 오름차순
		Arrays.sort(arr, new Comparator<int[]>() {
			public int compare(int[] o1, int[] o2)
			{
				if(o1[1] > o2[1]) //가격 오름차순
					return 1;
				
				else if(o1[1] == o2[1])
					return Integer.compare(o2[0], o1[0]);//내림차순
				
				else //정렬 X
					return -1;
			}
		});	
		
		//temp : 무게의 누적 총 합을 구할 변수,
		//same : 가격이 같을 때 가격의 누적 합
		int temp=0, same=0;
		boolean stop=false;
		
		for(int i=0; i<n; i++)
		{
			temp+=arr[i][0]; //무게 누적 총합
			if(i>=1 && arr[i-1][1] == arr[i][1])//이전과 가격이 같을때
				same+=arr[i][1];
			else same=0; //가격이 다를때
			
			if(temp>=m) //조건 m보다 같거나 클 때
			{
				stop=true; //표시
				answer=Math.min(answer, arr[i][1]+same);
			}
			
		}
		if(stop)
			System.out.println(answer);
		else
			System.out.println(-1);
		
		
	}
}