自动搬运

查看原文

来自洛谷，原作者为

	StudyingFather 在纷繁杂乱的世界里，独自寻找属于自己的光荣与梦想。

搬运于2025-08-24 22:16:11，当前版本为作者最后更新于2020-01-27 22:26:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

即，

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

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

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

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

我们将本题的一些概念用金融中的术语表达：$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;
}