UVa 13242 題解 — C++

此筆記為UVa 13242的題目詳解，包含解題思路、C++範例程式碼。

Pool Filling (OnlineJudge 13242)

題目

There is an empty pool that needs to be filled with water at a desired temperature. To do this, you have a row of jars placed near the border of the pool and numbered starting at 0. Each jar contains a different volume of water at a different temperature. You can pour as many jars as you want to the pool, but only if they are consecutive.

The objective is to fill at least half the capacity of the pool, without overflowing it, so that the resulting water temperature is as close as possible to a target temperature, and never more than 5 degrees hotter or warmer. We will assume that, when mixing two volumes of water, the resulting temperature of the mix is the average of the original temperatures weighted by volume.

For example, you may have 5 jars as follows:

Jar number	Volume (l)	Temperature (°C)
0	45	20
1	20	40
2	67	22
3	109	11
4	9	56

This way, for example, you could pour jars 1, 2 and 3 into the pool, but not only jars 1 and 3.

The resulting total volume (assuming that the pool is large enough) would be

$20+67+109=196$ liters and the resulting temperature would be

$(20\times 40+67\times 22+109\times 11)/(20+67+109)=17.719388°C$.

輸入 / 輸出說明

輸入說明

輸出說明

The input format is as follows. An integer in a single line which says the number of problems to solve. Then, for each problem: • A line with two integers: the maximum capacity of the pool and the target temperature. • A line with one integer: the number of jars, which will not be greater than 3000. • Then, a line for each jar containing two integers: the volume of water in the jar and its temperature.

For each problem, you have to print a line with two integers representing the first and the last jar to pour into the pool, minimizing the difference with respect to the target temperature. If there is no way to fill at least half the pool without overflowing it with water within the acceptable temperature range, the line should be ‘Not possible’. If there are many optimal solutions, you have to use the jars with the lowest numbers.

解題思路

這一題請放心大膽的用兩層巢狀迴圈去做。

我們只須不斷累加 體積 * 溫度(volume_temperature) 與 體積(volume) 並計算 溫度(temperature) = volume_temperature / volume、差距目標溫度的溫差(gap) = | temperature - target_T |，並與先前的 最小溫差(min) 比較，若比較小且溫差 < 5°C、容量(capacity) 的一半 ≤ 體積 ≤ 容量(capacity) 就更新 最小溫差、起始點、終點即可。

最後如果 最小溫差(min) 還是原本設定的 10 的話就代表不可能達成。

範例程式碼

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i, j;
	int capacity, target_T, n, q, solove = 0;
	
	cin >> q;
	
	while (solove < q) {
		solove++;
		
		cin >> capacity >> target_T >> n;
	
		int jar[n][2], min_start, min_end;
		float half_c, volume, volume_temperature, temperature, gap, min = 10;
		
		half_c = capacity / 2.0;  //一半的容量 
		
		cin >> jar[0][0] >> jar[0][1];
		
		for (i=1;i<n;i++)
			cin >> jar[i][0] >> jar[i][1];
		
		for (i=0;i<n;i++) {
			volume_temperature = 0;  //體積 * 溫度預設為 0 
			volume = 0;  //體積預設為 0 
			
			for (j=i;j<n;j++) {
				volume_temperature += jar[j][0] * jar[j][1];  //體積 * 溫度 
				volume += jar[j][0];  //體積 
				temperature = volume_temperature / volume;  //當前溫度 
				gap = abs(temperature-target_T);  //當前溫度與目標溫度的距離 
				
				if (gap <= 5 && gap < min && volume >= half_c && volume <= capacity) {
					min = gap;  //更新最小差距 
					
					//更新最小容量始末位置 
					min_start = i;
					min_end = j;
				}
			}
		}
		
		if (min == 10)
			cout << "Not possible" << endl;
		else
			cout << min_start << " " << min_end << endl;
	}

	return 0;
}

運行結果

AC 0.02s

tags: CPE 2星

查看更多資訊請至：https://www.tseng-school.com/