题解 P5980 【[PA2019]Herbata】

· · 题解

要能够从初始状态变成指定的终止状态，首要的条件是能量守恒。

即，

\sum_{i=1}^{n}a_il_i=\sum_{i=1}^{n}b_il_i

然而满足流量守恒只是有解的必要条件，事实上还有很多情况会导致无解。

那么怎样才能确保有解呢？

想象这样一个场景：你手头有一张借记卡（不能欠款），你会不停地收入一些钱，花掉一些钱，当一次消费的金额大于卡内余额的时候，这次消费就不能进行了。

到这个题里，我们也可以开一张「能量借记卡」。

我们将本题的一些概念用金融中的术语表达：l_i 可以认为是第 i 笔账单的数量，a_i 可以认为是每笔账单的支出（因此初态中的第 i 个杯子可以变成 l_i 个单价为 a_i 的商品）；同理，b_i 可以认为是每笔账单的收入（因此终态中的第 i 个杯子可以变成 l_i 张每张票面金额为 b_i 的支票）。

首先将初始状态的 n 个杯子按温度升序排序，终态的 n 个杯子也按温度升序排序。

接下来我们搞两个指针 p,q，刚开始 p 指向初始态的第一个杯子，q 指向终态的第一个杯子。

我们现在可以用 q 中的支票去买 p 中的商品。当然商家很刁钻，一张支票只能买一个商品。

如果一张支票的金额大于一个商品的钱，我们就可以将多余的钱（或者说是能量）存进银行卡，如果一张支票的金额小于一个商品的钱，我们就需要从银行卡里取些钱（能量）了。

（p 中的商品数和 q 中的支票数可能不一定相等，不过这不是问题，p 空的时候就将 p 向后移动，q 空的时候也将 q 向后移动就行了，别忘了总商品数和总支票数是相等的）

因为我们手里拿的是借记卡，所以任何时候余额都不能为负。

如果我们顺利地走完了上面的整个过程（也就是说没有赊账的情况发生），说明有解。否则无解。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
 ios::sync_with_stdio(false);
 int t;
 cin>>t;
 while(t--)
 {
  vector<pair<int,int> > a,b;
  int n;
  cin>>n;
  for(int i=1;i<=n;i++)
  {
   int l,x,y;
   cin>>l>>x>>y;
   a.push_back({x,l});
   b.push_back({y,l});
  }
  sort(a.begin(),a.end());
  sort(b.begin(),b.end());
  int p=0,q=0;
  long long sum=0;
  bool flag=true;
  while(p<n)
  {
   int l=min(a[p].second,b[q].second);
   sum-=1ll*l*(a[p].first-b[q].first);
   if(sum<0)
   {
    flag=false;
    break;
   }
   a[p].second-=l,b[q].second-=l;
   if(a[p].second==0)p++;
   if(b[q].second==0)q++;
  }
  if(flag&&sum==0)cout<<"TAK"<<endl;
  else cout<<"NIE"<<endl;
 }
 return 0;
}