# Pool Filling(UVA13242)
## 題目
[點我](https://onlinejudge.org/external/132/13242.pdf)

## 解題網站
[UVA](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=878&page=show_problem&problem=5165)
ZJ上無此題

## 題意
有一個游泳池與n個罐子，每個罐子裡有水，水有溫度與體積，要把罐子的水(連續區段)倒入游泳池，倒入的水會加權影響溫度，給定最大容量與目標溫度，計算在符合限制條件下，與目標溫度差最小的連續區段為何？

## 複雜度分析
題目說共有t筆測資，每筆測資中，n(罐子的數量)<=3000，因此若每筆測資採用$O(n^2)$的演算法，計算量約為$t\times 3000^2=t\times 9\times 10^6$，大概不會TLE，因此採取$O(n^2)$的演算法

## 演算法

對於每筆測資
1. 輸入tC(maximum capacity), tT(target temperature)
2. 宣告minT=最大值(最小溫度差), ansI, ansJ，並輸入n
3. 把n個罐子的體積與溫度輸入到vector v中
4. for (int i = 0; i < n; i++) // i代表起始罐子的編號
    3.1. 宣告c([i,j]的體積)=0, t=0([i,j]的加權溫度)
    3.2. for (int j = i; j < n; j++) // j代表終點罐子的編號
        3.2.1. c += v[i].體積
        3.2.2. t += v[i].溫度 * v[i].體積
        3.2.3. 如果 (c >= tC / 2) and (c <= tC) and (abs(t / c - tT) <= 5) and (abs(t / c - tT) < minV)，則更新minT, ansI, ansJ
5. 輸出ansI, ansJ

## 程式碼

#include <bits/stdc++.h>
#define int long long int
#define C first
#define T second
using namespace std;

signed main() {
    int cas;
    cin >> cas;
    while (cas--) {
        double tC, tT;
        cin >> tC >> tT;
        
        double minT = DBL_MAX, ansI, ansJ;
        int n;
        cin >> n;

        vector <pair <double, double>> v(n);
        for (int i = 0; i < n; i++) {
            cin >> v[i].C >> v[i].T;
        }

        for (int i = 0; i < n; i++) {
            double c = 0, t = 0;
            for (int j = i; j < n; j++) {
                c += v[j].C;
                t += v[j].T * v[j].C;
                if (c >= tC / 2 and c <= tC and abs(t / c - tT) <= 5 and abs(t / c - tT) < minT) {
                    minT = abs(t / c - tT);
                    ansI = i;
                    ansJ = j;
                }
            }
        }
        if (minT == DBL_MAX) {
            cout << "Not possible" << endl;
        } else {
            cout << ansI << " " << ansJ << endl;
        }
    }
    return 0;
}