5710.電気料金


1.問題リンク
2.参照リンク

1.トラブルシューティング

1. 상근이는 매우 전기를 아끼는 사람이다. 따라서, 항상 자신이 사는 건물에서 가장 전기를 적게 쓴다고 확신한다. 상근이는 돈도 전기만큼 아낀다.
2. A: 총 사용량의 금액 (이웃 사용량 + 상근이 사용량)
3. B: 이웃의 전기 요금과의 차이 (절댓값)
1からAとBの条件に合った料金を探せばタイムアウトが発生します.
1 <= A,B <= 10^9

1-1. Cost -> Watt


コストをWattに返却する方法を実現します.
問題では、指定されたテーブルに基づいて、次のソースコードを実装できます.
private static int use(int cost) {
	if (cost > 4979900)
		return (cost + 2020100) / 7;
	else if (cost > 29900)
		return (cost + 20100) / 5;
	else if (cost > 200) 
		return (cost + 100) / 3;
	else
		return cost / 2;
}
ノートに直接書くことをお勧めします

1-2. Watt -> Cost


1−1とは対照的に、所与のWattを用いてコストを取得する方法が実現される.
private static int use(int cost) {
	if (cost > 4979900)
		return (cost + 2020100) / 7;
	else if (cost > 29900)
		return (cost + 20100) / 5;
	else if (cost > 200)
		return (cost + 100) / 3;
	else
		return cost / 2;
}

1-3. 二分探索を行う


A,B条件を満たし,尚根が使用するWattを求める必要があるため,Wattを対象として二分探索を行った.
範囲を設定する場合、左は0、右はAではありません.
彼が探している対象はWattだからだ.(A、Bはコスト)
したがって,二分探索は以下のようになる.
1. 비용 -> Watt로 하여 이분 탐색의 범위를 설정한다.
2. 이분 탐색을 진행하여 현재 mid(c1)값과 total-mid(c2) 값의 비용을 계산한다.
3. 2번에서 계산된 비용의 차(|c2-c1|)가 B와 동일하다면 최소 비용을 반환한다.
 3-1. 동일하지 않다면 |c2-c1|가 클 경우 right=mid, 작을 경우 left=mid+1를 하여 탐색을 계속 진행한다.

2.ソースコード

//전기 요금
import java.util.*;
import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		while (true) {
			StringTokenizer st = new StringTokenizer(br.readLine());

			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());

			if (A == 0 && B == 0)
				break;

			System.out.println(findWatt(A,B));
		}
	}
	
	private static long findWatt(int A, int B) {
		int left = 0;
		int total = use(A);
		int right = total;
		
		while(left < right) {
			int mid = (left + right) /2;
			
			long c1 = cost(mid);
			long c2 = cost(total - mid);
			
			if(Math.abs(c2-c1) == B) {
				return Math.min(c1, c2);
			}
			
			if(Math.abs(c2-c1) > B)
				right = mid;
			else
				left = mid+1;
		}
		
		return 0;
	}



	private static int use(int cost) {
		if (cost > 4979900)
			return (cost + 2020100) / 7;
		else if (cost > 29900)
			return (cost + 20100) / 5;
		else if (cost > 200)
			return (cost + 100) / 3;
		else
			return cost / 2;
	}

	private static long cost(int use) {
		if (use > 1000000)
			return use * 7 - 2020100;
		else if (use > 10000)
			return use * 5 - 20100;
		else if (use > 100)
			return use * 3 - 100;
		else
			return use * 2;
	}
}
#### ```