PA 2019 Runda 2 Herbata 题解

题目分析

这道题要求判断是否可以通过无限次的分割和混合操作，将初始状态的水杯 $(l_i, a_i)$ 转化为目标状态 $(l_i, b_i)$。

关键操作：

1. 分割：将一杯水按任意比例分成多杯，温度保持不变
2. 混合：将两杯水混合，新温度为体积加权平均温度

解题思路

核心观察

1. 守恒量：总热量（体积 × 温度）在操作过程中守恒
2. 温度范围：混合后的温度一定在原来两杯水的温度之间
3. 问题转化：问题等价于判断能否通过重新分配热量来达到目标状态

算法设计

代码采用了贪心匹配的方法：

主要步骤：

1. 将初始状态 $(l_i, a_i)$ 和目标状态 $(l_i, b_i)$ 分别存储
2. 按温度排序初始状态和目标状态
3. 使用双指针贪心匹配：
   • 每次取当前温度最低的初始水和目标水
   • 用尽可能多的热量从初始水转移到目标水
   • 检查过程中是否出现热量不足的情况

代码详解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll N = 1000010;

ll n;
struct Nd {
    ll x, y;  // x: 体积, y: 温度
    friend ll operator<(const Nd &a, const Nd &b) {
        return a.y < b.y;  // 按温度排序
    }
} a[N], b[N];

void solve() {
    cin >> n;
    
    // 读入数据：初始状态 (l_i, a_i) 和目标状态 (l_i, b_i)
    for (ll i = 1, x, y, z; i <= n; i++) {
        cin >> x >> y >> z;
        a[i] = {x, y};  // 初始：体积x，温度y
        b[i] = {x, z};  // 目标：体积x，温度z
    }
    
    // 按温度排序
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    
    ll i = 1, j = 1;  // 双指针
    ll s = 0;         // 热量差（当前累积的热量盈余/赤字）
    
    while (i <= n && j <= n) {
        // 取当前可转移的最小体积
        ll w = min(a[i].x, b[j].x);
        
        // 计算热量变化：从温度a[i].y的水转移到温度b[j].y的目标
        // 热量差 = (目标温度 - 初始温度) × 体积
        s += (b[j].y - a[i].y) * w;
        
        // 如果热量差为负，说明热量不足，无解
        if (s < 0) {
            cout << "NIE\n";
            return;
        }
        
        // 更新剩余体积
        if (!(a[i].x -= w)) i++;
        if (!(b[j].x -= w)) j++;
    }
    
    // 检查是否所有水都处理完且热量平衡
    cout << (i > n && j > n && !s ? "TAK\n" : "NIE\n");
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    ll T;
    cin >> T;
    while (T--) solve();
    return 0;
}

算法原理

为什么这样是正确的？

1. 热量守恒：

   • 总热量 = Σ(体积 × 温度) 在操作中保持不变
   • 如果初始总热量 ≠ 目标总热量，肯定无解

2. 温度可行性：

   • 混合操作只能产生介于原温度之间的温度
   • 如果目标温度不在初始温度范围内，需要热量转移

3. 贪心策略：

   • 从低温开始匹配，确保热量总是从高温向低温转移
   • 如果出现热量赤字，说明无法达到目标

关键变量解释

• s：累积的热量差

  • s > 0：有多余热量可以用于升温
  • s < 0：热量不足，无法达到目标温度
  • s = 0：热量恰好平衡

• (b[j].y - a[i].y) * w：转移热量

  • 如果为正：需要消耗热量来升温
  • 如果为负：释放热量可用于其他升温

样例分析

样例1：TAK

输入：2
      2 1 4
      2 5 2

初始：2体积1°C + 2体积5°C = 总热量12
目标：2体积4°C + 2体积2°C = 总热量12
热量守恒，温度在范围内，有解

样例2：NIE

输入：2
      1 4 3
      1 5 4

初始：1体积4°C + 1体积5°C = 总热量9
目标：1体积3°C + 1体积4°C = 总热量7
总热量不守恒，无解

复杂度分析

• 时间复杂度：$O(n \log n)$，主要来自排序
• 空间复杂度：$O(n)$，存储初始和目标状态

正确性证明

定理：算法输出TAK当且仅当存在可行解

证明：

1. 必要性：如果算法输出TAK，那么：

   • 总热量守恒（最终s=0）
   • 所有温度转移都可行（过程中s≥0）
   • 因此存在可行的操作序列

2. 充分性：如果存在可行解，那么：

   • 总热量必须守恒
   • 必须能够通过混合操作实现温度转换
   • 贪心策略会找到这样的方案

总结

这道题的关键在于：

1. 识别热量守恒这一核心物理原理
2. 将问题转化为热量转移的可行性判断
3. 使用贪心算法高效验证可行性

算法巧妙地利用了排序和双指针技术，在 $O(n \log n)$ 时间内解决了问题，能够处理大规模输入。