题解：P11628 [WC2025] 猫粮（暂无数据）

场外口胡选手来一发题解。

观察可知我们的每只猫猫都只会吃到两袋猫粮，证明是显而易见的：如果有一只猫猫吃到了更多猫粮，则一定会有猫猫只能吃到不超过一袋猫粮，而一袋猫粮必定会把猫猫饿成猫饼，所以为了避免这种情况的发生，我们必须保证每只猫猫与两袋猫粮匹配。

以及，同样观察可知，所有猫粮加在一起的重量恰好等于 $n \times m$，因此为了全体猫猫的幸福，没有任何一只猫猫能浪费一粒猫粮，故给每只猫猫的两袋猫粮一定满足和为 $m$。

然后思考两种猫粮的区别：由于优质猫粮过于不可控导致其实际上变成了对选手而言的劣质猫粮，你直接往猫堆里丢两袋优质猫粮那到底是不是你希望的猫猫抢到根本不可控，所以考虑尽可能让一袋优质猫粮与一袋劣质猫粮匹配，尽力确保每一只抢到优质猫粮的猫猫都能恰好吃饱。

于是我们剩下了一堆猫粮，有优质的也有劣质的，但是互相之间已经不能匹配了。考虑先处理掉比较方便处理的部分：劣质猫粮。尽可能匹配掉所有劣质猫粮，注意无法匹配时宣告无解。

对于剩下的优质猫粮和嗷嗷待哺一口饭还没吃上的可怜猫猫，只有两种可能可以成功：

否则，对于你扔下的任何两袋猫粮，一定存在有坏猫猫会抢走你给其它猫猫安排的饭饭的可能性。

综上，我们得到了策略：先尽可能一一匹配所有优质与劣质猫粮，接着处理掉所有劣质猫粮并确认是否可行，最后特判掉所有优质猫粮即可。时间复杂度 $O(Tn)$。

代码等数据造好了补。